Aller au contenu principal

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

A0={x∈Σn:f(x)=0}A1={x∈Σn:f(x)=1}\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 A1A_1 contient toutes les solutions à notre problème de recherche, tandis que A0A_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 A0∩A1=∅A_0 \cap A_1 = \varnothing et A0∪A1=Σn,A_0 \cup A_1 = \Sigma^n, c'est-à-dire qu'il s'agit d'une bipartition de Σn.\Sigma^n.

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

∣A0⟩=1∣A0∣∑x∈A0∣x⟩∣A1⟩=1∣A1∣∑x∈A1∣x⟩\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 A0A_0 ni A1A_1 n'est vide. Les cas A0=∅A_0 = \varnothing et A1=∅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,S, on peut écrire ∣S⟩\vert S\rangle pour désigner le vecteur d'état quantique uniforme sur les éléments de S.S.

Définissons également ∣u⟩\vert u \rangle comme l'état quantique uniforme sur toutes les chaînes de nn bits :

∣u⟩=1N∑x∈Σn∣x⟩.\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.

Remarque :

∣u⟩=∣A0∣N∣A0⟩+∣A1∣N∣A1⟩.\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 ∣u⟩=H⊗n∣0n⟩,\vert u\rangle = H^{\otimes n} \vert 0^n \rangle, donc ∣u⟩\vert u\rangle représente l'état du registre Q\mathsf{Q} après l'initialisation à l'étape 1 de l'algorithme de Grover.

Cela implique que juste avant les itérations de GG à l'étape 2, l'état de Q\mathsf{Q} est contenu dans l'espace vectoriel bidimensionnel engendré par ∣A0⟩\vert A_0\rangle et ∣A1⟩,\vert A_1\rangle, et de plus les coefficients de ces vecteurs sont des nombres réels. Comme nous le verrons, l'état de Q\mathsf{Q} aura toujours ces propriétés — c'est-à-dire que l'état est une combinaison linéaire réelle de ∣A0⟩\vert A_0\rangle et ∣A1⟩\vert A_1\rangle — après n'importe quel nombre d'itérations de l'opération GG à l'étape 2.

Une observation sur l'opération de Grover​

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

G=H⊗nZORH⊗nZf,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 ff par la composition de ff avec la fonction NOT — autrement dit, la fonction obtenue en inversant le bit de sortie de f.f. Appelons cette nouvelle fonction gg ; on peut l'exprimer de plusieurs manières équivalentes.

