Analyse

Nous allons maintenant analyser l'algorithme de Grover pour comprendre comment il fonctionne. Nous commencerons par ce que l'on pourrait appeler une analyse symbolique, où nous calculons comment l'opération Grover $G$ agit sur certains états, puis nous relierons cette analyse symbolique à une image géométrique utile pour visualiser le fonctionnement de l'algorithme.

---

Solutions et non-solutions

Commençons par définir deux ensembles de chaînes.

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

L'ensemble $A_1$ contient toutes les solutions à notre problème de recherche, tandis que $A_0$ contient les chaînes qui ne sont pas des solutions (que nous pouvons appeler " non-solutions " lorsque c'est pratique). Ces deux ensembles satisfont $A_0 \cap A_1 = \varnothing$ et $A_0 \cup A_1 = \Sigma^n,$, ce qui revient à dire qu'il s'agit d'une bipartition de $\Sigma^n.$

Nous allons ensuite définir deux vecteurs unitaires représentant des superpositions uniformes sur les ensembles de solutions et de non-solutions.

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

Formellement, chacun de ces vecteurs n'est défini que lorsque l'ensemble correspondant est non vide, mais nous nous concentrerons ci-après sur le cas où ni $A_0$ ni $A_1$ ne sont vides. Les cas de $A_0 = \varnothing$ et $A_1 = \varnothing$ peuvent facilement être traités séparément, ce que nous ferons plus tard.

Soit dit en passant, la notation utilisée ici est courante : chaque fois que nous disposons d'un ensemble fini et non vide $S,$, nous pouvons écrire $\vert S\rangle$ pour désigner le vecteur d'état quantique qui est uniforme sur les éléments de $S.$

Définissons également $\vert u \rangle$ comme un état quantique uniforme sur toutes les chaînes de $n$ bits :

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

Notez que

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

Nous savons également que $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle,$ donc $\vert u\rangle$ représente l'état du registre $\mathsf{Q}$ après l'initialisation à l'étape 1 de l'algorithme de Grover.

Cela implique que juste avant les itérations de $G$ à l'étape 2, l'état de $\mathsf{Q}$ est contenu dans l'espace vectoriel bidimensionnel couvert par $\vert A_0\rangle$ et $\vert A_1\rangle,$ et que, de plus, les coefficients de ces vecteurs sont des nombres réels. Comme nous le verrons, l'état de $\mathsf{Q}$ aura toujours ces propriétés - ce qui signifie que l'état est une combinaison linéaire réelle de $\vert A_0\rangle$ et $\vert A_1\rangle$ - après un nombre quelconque d'itérations de l'opération $G$ à l'étape 2.

---

Une observation concernant l'opération Grover

Nous allons maintenant nous intéresser à l'opération Grover

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

en commençant par une observation intéressante à son sujet.

Imaginons un instant que nous remplacions la fonction $f$ par la composition de $f$ avec la fonction NOT - ou, en d'autres termes, la fonction que nous obtenons en retournant le bit de sortie de $f.$ Nous appellerons cette nouvelle fonction $g,$ et nous pouvons l'exprimer à l'aide de symboles de différentes manières.

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

Notez que

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

pour toute chaîne de caractères $x\in\Sigma^n,$ et donc

$$Z_g = - Z_f.$$

Cela signifie que si nous devions remplacer la fonction $f$ par la fonction $g,$, l'algorithme de Grover ne fonctionnerait pas différemment, car les états obtenus par l'algorithme dans les deux cas sont nécessairement équivalents jusqu'à une phase globale.

Ce n'est pas un problème! Intuitivement, l'algorithme ne se préoccupe pas de savoir quelles chaînes sont des solutions et quelles chaînes sont des non-solutions - il doit seulement être capable de distinguer les solutions et les non-solutions pour fonctionner correctement.

---

Action de l'opération Grover

Considérons maintenant l'action de $G$ sur les vecteurs d'états quantiques $\vert A_0\rangle$ et $\vert A_1\rangle.$

Observons tout d'abord que l'opération $Z_f$ a une action très simple sur $\vert A_0\rangle$ et sur $\vert A_1\rangle.$

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

Deuxièmement, nous avons l'opération $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ L'opération $Z_{\mathrm{OR}}$ est définie comme suit

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

pour chaque chaîne de caractères $x\in\Sigma^n,$ et une autre façon pratique d'exprimer cette opération est la suivante :

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

Un moyen simple de vérifier que cette expression est conforme à la définition de $Z_{\mathrm{OR}}$ est d'évaluer son action sur les états de base standard.

