Analyse

Nous allons maintenant analyser l'algorithme de Grover pour comprendre son fonctionnement. Nous commencerons par ce qu'on pourrait appeler une analyse symbolique, où nous calculons comment l'opération de Grover $G$ agit sur certains états, puis nous relierons cette analyse symbolique à une représentation géométrique qui aide à 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 (qu'on peut appeler non-solutions quand c'est pratique). Ces deux ensembles vérifient $A_0 \cap A_1 = \varnothing$ et $A_0 \cup A_1 = \Sigma^n,$ c'est-à-dire qu'il s'agit d'une bipartition de $\Sigma^n.$

Ensuite, nous allons 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 allons désormais nous concentrer sur le cas où ni $A_0$ ni $A_1$ n'est vide. Les cas $A_0 = \varnothing$ et $A_1 = \varnothing$ se traitent facilement séparément, et nous le ferons plus tard.

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

Définissons également $\vert u \rangle$ comme l'é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.$$

Remarque :

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

On a aussi $\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 engendré par $\vert A_0\rangle$ et $\vert A_1\rangle,$ et 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 — c'est-à-dire que l'état est une combinaison linéaire réelle de $\vert A_0\rangle$ et $\vert A_1\rangle$ — après n'importe quel nombre d'itérations de l'opération $G$ à l'étape 2.

Une observation sur l'opération de Grover

Intéressons-nous maintenant à l'opération de Grover

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

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

Imagine un instant que nous remplaçions la fonction $f$ par la composition de $f$ avec la fonction NOT — autrement dit, la fonction obtenue en inversant le bit de sortie de $f.$ Appelons cette nouvelle fonction $g$ ; on peut l'exprimer de plusieurs manières équivalentes.

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

Remarque :

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

pour toute chaîne $x\in\Sigma^n,$ et donc

$$Z_g = - Z_f.$$

Cela signifie que si on substituait 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 à une phase globale près.

Ce n'est pas un problème ! Intuitivement, l'algorithme n'a pas à savoir quelles chaînes sont des solutions et lesquelles sont des non-solutions — il lui suffit de pouvoir distinguer solutions et non-solutions pour fonctionner correctement.

Action de l'opération de Grover

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

D'abord, observons que l'opération $Z_f$ a une action très simple sur $\vert A_0\rangle$ et $\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}$$

Ensuite, considérons l'opération $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ L'opération $Z_{\mathrm{OR}}$ est définie par

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

de nouveau pour toute chaîne $x\in\Sigma^n,$ et une façon alternative commode d'exprimer cette opération est la suivante :

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

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

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

$$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 utilisée plus haut pour la superposition uniforme sur toutes les chaînes de $n$ bits.

Nous avons maintenant tout ce qu'il 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}$$

Puis 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

$$\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{et}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

qui en découlent.

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 engendré par $\vert A_0\rangle$ et $\vert A_1\rangle,$ et nous venons d'établir que $G$ envoie tout vecteur de cet espace sur 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 forme de 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'ici dans cette série, nous avons toujours associé les lignes et colonnes des matrices aux états classiques d'un système, mais les matrices peuvent aussi servir à décrire l'action de transformations linéaires sur différentes bases, comme c'est le cas ici.

Bien que ce ne soit pas du tout évident au premier coup d'œil, la matrice $M$ est ce qu'on obtient 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, qu'on peut également écrire sous la forme

$$\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, aussi vaut-il la peine d'insister sur son importance dès sa première apparition.

À la lumière de cette expression, nous observons 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}.$$

C'est parce qu'effectuer deux rotations d'angle $\theta$ revient à effectuer une rotation d'angle $2\theta.$ Une autre façon de le voir est d'utiliser l'expression alternative

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

avec les formules de duplication issues 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

$$\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'effet de l'application de $G$ à cet état est de le faire tourner d'un angle $2\theta$ dans l'espace engendré par $\vert A_0\rangle$ et $\vert A_1\rangle.$ Ainsi, par exemple :

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

Représentation géométrique

Relions maintenant l'analyse que nous venons de mener à une représentation 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 deux réflexions est d'effectuer une rotation.

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

$$\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 bidimensionnel engendré par $\vert A_0\rangle$ et $\vert A_1\rangle,$ il s'agit d'une réflexion par rapport à la droite 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 $\vert A_1\rangle.$

Ensuite, nous avons l'opération $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$ dont nous avons déjà vu qu'elle peut s'écrire

$$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 par rapport à la droite $L_2$ parallèle au vecteur $\vert u\rangle.$ Voici une figure représentant l'action de cette réflexion sur un vecteur unitaire $\vert\psi\rangle.$

Lorsque nous composons ces deux réflexions, nous obtenons une rotation — d'un angle égal au double de l'angle entre les axes de réflexion — comme l'illustre cette figure.

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