Choisir le nombre d'itérations

Nous avons établi que le vecteur d'état du registre $\mathsf{Q}$ dans l'algorithme de Grover reste dans le sous-espace bidimensionnel engendré par $\vert A_0\rangle$ et $\vert A_1\rangle$ une fois l'étape d'initialisation effectuée.

L'objectif est de trouver un élément $x\in A_1,$ et cet objectif sera atteint si nous parvenons à obtenir l'état $\vert A_1\rangle$ — car si nous mesurons cet état, nous obtiendrons nécessairement un résultat de mesure $x\in A_1.$ Étant donné que l'état de $\mathsf{Q}$ après $t$ itérations à l'étape 2 est

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle,$$

nous devons choisir $t$ de sorte que

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

soit aussi proche de $1$ que possible en valeur absolue, afin de maximiser la probabilité d'obtenir $x\in A_1$ lors de la mesure. Pour tout angle $\theta \in (0,2\pi),$ la valeur $\sin((2t + 1)\theta)$ oscille à mesure que $t$ augmente, bien qu'elle ne soit pas nécessairement périodique — rien ne garantit que nous obtiendrons jamais deux fois la même valeur.

Naturellement, en plus de rendre grande la probabilité d'obtenir un élément $x\in A_1$ lors de la mesure, nous souhaitons également choisir $t$ aussi petit que possible, car $t$ applications de l'opération $G$ nécessitent $t$ requêtes à la fonction $f.$ Comme nous cherchons à rendre $\sin( (2t + 1) \theta)$ proche de $1$ en valeur absolue, une façon naturelle d'y parvenir est de choisir $t$ de sorte que

$$(2t + 1) \theta \approx \frac{\pi}{2}.$$

En résolvant pour $t,$ on obtient

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

Bien sûr, $t$ doit être un entier, donc nous ne pourrons pas nécessairement atteindre exactement cette valeur — mais ce que nous pouvons faire, c'est prendre l'entier le plus proche de cette valeur, qui est

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

C'est le nombre d'itérations recommandé pour l'algorithme de Grover. En poursuivant l'analyse, nous verrons que la proximité de cet entier avec la valeur cible affecte naturellement les performances de l'algorithme.

(Incidemment, si la valeur cible $\pi/(4\theta) - 1/2$ se trouve exactement à mi-chemin entre deux entiers, cette expression de $t$ correspond à l'arrondi vers le haut. On pourrait alternativement arrondir vers le bas, ce qui est raisonnable car cela signifie une requête de moins — mais c'est secondaire et sans importance pour les besoins de cette leçon.)

En rappelant que la valeur de l'angle $\theta$ est donnée par la formule

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr),$$

nous constatons que le nombre d'itérations recommandé $t$ dépend du nombre de chaînes dans $A_1.$ Cela pose un problème si nous ne savons pas combien de solutions nous avons, comme nous le verrons plus tard.

Recherche unique

Commençons par nous concentrer sur la situation où il existe une seule chaîne $x$ telle que $f(x)=1.$ Une autre façon de le dire est que nous considérons une instance du problème de recherche unique. Dans ce cas, nous avons

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr),$$

ce qui peut être approximé de façon pratique par

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr) \approx \sqrt{\frac{1}{N}}$$

lorsque $N$ est grand. Si nous substituons $\theta = 1/\sqrt{N}$ dans l'expression

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

nous obtenons

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

En rappelant que $t$ est non seulement le nombre de fois où l'opération $G$ est effectuée, mais aussi le nombre de requêtes à la fonction $f$ requises par l'algorithme, nous voyons que nous sommes en bonne voie pour obtenir un algorithme nécessitant $O(\sqrt{N})$ requêtes.

Voyons maintenant dans quelle mesure le choix recommandé de $t$ fonctionne bien. La probabilité que la mesure finale donne la solution unique peut être exprimée explicitement comme

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

Le premier argument, $N,$ désigne le nombre d'éléments sur lesquels nous effectuons la recherche, et le second argument, qui est $1$ dans ce cas, désigne le nombre de solutions. Un peu plus tard, nous utiliserons la même notation de manière plus générale, lorsqu'il y a plusieurs solutions.

Voici un tableau des probabilités de succès pour des valeurs croissantes de $N = 2^n.$

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

