Algorithme de Grover

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

${\displaystyle N}$ qbits peuvent être intriqués de manière à former une superposition de ${\displaystyle 2^{N}}$ états : ${\displaystyle 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 ${\displaystyle \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 ${\displaystyle c_{1},c_{2},..}$ En fait, lors d'une mesure de cet état intriqué, l'état va se retrouver aléatoirement dans un et un seul état ${\displaystyle \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 ${\displaystyle {|c_{1}|}^{2},{|c_{2}|}^{2},...,{|c_{2^{N}}|}^{2}}$.

Le calcul quantique va calculer simultanément ${\displaystyle 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é.

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
   (${\displaystyle \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 ${\displaystyle O({\sqrt {2^{N}}})}$ itérations. La sélection de l'état cible par la boite noire est instantané, en tout cas en ${\displaystyle 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 ${\displaystyle f_{\mathrm {critere} }(x)}$ qui identifie si un état « ${\displaystyle x}$ » vérifie un certain critère :

${\displaystyle 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 ${\displaystyle \Psi _{0}}$ équi-superposé[4] de tous les états possibles de ${\displaystyle N}$ qbits :

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

$${\displaystyle \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 ${\displaystyle \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 ${\displaystyle N=3}$ qbits, ce qui donne ${\displaystyle 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, ${\displaystyle {\frac {\pi }{4}}{\sqrt {8}}\approx 2}$ fois, pour obtenir l'état final

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

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 ${\displaystyle 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) à ${\displaystyle {\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 ${\displaystyle {\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].

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[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 ${\displaystyle {\sqrt {N}}}$ étapes seulement[6].

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[7].

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 ${\displaystyle O\left(b^{\frac {\mu }{2}}\right)}$ (contre ${\displaystyle O\left(b^{\mu }\right)}$ pour un algorithme classique), il est possible d'obtenir une complexité de ${\displaystyle O\left(b^{\alpha {\frac {\mu }{2}}}\right)}$ (avec ${\displaystyle \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[Williams 4].

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 :

$${\displaystyle {\hat {G}}=\left({\hat {H}}{\hat {Z}}{\hat {H}}\right){\hat {O}}}$$

• ${\displaystyle {\hat {O}}}$ est l'Oracle (${\displaystyle U_{\omega }}$ sur la figure ci-contre).
• ${\displaystyle {\hat {H}}}$ est l'opérateur (ou transformation) de Hadamard, qui est un opérateur de base en calcul quantique. Il est tel que ${\displaystyle {\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.
• ${\displaystyle {\hat {Z}}}$ est l'opérateur « Zero phase shift » défini comme ${\displaystyle {\hat {Z}}=2\left|0\right\rangle \left\langle 0\right|-{\hat {I}}}$ (${\displaystyle {\hat {I}}}$ étant l'opérateur identité).
• ${\displaystyle {\hat {H}}{\hat {Z}}{\hat {H}}}$ est appelé l'opérateur de diffusion de Grover.

C'est ${\displaystyle {\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 :

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

${\displaystyle \Psi _{0}={\hat {H}}\left|0\right\rangle }$ est l'état équi-superposé initial.

En appliquant cet opérateur ${\displaystyle {\hat {M}}={\hat {H}}{\hat {Z}}{\hat {H}}}$ à un état quelconque ${\displaystyle \left|\Psi \right\rangle =\sum _{k}c_{k}\left|k\right\rangle }$ :

${\displaystyle {\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 ${\displaystyle c_{k}\Rightarrow 2{\bar {c}}-c_{k}}$ ce qui constitue en effet un miroir de l'amplitude autour de la moyenne des amplitudes.

Il existe plusieurs démonstrations du nombre optimal d'itérations ${\displaystyle 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 ${\displaystyle {\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 ${\displaystyle {\frac {1}{\sqrt {2^{N}}}}}$.

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

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

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

${\displaystyle \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 (${\displaystyle \left|t\right\rangle }$ étant l'état cible recherché) :

${\displaystyle \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

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

On remarque aussi que, selon cette représentation, l'opérateur ${\displaystyle {\hat {O}}}$ effectue une symétrie du vecteur par rapport à ${\displaystyle \left|u\right\rangle }$, puisque l'Oracle inverse uniquement la composante de ${\displaystyle \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 ${\displaystyle {\hat {G}}}$ vu plus haut, à un état quelconque ${\displaystyle \left|\sigma \right\rangle }$ ?

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

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

${\displaystyle {\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 ${\displaystyle {\hat {G}}}$ effectue, dans cette représentation, une rotation d'angle ${\displaystyle 2\theta }$, tel que ${\displaystyle \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 ${\displaystyle \left|u\right\rangle }$ à ${\displaystyle \left|t\right\rangle }$, c'est-à-dire pour une rotation totale de ${\displaystyle {\frac {\pi }{2}}}$.

On doit avoir :

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

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

d'où :

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