g(x)=¬f(x)=1⊕f(x)=1−f(x)={1f(x)=00f(x)=1g(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⊕f(x)=−(−1)f(x)(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}

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

Zg=−Zf.Z_g = - Z_f.

Cela signifie que si on substituait la fonction ff par la fonction g,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 GG sur les vecteurs d'état quantique ∣A0⟩\vert A_0\rangle et ∣A1⟩.\vert A_1\rangle.

D'abord, observons que l'opération ZfZ_f a une action très simple sur ∣A0⟩\vert A_0\rangle et ∣A1⟩.\vert A_1\rangle.

Zf∣A0⟩=∣A0⟩Zf∣A1⟩=−∣A1⟩\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⊗nZORH⊗n.H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}. L'opération ZORZ_{\mathrm{OR}} est définie par

ZOR∣x⟩={∣x⟩x=0n−∣x⟩x≠0n,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∈Σn,x\in\Sigma^n, et une façon alternative commode d'exprimer cette opération est la suivante :

ZOR=2∣0n⟩⟨0n∣−I.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 ZORZ_{\mathrm{OR}} est d'évaluer son action sur les états de la base standard.

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

H⊗nZORH⊗n=2H⊗n∣0n⟩⟨0n∣H⊗n−I=2∣u⟩⟨u∣−I,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, ∣u⟩,\vert u \rangle, que celle utilisée plus haut pour la superposition uniforme sur toutes les chaînes de nn bits.

Nous avons maintenant tout ce qu'il faut pour calculer l'action de GG sur ∣A0⟩\vert A_0\rangle et ∣A1⟩.\vert A_1\rangle. Calculons d'abord l'action de GG sur ∣A0⟩.\vert A_0\rangle.

G∣A0⟩=(2∣u⟩⟨u∣−I)Zf∣A0⟩=(2∣u⟩⟨u∣−I)∣A0⟩=2∣A0∣N∣u⟩−∣A0⟩=2∣A0∣N(∣A0∣N∣A0⟩+∣A1∣N∣A1⟩)−∣A0⟩=(2∣A0∣N−1)∣A0⟩+2∣A0∣⋅∣A1∣N∣A1⟩=∣A0∣−∣A1∣N∣A0⟩+2∣A0∣⋅∣A1∣N∣A1⟩\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 GG sur ∣A1⟩.\vert A_1\rangle.

G∣A1⟩=(2∣u⟩⟨u∣−I)Zf∣A1⟩=−(2∣u⟩⟨u∣−I)∣A1⟩=−2∣A1∣N∣u⟩+∣A1⟩=−2∣A1∣N(∣A0∣N∣A0⟩+∣A1∣N∣A1⟩)+∣A1⟩=−2∣A1∣⋅∣A0∣N∣A0⟩+(1−2∣A1∣N)∣A1⟩=−2∣A1∣⋅∣A0∣N∣A0⟩+∣A0∣−∣A1∣N∣A1⟩\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

∣u⟩=∣A0∣N∣A0⟩+∣A1∣N∣A1⟩\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

⟨u∣A0⟩=∣A0∣Net⟨u∣A1⟩=∣A1∣N\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

G∣A0⟩=∣A0∣−∣A1∣N∣A0⟩+2∣A0∣⋅∣A1∣N∣A1⟩G∣A1⟩=−2∣A1∣⋅∣A0∣N∣A0⟩+∣A0∣−∣A1∣N∣A1⟩.\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 Q\mathsf{Q} juste avant l'étape 2 est contenu dans l'espace bidimensionnel engendré par ∣A0⟩\vert A_0\rangle et ∣A1⟩,\vert A_1\rangle, et nous venons d'établir que GG 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 GG sur cet espace sous forme de matrice,

M=(∣A0∣−∣A1∣N−2∣A1∣⋅∣A0∣N2∣A0∣⋅∣A1∣N∣A0∣−∣A1∣N),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 à ∣A0⟩\vert A_0\rangle et ∣A1⟩.\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 MM est ce qu'on obtient en élevant au carré une matrice d'apparence plus simple.

(∣A0∣N−∣A1∣N∣A1∣N∣A0∣N)2=(∣A0∣−∣A1∣N−2∣A1∣⋅∣A0∣N2∣A0∣⋅∣A1∣N∣A0∣−∣A1∣N)=M\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

(∣A0∣N−∣A1∣N∣A1∣N∣A0∣N)\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

(∣A0∣N−∣A1∣N∣A1∣N∣A0∣N)=(cos⁡(θ)−sin⁡(θ)sin⁡(θ)cos⁡(θ))\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

θ=sin⁡−1(∣A1∣N).\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=(cos⁡(θ)−sin⁡(θ)sin⁡(θ)cos⁡(θ))2=(cos⁡(2θ)−sin⁡(2θ)sin⁡(2θ)cos⁡(2θ)).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θ.2\theta. Une autre façon de le voir est d'utiliser l'expression alternative

θ=cos⁡−1(∣A0∣N),\theta = \cos^{-1}\biggl(\sqrt{\frac{\vert A_0\vert}{N}}\biggr),

avec les formules de duplication issues de la trigonométrie :

cos⁡(2θ)=cos⁡2(θ)−sin⁡2(θ)sin⁡(2θ)=2sin⁡(θ)cos⁡(θ).\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 Q\mathsf{Q} au début de l'étape 2 est

∣u⟩=∣A0∣N∣A0⟩+∣A1∣N∣A1⟩=cos⁡(θ)∣A0⟩+sin⁡(θ)∣A1⟩,\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 GG à cet état est de le faire tourner d'un angle 2θ2\theta dans l'espace engendré par ∣A0⟩\vert A_0\rangle et ∣A1⟩.\vert A_1\rangle. Ainsi, par exemple :

G∣u⟩=cos⁡(3θ)∣A0⟩+sin⁡(3θ)∣A1⟩G2∣u⟩=cos⁡(5θ)∣A0⟩+sin⁡(5θ)∣A1⟩G3∣u⟩=cos⁡(7θ)∣A0⟩+sin⁡(7θ)∣A1⟩\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

Gt∣u⟩=cos⁡((2t+1)θ)∣A0⟩+sin⁡((2t+1)θ)∣A1⟩.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 GG est le produit de deux réflexions, ZfZ_f et H⊗nZORH⊗n.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 Zf.Z_f. Comme nous l'avons déjà observé précédemment :

Zf∣A0⟩=∣A0⟩Zf∣A1⟩=−∣A1⟩.\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 ∣A0⟩\vert A_0\rangle et ∣A1⟩,\vert A_1\rangle, il s'agit d'une réflexion par rapport à la droite parallèle à ∣A0⟩,\vert A_0\rangle, que nous appellerons L1.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 ∣A0⟩\vert A_0\rangle et ∣A1⟩.\vert A_1\rangle.

Une figure illustrant l'action d'une réflexion sur un vecteur.

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

H⊗nZORH⊗n=2∣u⟩⟨u∣−I.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 L2L_2 parallèle au vecteur ∣u⟩.\vert u\rangle. Voici une figure représentant l'action de cette réflexion sur un vecteur unitaire ∣ψ⟩.\vert\psi\rangle.

Une figure illustrant l'action d'une deuxième réflexion sur un vecteur.

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.

Une figure illustrant l'action de l'opération de Grover sur un vecteur.

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 ∣A0⟩\vert A_0\rangle et ∣A1⟩\vert A_1\rangle d'un angle de 2θ.2\theta.