Remarquons que ces probabilités ne sont pas strictement croissantes. En particulier, nous observons une anomalie intéressante pour $N=4,$ où nous obtenons une solution avec certitude. Il peut cependant être prouvé en général que

$$p(N,1) \geq 1 - \frac{1}{N}$$

pour tout $N,$ de sorte que la probabilité de succès tend vers $1$ à la limite quand $N$ devient grand, comme les valeurs ci-dessus semblent le suggérer. C'est une bonne nouvelle !

Mais remarque cependant que même une borne aussi faible que $p(N,1) \geq 1/2$ établit l'utilité de l'algorithme de Grover. Quel que soit le résultat de mesure $x$ que nous obtenons en exécutant la procédure, nous pouvons toujours vérifier si $f(x) = 1$ avec une seule requête à $f.$ Et si nous échouons à obtenir la chaîne unique $x$ pour laquelle $f(x) = 1$ avec une probabilité d'au plus $1/2$ en exécutant la procédure une fois, alors après $m$ exécutions indépendantes de la procédure, nous aurons échoué à obtenir cette chaîne unique $x$ avec une probabilité d'au plus $2^{-m}.$ C'est-à-dire qu'en utilisant $O(m \sqrt{N})$ requêtes à $f,$ nous obtiendrons la solution unique $x$ avec une probabilité d'au moins $1 - 2^{-m}.$ En utilisant la meilleure borne $p(N,1) \geq 1 - 1/N,$ on constate que la probabilité de trouver $x\in A_1$ par cette méthode est en réalité d'au moins $1 - N^{-m}.$

Solutions multiples

À mesure que le nombre d'éléments dans $A_1$ varie, l'angle $\theta$ varie aussi, ce qui peut avoir un effet significatif sur la probabilité de succès de l'algorithme. Par souci de concision, écrivons $s = \vert A_1 \vert$ pour désigner le nombre de solutions, et comme précédemment nous supposerons que $s\geq 1.$

Comme exemple motivant, imaginons que nous ayons $s = 4$ solutions plutôt qu'une seule, comme nous l'avons considéré ci-dessus. Cela signifie que

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

ce qui est approximativement le double de l'angle que nous avions dans le cas $\vert A_1 \vert = 1$ lorsque $N$ est grand. Supposons que nous n'en sachions pas davantage et que nous sélectionnions la même valeur de $t$ que dans le cadre de la solution unique :

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

L'effet sera catastrophique, comme le révèle le tableau de probabilités suivant.

$$\begin{array}{ll} N & \text{Success probability}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

Cette fois, la probabilité de succès tend vers $0$ lorsque $N$ tend vers l'infini. Cela se produit parce que nous effectuons effectivement une rotation deux fois plus rapide que lorsqu'il y avait une solution unique, ce qui nous fait dépasser la cible $\vert A_1\rangle$ et atterrir près de $-\vert A_0\rangle.$

Cependant, si nous utilisons plutôt le choix recommandé de $t,$ qui est

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

pour

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

alors les performances seront meilleures. Plus précisément, l'utilisation de ce choix de $t$ conduit à un succès avec une haute probabilité.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

En généralisant ce qui a été affirmé précédemment, il peut être prouvé que

$$p(N,s) \geq 1 - \frac{s}{N},$$

où nous utilisons la notation suggérée précédemment : $p(N,s)$ désigne la probabilité que l'algorithme de Grover exécuté pendant $t$ itérations révèle une solution lorsqu'il y a $s$ solutions au total parmi $N$ possibilités.

Cette borne inférieure de $1 - s/N$ sur la probabilité de succès est légèrement particulière en ce sens que plus il y a de solutions, plus la borne inférieure est mauvaise — mais sous l'hypothèse que $s$ est nettement plus petit que $N,$ nous concluons néanmoins que la probabilité de succès est raisonnablement élevée. Comme précédemment, le simple fait que $p(N,s)$ soit raisonnablement grand implique l'utilité de l'algorithme.

Il se trouve également que

$$p(N,s) \geq \frac{s}{N}.$$

Cette borne inférieure décrit la probabilité qu'une chaîne $x\in\Sigma^n$ choisie uniformément au hasard soit une solution — ainsi, l'algorithme de Grover fait toujours au moins aussi bien qu'une supposition aléatoire. (En fait, lorsque $t=0,$ l'algorithme de Grover est une supposition aléatoire.)

