Algorithme de Grover

Algorithme de Grover

En informatique quantique, l´algorithme de Grover est un algorithme de recherche, permettant de rechercher un ou plusieurs éléments qui répondent à un critère donné parmi N éléments non classés en temps proportionnel à \sqrt {N} et avec un espace de stockage proportionnel à log N. Il a été découvert par Lov Grover en 1996[1].

Dans les mêmes conditions (recherche parmi des éléments non classés), un algorithme classique ne peut faire mieux qu'une recherche dans un temps proportionnel à N, en testant successivement le critère sur chaque élément. L'étendue de la gamme de critères pouvant être utilisée par cet algorithme lui donne un caractère universel, ce qui en fait un des algorithmes les plus importants et potentiellement le plus utile de l'informatique quantique.

L'exemple classique d'utilisation de cet algorithme est la recherche, dans un annuaire téléphonique ordinaire classé alphabétiquement, du nom qui correspond à un numéro de téléphone donné. L'algorithme de Grover fonctionne toujours en lui présentant les nombres entiers de 1 à N, représentant dans le cas de l'annuaire une position dans ce dernier. Le critère de sélection est dans ce cas : la position correspond à un numéro de téléphone donné. La position étant connue, on en déduit le nom ou toute autre information liée à la position.

Plus généralement, l'ensemble des nombres entiers de 1 à N peut indexer un ensemble de solutions possibles à un problème. Dans ce cas, s'il est possible de vérifier rapidement qu'une solution résout un problème (ce qui est généralement le cas, et ce qui définit même toute une classe importante de problèmes dits de complexité NP), alors il est possible à l'aide de cet algorithme d'accélérer notablement la recherche des solutions de ces problèmes par rapport à une « recherche brute ».

Parmi les problèmes « NP» (et même « NP-Complet ») qui pourraient être résolus par cet algorithme se trouvent notamment :

Malgré tout, ce genre de problème est souvent de complexité exponentielle par rapport au nombre d'éléments du problème (typiquement, N = 2n si n est le nombre d'éléments mis en jeu dans le problème). Même si cet algorithme apporte une optimisation non négligeable (quadratique) par rapport à une recherche brute, cet algorithme transforme un problème de complexité 2n en \sqrt {2^n} = 2^{n/2}, qui demeure exponentielle.

Certains algorithmes classiques, adaptés à un problème particulier, peuvent faire mieux, surtout si on tolère une solution approximative, ou probabiliste. Mais cet algorithme présente le double avantage d'être généraliste (dès que l'on a l'algorithme pour vérifier une solution, on a automatiquement l'algorithme pour trouver la solution), et de garantir de trouver la ou les solution(s) optimale(s).

Il a été prouvé en 1999, par Christof Zalka[2], que l'algorithme de Grover est l'algorithme quantique le plus efficace pouvant traiter le problème de la recherche non structurée. Il est impossible de faire mieux qu'une amélioration quadratique de la complexité, en utilisant le parallélisme du calcul quantique.

Sommaire

Principe de l'algorithme

Rappels et notations

En calcul quantique, l'information est codée par des qbits, qui possèdent comme tout objet quantique la particularité de pouvoir être simultanément dans deux états différents notés \left| 0 \right\rangle et \left| 1 \right\rangle[3]. Cet état superposé est un vecteur, combinaison linéaire des deux états \alpha \cdot \left| 0 \right\rangle + \beta \cdot \left| 1 \right\rangle, α et β étant deux scalaires complexes.

N qbits peuvent être intriqués de manière à former une superposition de 2N états : c_1 \cdot \left| 000..00 \right\rangle + c_2 \cdot \left| 000..01 \right\rangle + c_3 \cdot \left| 000..10 \right\rangle + .. + c_{2^N} \cdot \left| 111..11 \right\rangle. Ce vecteur est normé, de sorte que \sum_{i=1}^{2^N}{|c_i|}^2 = 1.