L'opération $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ peut donc s'écrire comme suit :

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

en utilisant la même notation, $\vert u \rangle,$, que celle que nous avons utilisée ci-dessus pour la superposition uniforme de toutes les chaînes de $n$ -bits.

Nous avons maintenant ce qu'il nous faut pour calculer l'action de $G$ sur $\vert A_0\rangle$ et $\vert A_1\rangle.$ Calculons d'abord l'action de $G$ sur $\vert A_0\rangle.$

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

Et deuxièmement, calculons l'action de $G$ sur $\vert A_1\rangle.$

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

Dans les deux cas, nous utilisons l'équation suivante

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

ainsi que les expressions

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{and}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

qui suivent.

En résumé, nous avons

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

Comme nous l'avons déjà noté, l'état de $\mathsf{Q}$ juste avant l'étape 2 est contenu dans l'espace bidimensionnel couvert par $\vert A_0\rangle$ et $\vert A_1\rangle,$ et nous venons d'établir que $G$ fait correspondre tout vecteur de cet espace à un autre vecteur du même espace. Cela signifie que, pour les besoins de l'analyse, nous pouvons concentrer notre attention exclusivement sur ce sous-espace.

Pour mieux comprendre ce qui se passe dans cet espace bidimensionnel, exprimons l'action de $G$ sur cet espace sous la forme d'une matrice,

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

dont les première et deuxième lignes/colonnes correspondent respectivement à $\vert A_0\rangle$ et $\vert A_1\rangle,$. Jusqu'à présent, dans cette série, nous avons toujours associé les lignes et les colonnes des matrices aux états classiques d'un système, mais les matrices peuvent également être utilisées pour décrire les actions des mappings linéaires sur différentes bases, comme c'est le cas ici.

Bien que cela ne soit pas du tout évident à première vue, la matrice $M$ est ce que nous obtenons en élevant au carré une matrice d'apparence plus simple.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

La matrice

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

est une matrice de rotation, que l'on peut également exprimer comme suit

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

pour

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

Cet angle $\theta$ va jouer un rôle très important dans l'analyse qui suit, et il convient donc de souligner son importance ici, alors que nous le voyons pour la première fois.

À la lumière de l'expression de cette matrice, on observe que

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

En effet, tourner deux fois autour de l'angle $\theta$ équivaut à tourner autour de l'angle $2\theta.$ Une autre façon de voir cela est d'utiliser l'expression alternative

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

ainsi que les formules d' angle double de la trigonométrie :

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

En résumé, l'état du registre $\mathsf{Q}$ au début de l'étape 2 est le suivant

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

et l'application de $G$ à cet état a pour effet de le faire pivoter d'un angle $2\theta$ dans l'espace couvert par $\vert A_0\rangle$ et $\vert A_1\rangle.$ Ainsi, par exemple, nous avons

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

et en général

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

---

Image géométrique

Relions maintenant l'analyse que nous venons de faire à une image géométrique. L'idée est que l'opération $G$ est le produit de deux réflexions, $Z_f$ et $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ Et l'effet net de ces deux réflexions est d'effectuer une rotation.

Commençons par $Z_f.$ Comme nous l'avons déjà observé précédemment, nous avons

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

Dans l'espace vectoriel à deux dimensions couvert par $\vert A_0\rangle$ et $\vert A_1\rangle,$ il s'agit d'une réflexion sur la ligne parallèle à $\vert A_0\rangle,$ que nous appellerons $L_1.$ Voici une figure illustrant l'action de cette réflexion sur un vecteur unitaire hypothétique $\vert\psi\rangle,$ que nous supposons être une combinaison linéaire réelle de $\vert A_0\rangle$ et de $\vert A_1\rangle.$

Deuxièmement, nous avons l'opération $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$ qui, comme nous l'avons déjà vu, peut s'écrire comme suit

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

Il s'agit également d'une réflexion, cette fois sur la ligne $L_2$ parallèle au vecteur $\vert u\rangle.$ Voici une figure illustrant l'action de cette réflexion sur un vecteur unitaire $\vert\psi\rangle.$

Lorsque l'on compose ces deux réflexions, on obtient une rotation - de deux fois l'angle entre les lignes de réflexion - comme l'illustre cette figure.

Cela explique, en termes géométriques, pourquoi l'opération Grover a pour effet de faire pivoter les combinaisons linéaires de $\vert A_0\rangle$ et $\vert A_1\rangle$ d'un angle de $2\theta.$