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.

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 à la recherche brute.

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

• le problème SAT ;
• la coloration de graphe ;
• la détermination d'un chemin hamiltonien dans un graphe ;
• des puzzles, cryptographiques comme « SEND+MORE=MONEY », ou numériques comme le sudoku.

Malgré tout, ce genre de problème est souvent de complexité exponentielle par rapport au nombre d'éléments du problème (typiquement, $N=2^{n}$ 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, il transforme un problème de complexité $2^{n}$ 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, 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.

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$. Cet état superposé est un vecteur, combinaison linéaire des deux états $\alpha \cdot \left|0\right\rangle +\beta \cdot \left|1\right\rangle$, $\alpha$ et $\beta$ étant deux scalaires complexes.

Un ensemble de $N$ qbits chacun dans un état superposé forme globalement une superposition de $2^{N}$ é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 $c_{1},c_{2},..$ En fait, lors d'une mesure de cet état intriqué, l'état va être projeté aléatoirement sur un et un seul état, vecteur propre de l'instrument de mesure caractérisé par son Observable $\left|000..00\right\rangle ,\left|000..01\right\rangle ,\left|000..10\right\rangle ,...,\left|111..11\right\rangle$, ce avec une probabilité respective de ${|c_{1}|}^{2},{|c_{2}|}^{2},...,{|c_{2^{N}}|}^{2}$.

Le calcul quantique va calculer simultanément $2^{N}$ résultats, et ceci de manière parfaitement déterministe car l'équation de Schrödinger, et donc l'évolution du vecteur d'état, est déterministe. Mais on ne peut avoir directement accès à tous les résultats, car l'observation ne donne accès qu'à une seule configuration, prise au hasard parmi toutes les configurations, en détruisant le reste de l'état quantique. Néanmoins, le calcul peut être réalisé de manière à donner à l'état intéressant une probabilité proche de 1 et le reste une probabilité négligeable, et mesurer ainsi avec certitude le résultat recherché. C'est exactement ce qui va se passer pour l'algorithme de Grover où une phase « d'amplification » cherche à rendre déterministe le résultat recherché.

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 des états de la superposition
   ($\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 l'état "cible" de la boite noire. Cette boîte noire 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 {2^{N}}})$ itérations. La sélection de l'état cible par la boite noire est instantané, en tout cas en $O(1)$, mais il est impossible de récupérer instantanément l'état cible sélectionné.

La boîte noire est définie mathématiquement par une fonction $f_{\mathrm {critere} }(x)$ qui identifie si un état « $x$ » vérifie un certain critère :

$f_{\mathrm {critere} }(x)={\begin{cases}1,&\mathrm {Si~x~v{\acute {e}}rifie~le~crit{\grave {e}}re} \\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 $\Psi _{0}$ équi-superposé 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=2^{3}$ é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

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.

Applications de l'algorithme de Grover

L'algorithme de recherche de Grover est très polyvalent : 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. 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.

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 un objet quantique dans un é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.

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. 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 $\alpha$ 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.

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}}=\left({\hat {H}}{\hat {Z}}{\hat {H}}\right){\hat {O}}$$

• ${\hat {O}}$ est l'Oracle ($U_{\omega }$ 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é).
• ${\hat {H}}{\hat {Z}}{\hat {H}}$ est appelé l'opérateur de diffusion de Grover.

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{aligned}{\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{aligned}}$

$\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{aligned}{\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{aligned}}$

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}}}$. Certaines 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}}$. 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.

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ù $\theta$ 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{aligned}\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{aligned}}$

Donc :

${\begin{aligned}\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{aligned}}$

Donc, l'opérateur ${\hat {G}}$ effectue, dans cette représentation, une rotation d'angle $2\theta$, 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{aligned}\theta +2m\theta &\leq {\frac {\pi }{2}}&&\Longrightarrow &&\theta \left(1+2m\right)\leq {\frac {\pi }{2}}&&\Longrightarrow &&m\leq {\frac {\pi }{4\theta }}-{\frac {1}{2}}\approx {\frac {\pi }{4\theta }}\end{aligned}}$.

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

$\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 :