Les lois de la mécanique quantique interdisent d'avoir une information complète sur un état quantique, et donc de déterminer toutes les valeurs c1,c2,.. En fait, lors d'une mesure de cet état intriqué, l'état va se retrouver aléatoirement dans un et un seul état \left| 000..00 \right\rangle , \left| 000..01 \right\rangle , \left| 000..10 \right\rangle , ... , \left| 111..11 \right\rangle, avec une probabilité respective de {|c_1|}^2, {|c_2|}^2, ... , {|c_{2^N}|}^2.

Ceci est la limitation principale du calcul quantique, qui est en mesure de calculer simultanément 2N résultats, mais auxquels on ne peut avoir directement accès. Tout algorithme quantique doit donc comporter une phase qui permet d'exploiter et de mesurer les résultats, ce qui va venir gréver les performances idéales que permettraient le parallélisme quantique. C'est exactement ce qui va se passer pour l'algorithme de Grover.

Présentation générale de l'algorithme

L'algorithme de Grover incorpore deux éléments principaux :

  1. Une « boîte noire », ou Oracle, qui détermine si un état quantique (\left| 000..00 \right\rangle , \left| 000..01 \right\rangle , \left| 000..10 \right\rangle , ... , \left| 111..11 \right\rangle) donné en entrée correspond à un certain critère. C'est cette boîte noire qui permet de particulariser l'algorithme à un problème donné.
  2. Un algorithme d'amplification d'amplitude, qui permet de rendre exploitable et mesurable l'information donnée par la boîte noire. Cet algorithme est indépendant de la boîte noire, et c'est cette procédure qui nécessite O(\sqrt N) itérations.


La boîte noire est définie mathématiquement par une fonction fcritere(x) qui identifie si un état « x » vérifie un certain critère :

f_{critere}(x) = \begin{cases} 1, & \mathrm{Si~x~v\acute erifie~le~crit\grave ere} \\ 0, & \text{sinon} \end{cases}

Cette boîte noire est bien entendu en mesure d'accepter une superposition d'états en entrée, et donc de vérifier le critère simultanément pour tous les états de la superposition. En effet, la boîte noire est elle-même implémentée par un calcul quantique, qui est en mesure d'opérer sur une superposition d'un bout à l'autre d'algorithme qui détermine le critère.

Le propos de l'algorithme est maintenant le suivant : étant donné un état initial Ψ0 équi-superposé[4] de tous les états possibles de N qbits :

\left| \Psi_0 \right\rangle = \frac{1}{\sqrt {2^N}} \sum_{x=0}^{{2^N}-1}{\left| x \right\rangle }

comment la boîte noire va-t-elle influencer cet état pour donner un résultat mesurable ? Pour pouvoir mesurer le résultat, et trouver ainsi le résultat en une seule opération, l'état final doit être :

\left| \Psi_{final} \right\rangle = \varepsilon \cdot \left| 000..00 \right\rangle + \varepsilon \cdot \left| 000..01 \right\rangle + .. + 1-\varepsilon \cdot \left| cible \right\rangle + .. + \varepsilon \cdot \left| 111..11 \right\rangle

afin de mesurer avec une quasi-certitude l'état \left| cible \right\rangle, qui a été signalé par la boîte noire.


Pour aboutir à ce résultat, l'algorithme de Grover procède ainsi (on suppose dans cet exemple N = 3 qbits, ce qui donne 8 = 23 états superposés, et l'état à rechercher est l'état 6) :

  1. Préparation d'un état équi-superposé
  2. L'algorithme fait en sorte que la boîte noire inverse la phase de l'état (ou des états) qui vérifie le critère
  3. L'algorithme applique ensuite un opérateur d'amplification d'amplitude, qui effectue un miroir des amplitudes autour de la moyenne des amplitudes. Cela a pour effet d'amplifier l'état cible, et de diminuer les autres états (voir schémas)
  4. On itère au total les étapes 2 et 3, \frac {\pi}{4} \sqrt{8} \approx 2 fois, pour obtenir l'état final

  • 1 : État initial

  • 2 : Application de l'oracle

  • 3 : Application de l'opérateur « miroir autour de la moyenne »

  • 3 : État amplifié

  • 4 : État final, après une itération supplémentaire

Cliquez sur une vignette pour l’agrandir

L'état peut être alors mesuré pour obtenir, avec une quasi-certitude, l'état recherché.