Examinons maintenant le nombre d'itérations (et donc le nombre de requêtes)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

pour

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{s}{N}}\biggr).$$

Pour tout $\alpha \in [0,1],$ il est vrai que $\sin^{-1}(\alpha)\geq \alpha,$ et donc

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

Cela implique que

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

Cela se traduit par une économie du nombre de requêtes à mesure que $s$ augmente. En particulier, le nombre de requêtes nécessaires est

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

Nombre de solutions inconnu

Si le nombre de solutions $s = \vert A_1 \vert$ est inconnu, alors une approche différente est nécessaire, car dans cette situation nous n'avons aucune connaissance de $s$ pour guider notre choix de $t.$ Il existe en fait plusieurs approches.

Une approche simple consiste à choisir

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

uniformément au hasard. Sélectionner $t$ de cette façon trouve toujours une solution (en supposant qu'il en existe une) avec une probabilité supérieure à 40 %, bien que cela ne soit pas évident et nécessite une analyse qui ne sera pas présentée ici. Cela a du sens, cependant, surtout lorsque nous pensons à l'image géométrique : faire tourner l'état de $\mathsf{Q}$ un nombre aléatoire de fois de cette manière n'est pas sans rappeler le choix d'un vecteur unitaire aléatoire dans l'espace engendré par $\vert A_0\rangle$ et $\vert A_1\rangle,$ pour lequel il est probable que le coefficient de $\vert A_1\rangle$ soit raisonnablement grand. En répétant cette procédure et en vérifiant le résultat de la même façon que décrite précédemment, la probabilité de trouver une solution peut être rendue très proche de $1.$

Il existe une méthode plus raffinée qui trouve une solution lorsqu'il en existe une en utilisant $O(\sqrt{N/s})$ requêtes, même lorsque le nombre de solutions $s$ est inconnu, et qui nécessite $O(\sqrt{N})$ requêtes pour déterminer qu'il n'y a pas de solutions lorsque $s=0.$

L'idée de base est de choisir $t$ uniformément au hasard dans l'ensemble $\{1,\ldots,T\}$ de manière itérative, pour des valeurs croissantes de $T.$ En particulier, nous pouvons commencer avec $T = 1$ et l'augmenter de façon exponentielle, en terminant toujours le processus dès qu'une solution est trouvée et en limitant $T$ de façon à ne pas gaspiller des requêtes lorsqu'il n'y a pas de solution. Le processus tire parti du fait que moins de requêtes sont nécessaires lorsqu'il y a plus de solutions. Une certaine attention est cependant requise pour équilibrer le taux de croissance de $T$ avec la probabilité de succès à chaque itération. (Prendre $T \leftarrow \lceil \frac{5}{4}T\rceil$ fonctionne, par exemple, comme le révèle une analyse. Doubler $T,$ en revanche, ne fonctionne pas — cela s'avère être une augmentation trop rapide.)

Les cas triviaux

Tout au long de l'analyse que nous venons d'effectuer, nous avons supposé que le nombre de solutions est non nul. En effet, en faisant référence aux vecteurs

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

nous avons implicitement supposé que $A_0$ et $A_1$ sont tous les deux non vides. Nous allons ici brièvement examiner ce qui se passe lorsque l'un de ces ensembles est vide.

Avant de nous lancer dans une analyse, observons l'évidence : si chaque chaîne $x\in\Sigma^n$ est une solution, nous verrons une solution lors de la mesure ; et lorsqu'il n'y a aucune solution, nous n'en verrons pas. En un certain sens, il n'est pas nécessaire d'aller plus loin que cela.

Nous pouvons cependant vérifier rapidement les mathématiques pour ces cas triviaux. La situation où l'un de $A_0$ et $A_1$ est vide se produit quand $f$ est constante ; $A_1$ est vide quand $f(x) = 0$ pour tout $x\in\Sigma^n,$ et $A_0$ est vide quand $f(x) = 1$ pour tout $x\in\Sigma^n.$ Cela signifie que

$$Z_f \vert u\rangle = \pm \vert u\rangle,$$

et par conséquent

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

Ainsi, quel que soit le nombre d'itérations $t$ que nous effectuons dans ces cas, les mesures révèleront toujours une chaîne $x\in\Sigma^n$ aléatoire uniforme.