Description de l'algorithme de Grover

Dans cette section, nous allons décrire l'algorithme de Grover. Nous commencerons par présenter les portes de requête de phase et la façon de les construire, puis nous décrirons l'algorithme de Grover lui-même. Enfin, nous discuterons brièvement de la façon dont cet algorithme s'applique naturellement à la recherche.

Portes de requête de phase

L'algorithme de Grover utilise des opérations connues sous le nom de portes de requête de phase. Contrairement à une porte de requête ordinaire $U_f$, définie pour une fonction donnée $f$ de la manière habituelle décrite précédemment, une porte de requête de phase pour la fonction $f$ est définie comme

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

pour toute chaîne $x\in\Sigma^n$.

L'opération $Z_f$ peut être implémentée en utilisant une porte de requête $U_f$ comme le suggère ce diagramme :

Cette implémentation utilise le phénomène de rétroaction de phase, et nécessite qu'un qubit d'espace de travail, initialisé dans l'état $\vert -\rangle,$ soit disponible. Ce qubit reste dans l'état $\vert - \rangle$ après la fin de l'implémentation, et peut être réutilisé (pour implémenter des portes $Z_f$ ultérieures, par exemple) ou simplement écarté.

En plus de l'opération $Z_f$, nous utiliserons également une porte de requête de phase pour la fonction OU à $n$ bits, qui est définie comme suit pour chaque chaîne $x\in\Sigma^n$.

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

Explicitement, la porte de requête de phase pour la fonction OU à $n$ bits opère comme suit :

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}$$

Pour être clair, c'est ainsi que $Z_{\mathrm{OR}}$ opère sur les états de base standard ; son comportement sur des états arbitraires est déterminé à partir de cette expression par linéarité.

L'opération $Z_{\mathrm{OR}}$ peut être implémentée comme un circuit quantique en commençant par un circuit booléen pour la fonction OU, puis en construisant une opération $U_{\mathrm{OR}}$ (c'est-à-dire une porte de requête standard pour la fonction OU à $n$ bits) en utilisant la procédure décrite dans la leçon Fondements algorithmiques quantiques, et enfin une opération $Z_{\mathrm{OR}}$ en utilisant le phénomène de rétroaction de phase comme décrit ci-dessus. Remarque que l'opération $Z_{\mathrm{OR}}$ ne dépend pas de la fonction $f$ et peut donc être implémentée par un circuit quantique sans portes de requête.

Description de l'algorithme

Maintenant que nous disposons des deux opérations $Z_f$ et $Z_{\mathrm{OR}}$, nous pouvons décrire l'algorithme de Grover.

L'algorithme fait référence à un nombre $t$, qui est le nombre d'itérations qu'il effectue (et donc le nombre de requêtes à la fonction $f$ qu'il nécessite). Ce nombre $t$ n'est pas spécifié par l'algorithme de Grover tel que nous le décrivons, et nous discuterons plus loin dans la leçon comment il peut être choisi.

Algorithme de Grover

1. Initialiser un registre de $n$ qubits $\mathsf{Q}$ dans l'état tout-zéro $\vert 0^n \rangle$ puis appliquer une opération de Hadamard à chaque qubit de $\mathsf{Q}$.
2. Appliquer $t$ fois l'opération unitaire $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ au registre $\mathsf{Q}$
3. Mesurer les qubits de $\mathsf{Q}$ dans la base standard et retourner la chaîne résultante.

L'opération $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ itérée à l'étape 2 sera appelée l'opération de Grover dans la suite de cette leçon. Voici une représentation en circuit quantique de l'opération de Grover lorsque $n=7\!:$

Dans ce diagramme, l'opération $Z_f$ est représentée comme étant plus grande que $Z_{\mathrm{OR}}$ comme indicateur visuel informel suggérant qu'elle est probablement l'opération la plus coûteuse. En particulier, lorsque nous travaillons dans le modèle de requêtes, $Z_f$ nécessite une requête tandis que $Z_{\mathrm{OR}}$ n'en nécessite aucune. Si au lieu de cela nous disposons d'un circuit booléen pour la fonction $f,$ puis le convertissons en un circuit quantique pour $Z_f,$ on peut raisonnablement s'attendre à ce que le circuit quantique résultant soit plus grand et plus complexe que celui pour $Z_{\mathrm{OR}}.$

Voici un diagramme d'un circuit quantique pour l'algorithme entier lorsque $n=7$ et $t=3$. Pour des valeurs plus grandes de $t$, il suffit d'insérer des instances supplémentaires de l'opération de Grover immédiatement avant les mesures.

Application à la recherche

L'algorithme de Grover peut être appliqué au problème de Recherche comme suit :

• Choisir le nombre $t$ à l'étape 2. (Cela est discuté plus loin dans la leçon.)

• Exécuter l'algorithme de Grover sur la fonction $f$, en utilisant le choix que nous avons fait pour $t$, pour obtenir une chaîne $x\in\Sigma^n$.

• Interroger la fonction $f$ sur la chaîne $x$ pour voir si c'est une solution valide :

  • Si $f(x) = 1$, alors nous avons trouvé une solution, nous pouvons donc nous arrêter et retourner $x$.

  • Sinon, si $f(x) = 0$, nous pouvons soit relancer la procédure, éventuellement avec un choix différent pour $t$, soit décider d'abandonner et retourner « aucune solution ».

Une fois que nous aurons analysé le fonctionnement de l'algorithme de Grover, nous verrons qu'en prenant $t = O(\sqrt{N})$, on obtient une solution à notre problème de recherche (si elle existe) avec une forte probabilité.