Remarques et éléments complémentaires

Nombre d'itérations. Optimalité du nombre d'itérations

Probabilité de détection en fonction du nombre d'itérations, pour 10 qbits = recherche parmi 1024 éléments

Le nombre d'itérations optimal est exactement de k = \frac {\pi}{4} \sqrt{2^N}, N étant le nombre de qbits (voir Détermination du nombre d'itérations optimal). Au delà de ce nombre, la probabilité de détection commence à décroître. C'est pourquoi C.P. Williams, dans son livre Explorations in Quantum Computing, aime citer l'épouse d'un informaticien quantique qui compare l'algorithme de Grover à la cuisson d'un soufflé : il est nécessaire d'arrêter l'algorithme ni trop tôt ni trop tard.

La probabilité de détecter la solution est non-nulle dès la première itération et s'accroît à chaque itération. Serait-il possible d'accélérer le processus en s'arrêtant (par exemple) à \frac k {10} itérations, vérifier si le résultat mesuré est une solution (ce qui est rapide), sinon tout recommencer pour de nouveau \frac k {10} itérations etc...? Est-ce que, en moyenne, ce processus ne serait pas plus rapide que de faire à chaque fois le nombre d'itérations optimal ? Le calcul montre que cette stratégie nécessite, en moyenne, le même nombre d'itérations que le nombre optimal, sans compter le coût de réinitialiser le dispositif à chaque échec[Williams 1].

Applications de l'algorithme de Grover

L'algorithme de recherche de Grover est très versatile : l'opérateur qui identifie les solutions du problème (l'Oracle) étant clairement dissocié du reste de l'algorithme, il peut être utilisé pour des problèmes très divers, et notamment pour les problèmes de complexité NP (voir introduction).

On peut également utiliser l'Oracle à d'autres niveaux, pour non pas rechercher directement des solutions, mais pour chercher des heuristiques de solutions. Par exemple, il est en théorie possible d'utiliser l'algorithme de Grover pour accélérer les algorithmes probabilistes classiques[Williams 2]. Dans un algorithme probabiliste, on utilise successivement plusieurs graines de générateur de nombres pseudo-aléatoires : certaines graines vont s'orienter vers la solution, d'autres graines vont faire diverger l'algorithme. On s'arrête après l'essai successif d'un certain nombre N de graines, dès qu'une même solution semble être désignée par plusieurs graines, alors que les autres graines donnent des résultats très différents. L'algorithme de Grover peut donner les mêmes résultats, en exploitant une superposition de graines, en \sqrt N étapes seulement[5].

Dans un autre domaine, l'algorithme de Grover peut être utilisé, non pour faire des recherches de solution, mais uniquement pour ses capacités d'amplification d'amplitude. Les chercheurs en physique quantique ont souvent le besoin de préparer objet quantique dans état particulier, ce qui est en général extrêmement difficile. L'algorithme de Grover permet de fabriquer un état quantique donné, en n'amplifiant que les composantes voulues par l'expérimentateur[6].

Récursivité de l'algorithme de Grover et traitement des problèmes NP-Complets

Il est en théorie, et en pratique, possible d'utiliser l'algorithme de Grover lui-même dans l'Oracle, menant à une certaine forme de récursivité de l'algorithme.

Cette forme de récursivité s'applique particulièrement bien aux problèmes NP-Complets dont la recherche de solution s'effectue souvent en descendant un arbre de recherche[Williams 3]. Au lieu de rechercher la solution parmi toutes les solutions terminales de l'arbre, ce qui mène à une complexité brute de O \left( b^{\frac \mu 2} \right) (contre O \left( b^{\mu} \right) pour un algorithme classique), il est possible d'obtenir une complexité de O \left( b^{\alpha \frac \mu 2} \right) (avec α un facteur inférieur (voire très inférieur) à un, dépendant du problème considéré) en appliquant l'algorithme de Grover aux niveaux successifs de l'arbre. La complexité demeure toujours exponentielle, mais l'amélioration est telle que l'algorithme quantique est alors en mesure d'être meilleur que les meilleurs algorithmes classiques pour résoudre ces problèmes NP-Complets[Williams 4].

Détails d'implémentation de l'algorithme

Opérateur de Grover

Circuit quantique représentant l'algorithme de Grover

L'opérateur quantique itéré, dit « opérateur de Grover », s'exprime sous la forme suivante :

\hat G = \hat H \hat Z \hat H \hat O


  • \hat O est l'Oracle (Uω sur la figure ci-contre).
  • \hat H est l'opérateur (ou transformation) de Hadamard, qui est un opérateur de base en calcul quantique. Il est tel que \hat H = \frac 1 {\sqrt 2} \left( \left| 0 \right\rangle \left\langle 0 \right| + \left| 1 \right\rangle \left\langle 0 \right| - \left| 0 \right\rangle \left\langle 1 \right| + \left| 1 \right\rangle \left\langle 1 \right| \right) = \frac 1 {\sqrt 2} \begin{pmatrix} 1 & 1 \\ -1 & 1 \end{pmatrix} .
    Il possède la propriété de transformer un état pur en un état superposé, et réciproquement.
  • \hat Z est l'opérateur « Zero phase shift » défini comme \hat Z = 2 \left| 0 \right\rangle \left\langle 0 \right| - \hat I (\hat I étant l'opérateur identité).

Opérateur de diffusion de Grover (miroir autour de la moyenne)

C'est \hat H \hat Z \hat H, qui va inverser les états autour de la moyenne (voir présentation générale de l'algorithme). En effet :

\begin{align} \hat H \hat Z \hat H & = \hat H \left( 2 \left| 0 \right\rangle \left\langle 0 \right| - \hat I \right) \hat H \\ & = 2 \hat H \left| 0 \right\rangle \left\langle 0 \right| \hat H - \hat H \hat I \hat H \\ & = 2 \left| \Psi_0 \right\rangle \left\langle \Psi_0 \right| - \hat H \hat I \hat H \\ & = 2 \left| \Psi_0 \right\rangle \left\langle \Psi_0 \right| - \hat I \\ & = \frac 2 {2^N} \sum_{i,j} \left| i \right\rangle \left\langle j \right| - \hat I \end{align}

\Psi_0 = \hat H \left| 0 \right\rangle est l'état équi-superposé initial.

En appliquant cet opérateur \hat M = \hat H \hat Z \hat H à un état quelconque \left| \Psi \right\rangle = \sum_k c_k \left| k \right\rangle :

\begin{align} \hat M \left| \Psi \right\rangle & = \left( \frac 2 {2^N} \sum_{i,j} \left| i \right\rangle \left\langle j \right| - \hat I \right) \left( \sum_k c_k \left| k \right\rangle \right) \\ & = \frac 2 {2^N} \left( \sum_{i,j} c_j \left| i \right\rangle \right) - \sum_k c_k \left| k \right\rangle \\ & = \frac {2 \sum_j c_j} {2^N} \sum_i \left| i \right\rangle - \sum_k c_k \left| k \right\rangle \\ & = \sum_k \left( 2 \left\langle c \right\rangle - c_k \right) \left| k \right\rangle \end{align}

Chaque amplitude est transformée c_k \Rightarrow 2 \bar c - c_k ce qui constitue en effet un miroir de l'amplitude autour de la moyenne des amplitudes.

Détermination du nombre d'itérations optimal

Il existe plusieurs démonstrations du nombre optimal d'itérations k = \frac {\pi}{4} \sqrt{2^N}. Les unes effectuent une interprétation géométrique de l'opérateur de diffusion de Grover, faisant apparaître une analogie entre cet opérateur et une rotation progressive du vecteur d'état de l'état initial vers l'état cible. L'état initial et l'état cible étant orthogonaux, il suffit de compter le nombre de rotations pour aboutir à une rotation totale de \frac \pi 2[Williams 5]. On peut également, plus algébriquement, calculer combien d'inversions autour de la moyenne sont nécessaires pour aboutir à un maximum, en partant d'une distribution uniforme \frac 1 {\sqrt {2^N}}.

Voici une démonstration du calcul du nombre d'itérations, par la méthode géométrique[7]

Interprétation géométrique de l'opérateur de Grover

Soit l'état initial équi-superposé :

\left| \Psi_0 \right\rangle = \frac{1}{\sqrt {2^N}} \sum_{x=0}^{{2^N}-1}{\left| x \right\rangle }

On peut remarquer que cet état peut se décomposer en la somme (\left| t \right\rangle étant l'état cible recherché) :

\left| \Psi_0 \right\rangle = \frac{1}{\sqrt {2^N}} \left| t \right\rangle + \frac{1}{\sqrt {2^N}} \sum_\overset{x=0}{x \neq t}^{{2^N}-1}{\left| x \right\rangle } = \frac{1}{\sqrt {2^N}} \left| t \right\rangle + \frac{\sqrt{2^N-1}}{\sqrt {2^N}} \left| u \right\rangle

avec

\left| u \right\rangle = \frac{1}{\sqrt {2^N-1}} \sum_\overset{x=0}{x \neq t}^{{2^N}-1}{\left| x \right\rangle}

et où \left| t \right\rangle et \left| u \right\rangle sont des vecteurs normés à un. La figure ci-contre représente alors l'état \left | \Psi_0 \right\rangle = \cos{\theta} \left | u \right\rangle + \sin{\theta} \left | t \right \rangle dans cette base, où θ est l'angle entre \left| u \right\rangle et \left| \Psi_0 \right\rangle. D'après cette représentation, on obtient naturellement \sin \theta = \frac{1}{\sqrt {2^N}}.

On remarque aussi que, selon cette représentation, l'opérateur \hat O effectue une symétrie du vecteur par rapport à \left| u \right\rangle, puisque l'Oracle inverse uniquement la composante de \left| t \right\rangle.

Selon cette représentation, tout opérateur quantique va provoquer une rotation d'un vecteur représenté dans cette base (les opérateurs quantiques étant unitaires, l'image d'un vecteur par un opérateur sera toujours sur le cercle unité). Quel est l'angle de rotation que va faire subir l'opérateur de Grover \hat G vu plus haut, à un état quelconque \left| \sigma \right\rangle ?


Soit \left| \sigma_1 \right\rangle = \hat G \left| \sigma \right\rangle, et \left| \sigma ' \right\rangle = \hat O \left| \sigma \right\rangle. On a donc, d'après la formulation de \hat G vue plus haut :

\begin{align} \left| \sigma_1 \right\rangle & = \left( 2 \left| \Psi_0 \right\rangle \left\langle \Psi_0 \right| - \hat I \right) \hat O \left| \sigma \right\rangle && & = 2 \langle \Psi_0 | \hat O | \sigma \rangle \left| \Psi_0 \right\rangle - \hat O \left| \sigma \right\rangle && & = 2 \langle \Psi_0 | \sigma ' \rangle \left| \Psi_0 \right\rangle - \left| \sigma' \right\rangle && & = 2 \cos \alpha_2 \left| \Psi_0 \right\rangle - \left| \sigma' \right\rangle && \end{align}

Donc :

\begin{align} \langle \sigma | \sigma_1 \rangle & = 2 \cos \alpha_2 \langle \sigma | \Psi_0 \rangle - \langle \sigma | \sigma ' \rangle && & = 2 \cos (\alpha_2) \cos (\alpha_1) - \cos (\alpha_1 + \alpha_2) && & = \cos (\alpha_2 - \alpha_1) = \cos (2 \theta) \end{align}


Donc, l'opérateur \hat G effectue, dans cette représentation, une rotation d'angle 2θ, tel que \theta = \arcsin \frac{1}{\sqrt {2^N}}.


Muni de ce résultat, il suffit maintenant de calculer combien de rotations sont nécessaires pour passer de \left| u \right\rangle à \left| t \right\rangle, c'est-à-dire pour une rotation totale de \frac \pi 2.

On doit avoir :

\begin{align} \theta + 2 m \theta & \le \frac \pi 2 \Longrightarrow && \theta \left( 1 + 2 m \right) & \le \frac \pi 2 \Longrightarrow && \theta & \le \frac \pi {4 \theta} \end{align}


Pour des valeurs de N suffisamment grandes (ce qui est normalement le cas d'utilisation de l'algorithme de Grover..), on peut approximer

\theta \approx \sin \theta = \frac{1}{\sqrt {2^N}}

d'où :

m \approx \frac \pi 4 \sqrt {2^N}.

Bibliographie

  • Colin P. Wiliams Explorations in Quantum Computing Springer 2011 :
  1. ↑ Paragraphe 5.6 « Can Grover's Algorithm Be Beaten ? »
  2. ↑ Paragraphe 5.7.1 « Speeding Up Randomized Algorithms »
  3. ↑ Paragraphe 7.4 « Quantum Solution Using Nested Grover's Algorithm »
  4. ↑ Paragraphe 7.5 « Summary »
  5. ↑ Voir par exemple 5.4.1 « How Much Amplitude Amplification is Needed to Ensure Success ? »

Notes et références

  1. ↑ Grover L.K. : A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
  2. ↑ C Zalka Grover's Quantum Searching Algorithm is Optimal Phys. rev. A, Volume 60 Issue 4 (1999) pp. 2476-2751
  3. ↑ Se rappeler le Chat de Schrödinger
  4. ↑ C'est-à-dire que, si on mesure cet état, on a une chance égale de mesurer n'importe quel état de la superposition
  5. ↑ A. Carlini et A. Hosota Quantum Probabilistic Subroutines and Problems in Number Theory Phys. Rev. A, Volume 62 (2000)
  6. ↑ L.K Grover Synthesis of Quantum Superpositions by Quantum Computation Phys. Rev. Lett. Volume 85 Issue 6 (2000) pp. 1334-1337
  7. ↑ Voir Présentation de l'algorithme de Grover par le Pr. Raffaele Solca

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Grover de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Algorithme de Shor — En arithmétique modulaire, l’algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O((logN)3) et en espace O(logN), nommé en l honneur de Peter Shor. Beaucoup de cryptosystèmes à clé publique, tels que le RSA,… …   Wikipédia en Français

  • Grover — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Grover (label) Algorithme de Grover Grover est le nom de plusieurs lieux aux  États Unis Grover (Colorado) …   Wikipédia en Français

  • Algorithme de Deutsch-Jozsa — L Algorithme de Deutsch Jozsa est un algorithme quantique, proposé par David Deutsch et Richard Jozsa en 1992 avec des améliorations de R. Cleve, A. Ekert, C. Macchiavello, et M. Mosca en 1998[1],[2]. Bien qu il ne soit pas d un grand intérêt… …   Wikipédia en Français

  • Lov Grover — Lov Kumar Grover (né en 1961) est un informaticien indo américain. Il est à l origine de l algorithme quantique de recherche dans une base de donnée non hiérarchisée le plus efficace (Algorithme de Grover)[1]. Il a obtenu son diplôme de premier… …   Wikipédia en Français

  • Calcul quantique — Calculateur quantique Cet article fait partie de la série Mécanique quantique Postulats de la mécanique quantique Histoire de …   Wikipédia en Français

  • Calculateur quantique — La Sphère de Bloch est une représentation d’un qubit Un calculateur quantique ou ordinateur[1] quantique, repose sur des propriétés quantiques de la matière : superposition et intrication d éta …   Wikipédia en Français

  • Ordinateur quantique — Calculateur quantique Cet article fait partie de la série Mécanique quantique Postulats de la mécanique quantique Histoire de …   Wikipédia en Français

  • Informatique quantique — L informatique quantique est le sous domaine de l informatique qui traite des ordinateurs quantiques utilisant des phénomènes de la mécanique quantique, par opposition à ceux de l électricité exclusivement, pour l informatique dite… …   Wikipédia en Français

  • Informatique Quantique — L informatique quantique est le sous domaine de l informatique qui traite des ordinateurs quantiques utilisant des phénomènes de la mécanique quantique, par opposition à ceux de l électricité exclusivement, pour l informatique dite… …   Wikipédia en Français

  • Information quantique — La théorie de l information quantique, parfois abrégée simplement en information quantique, est un développement de la théorie de l information de Claude Shannon exploitant les propriétés de la mécanique quantique, notamment le principe de… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”