Procédure d'estimation de phase

Nous allons maintenant aborder la procédure d'estimation de phase, qui est un algorithme quantique permettant de résoudre le problème d'estimation de phase.

Nous commencerons par un échauffement à faible précision, qui illustre l'intuition de base derrière cette méthode. Nous parlerons ensuite de la transformée de Fourier quantique, une opération quantique importante utilisée dans la procédure d'estimation de phase, ainsi que de son implémentation sous forme de Circuit quantique. Une fois la transformée de Fourier quantique en main, nous décrirons la procédure d'estimation de phase dans toute sa généralité et analyserons ses performances.

Échauffement : approximer les phases à faible précision

Nous commencerons par quelques versions simples de la procédure d'estimation de phase qui fournissent des solutions à faible précision au problème d'estimation de phase. C'est utile pour expliquer l'intuition derrière la procédure générale que nous verrons un peu plus loin dans la leçon.

Utiliser le retour de phase

Une approche simple du problème d'estimation de phase, qui nous permet d'apprendre quelque chose sur la valeur $\theta$ que nous cherchons, est basée sur le phénomène de retour de phase (phase kick-back). Comme nous allons le voir, c'est essentiellement une version à un seul qubit de la procédure générale d'estimation de phase qui sera discutée plus loin dans la leçon.

En tant qu'entrée du problème d'estimation de phase, nous disposons d'un circuit quantique unitaire pour l'opération $U.$ Nous pouvons utiliser la description de ce circuit pour créer un circuit pour une opération contrôlée-$U$, qui peut être représentée comme le suggère cette figure (avec l'opération $U,$ vue comme une porte quantique, à gauche et une opération contrôlée-$U$ à droite).

Nous pouvons créer un circuit quantique pour une opération contrôlée-$U$ en ajoutant d'abord un qubit de contrôle au circuit pour $U,$ puis en remplaçant chaque porte du circuit pour $U$ par une version contrôlée de cette porte — ainsi, notre nouveau qubit de contrôle contrôle effectivement chaque porte du circuit pour $U.$ Cela nécessite que nous disposions d'une version contrôlée de chaque porte de notre circuit, mais nous pouvons toujours construire des circuits pour ces opérations contrôlées au cas où elles ne seraient pas incluses dans notre ensemble de portes.

Considère maintenant le circuit suivant, où l'état d'entrée $\vert\psi\rangle$ de tous les qubits sauf le premier en haut est le vecteur propre d'état quantique de $U.$

Les probabilités de résultats de mesure pour ce circuit dépendent de la valeur propre de $U$ correspondant au vecteur propre $\vert\psi\rangle.$ Analysons le circuit en détail pour déterminer exactement comment.

L'état initial du circuit est

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

et la première porte de Hadamard transforme cet état en

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

Ensuite, l'opération contrôlée-$U$ est effectuée, ce qui donne l'état

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

En utilisant l'hypothèse que $\vert\psi\rangle$ est un vecteur propre de $U$ ayant la valeur propre $\lambda = e^{2\pi i\theta},$ nous pouvons exprimer cet état autrement comme suit.

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

Nous observons ici le phénomène de retour de phase. Il est légèrement différent cette fois de ce qu'il était pour l'algorithme de Deutsch et l'algorithme de Deutsch-Jozsa, car nous ne travaillons pas avec une porte d'interrogation — mais l'idée est similaire.

Enfin, la deuxième porte de Hadamard est appliquée. Après quelques simplifications, nous obtenons cette expression pour cet état.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

La mesure produit donc les résultats $0$ et $1$ avec ces probabilités :

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

Voici un graphique des probabilités pour les deux résultats possibles, $0$ et $1,$ en fonction de $\theta.$

Naturellement, les deux probabilités s'additionnent toujours à $1.$ Remarque que lorsque $\theta = 0,$ le résultat de la mesure est toujours $0,$ et lorsque $\theta = 1/2,$ le résultat de la mesure est toujours $1.$ Ainsi, bien que le résultat de la mesure ne révèle pas exactement ce qu'est $\theta,$ il nous fournit quand même des informations à son sujet — et si on nous promettait que soit $\theta = 0$ soit $\theta = 1/2,$ on pourrait apprendre du circuit lequel est correct sans erreur.

De manière intuitive, on peut considérer le résultat de la mesure du circuit comme une estimation de $\theta$ à « un bit de précision ». Autrement dit, si on écrivait $\theta$ en notation binaire et qu'on l'arrondissait à un bit, on obtiendrait un nombre comme celui-ci :

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

Le résultat de la mesure peut être vu comme une estimation du bit $a.$ Lorsque $\theta$ n'est ni $0$ ni $1/2,$ il y a une probabilité non nulle que l'estimation soit incorrecte — mais la probabilité de faire une erreur devient de plus en plus petite à mesure qu'on se rapproche de $0$ ou de $1/2.$

Il est naturel de se demander quel rôle jouent les deux portes de Hadamard dans cette procédure :

• La première porte de Hadamard met le qubit de contrôle dans une superposition uniforme de $\vert 0\rangle$ et $\vert 1\rangle,$ de sorte que lorsque le retour de phase se produit, il se produit pour l'état $\vert 1\rangle$ et non pour l'état $\vert 0\rangle$, créant une différence de phase relative qui affecte les résultats de mesure. Si on ne faisait pas cela et que le retour de phase produisait une phase globale, cela n'aurait aucun effet sur les probabilités d'obtenir différents résultats de mesure.

• La deuxième porte de Hadamard nous permet d'apprendre quelque chose sur le nombre $\theta$ grâce au phénomène d'interférence. Avant la deuxième porte de Hadamard, l'état du qubit du haut est

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  et si on mesurait cet état, on obtiendrait $0$ et $1$ chacun avec probabilité $1/2,$ sans rien apprendre sur $\theta.$ En appliquant la deuxième porte de Hadamard, cependant, on fait en sorte que le nombre $\theta$ affecte les probabilités de sortie.

Doubler la phase

Le circuit ci-dessus utilise le phénomène de retour de phase pour approximer $\theta$ à un seul bit de précision. Un bit de précision peut suffire dans certaines situations — mais pour la factorisation, nous aurons besoin d'une précision bien plus grande. Une question naturelle est : comment peut-on en apprendre davantage sur $\theta$ ?

Une chose très simple que l'on peut faire est de remplacer l'opération contrôlée-$U$ dans notre circuit par deux copies de cette opération, comme dans ce circuit :

Deux copies d'une opération contrôlée-$U$ sont équivalentes à une opération contrôlée-$U^2$. Si $\vert\psi\rangle$ est un vecteur propre de $U$ ayant la valeur propre $\lambda = e^{2\pi i \theta},$ alors cet état est aussi un vecteur propre de $U^2,$ cette fois avec la valeur propre $\lambda^2 = e^{2\pi i (2\theta)}.$

Ainsi, si on exécute cette version du circuit, on effectue en fait le même calcul qu'auparavant, sauf que le nombre $\theta$ est remplacé par $2\theta.$ Voici un graphique illustrant les probabilités de sortie lorsque $\theta$ varie de $0$ à $1.$

Faire cela peut effectivement nous fournir des informations supplémentaires sur $\theta.$ Si la représentation binaire de $\theta$ est

$$\theta = 0.a_1 a_2 a_3\cdots$$

alors doubler $\theta$ décale effectivement le point binaire d'une position vers la droite :

$$2\theta = a_1. a_2 a_3\cdots$$

Et parce que nous assimilons $\theta = 1$ à $\theta = 0$ lorsque nous parcourons le cercle unité, nous voyons que le bit $a_1$ n'a aucune influence sur nos probabilités, et nous obtenons en fait une estimation pour le deuxième bit après le point binaire si on arrondit $\theta$ à deux bits. Par exemple, si on savait à l'avance que $\theta$ était soit $0$ soit $1/4,$ on pourrait faire entièrement confiance au résultat de la mesure pour nous dire lequel c'est.

Il n'est cependant pas immédiatement évident comment cette estimation devrait être réconciliée avec ce que nous avons appris du circuit de retour de phase original (non doublé) pour nous donner les informations les plus précises possibles sur $\theta.$ Faisons donc un pas en arrière et réfléchissons à la marche à suivre.

Estimation de phase à deux qubits

Plutôt que de considérer séparément les deux options décrites ci-dessus, combinons-les en un seul circuit comme ceci.

Les portes de Hadamard après les opérations contrôlées ont été supprimées et il n'y a pas encore de mesures ici. Nous ajouterons davantage au circuit au fil de nos réflexions sur la façon d'apprendre le plus possible sur $\theta.$

Si on exécute ce circuit lorsque $\vert\psi\rangle$ est un vecteur propre de $U,$ l'état des qubits du bas restera $\vert\psi\rangle$ tout au long du circuit, et les phases seront « renvoyées » dans l'état des deux qubits du haut. Analysons le circuit avec soin, à l'aide de la figure suivante.

Nous pouvons écrire l'état $\vert\pi_1\rangle$ comme ceci :

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

Lorsque la première opération contrôlée-$U$ est effectuée, la valeur propre $\lambda = e^{2\pi i\theta}$ est renvoyée dans la phase lorsque $a_0$ (le qubit du haut) est égal à $1,$ mais pas lorsqu'il vaut $0.$ Ainsi, nous pouvons exprimer l'état résultant comme ceci :

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

Les deuxième et troisième portes contrôlées-$U$ font quelque chose de similaire, sauf pour $a_1$ plutôt que $a_0,$ et avec $\theta$ remplacé par $2\theta.$ Nous pouvons exprimer l'état résultant comme ceci :

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

Si on considère la chaîne binaire $a_1 a_0$ comme représentant un entier $x \in \{0,1,2,3\}$ en notation binaire, soit $x = 2 a_1 + a_0,$ on peut exprimer cet état autrement comme suit.

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

Notre objectif est d'extraire le plus d'informations possible sur $\theta$ à partir de cet état.

À ce stade, nous allons considérer un cas particulier, où l'on nous promet que $\theta = \frac{y}{4}$ pour un certain entier $y\in\{0,1,2,3\}.$ En d'autres termes, nous avons $\theta\in \{0, 1/4, 1/2, 3/4\},$ de sorte que nous pouvons exprimer ce nombre exactement en notation binaire avec deux bits, comme .$00,$ .$01,$ .$10,$ ou .$11.$ En général, $\theta$ pourrait ne pas être l'une de ces quatre valeurs, mais réfléchir à ce cas particulier nous aidera à comprendre comment extraire le plus efficacement possible des informations sur $\theta$ en général.

Nous allons d'abord définir un vecteur d'état à deux qubits pour chaque valeur possible $y \in \{0, 1, 2, 3\}.$

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

Après simplification des exponentielles, nous pouvons écrire ces vecteurs comme suit.

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

Ces vecteurs sont orthogonaux : si on choisit n'importe quelle paire d'entre eux et qu'on calcule leur produit scalaire, on obtient $0.$ Chacun est aussi un vecteur unitaire, donc $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ est une base orthonormée. Nous savons donc immédiatement qu'il existe une mesure capable de les discriminer parfaitement — ce qui signifie que, si on nous en donne un sans nous dire lequel, on peut déterminer lequel c'est sans erreur.

Pour effectuer une telle discrimination avec un circuit quantique, nous pouvons d'abord définir une opération unitaire $V$ qui transforme les états de la base standard en les quatre états listés ci-dessus.

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

Pour écrire $V$ sous forme de matrice $4\times 4$, il suffit de prendre les colonnes de $V$ comme étant les états $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle.$

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Il s'agit d'une matrice spéciale, et il est probable que certains lecteurs l'aient déjà rencontrée : c'est la matrice associée à la transformée de Fourier discrète à $4$ dimensions. En tenant compte de ce fait, appelons-la $\mathrm{QFT}_4$ plutôt que $V.$ Le nom $\mathrm{QFT}$ est l'abréviation de transformée de Fourier quantique — qui est essentiellement la transformée de Fourier discrète, vue comme une opération unitaire. Nous discuterons de la transformée de Fourier quantique de manière plus détaillée et générale sous peu.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Nous pouvons effectuer l'inverse de cette opération pour aller dans l'autre sens, afin de transformer les états $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ en états de la base standard $\vert 0\rangle,\ldots,\vert 3\rangle.$ Si on fait cela, on peut mesurer pour apprendre quelle valeur $y\in\{0,1,2,3\}$ décrit $\theta$ via $\theta = y/4.$ Voici un diagramme d'un circuit quantique qui fait cela.

En résumé, si on exécute ce circuit lorsque $\theta = y/4$ pour $y\in\{0,1,2,3\},$ l'état immédiatement avant les mesures sera $\vert \psi\rangle \vert y\rangle$ (pour $y$ encodé comme une chaîne binaire à deux bits), de sorte que les mesures révéleront la valeur $y$ sans erreur.

Ce circuit est motivé par le cas particulier où $\theta \in \{0,1/4,1/2,3/4\}$ — mais on peut l'exécuter pour n'importe quel choix de $U$ et $\vert \psi\rangle,$ et donc n'importe quelle valeur de $\theta,$ que l'on souhaite. Voici un graphique des probabilités de sortie que le circuit produit pour des choix arbitraires de $\theta.$

C'est une nette amélioration par rapport à la variante à un seul qubit décrite précédemment dans la leçon. Ce n'est pas parfait — cela peut donner une mauvaise réponse — mais la réponse est fortement orientée vers les valeurs de $y$ pour lesquelles $y/4$ est proche de $\theta.$ En particulier, le résultat le plus probable correspond toujours à la valeur de $y/4$ la plus proche de $\theta$ (en assimilant $\theta = 0$ et $\theta = 1$ comme précédemment), et d'après le graphique, il semble que cette valeur la plus proche pour $x$ apparaisse toujours avec une probabilité légèrement supérieure à $40\%.$ Lorsque $\theta$ se trouve exactement à mi-chemin entre deux telles valeurs, comme $\theta = 0.375$ par exemple, les deux valeurs de $y$ également proches sont également probables.

Se préparer à généraliser à plusieurs qubits

Étant donné l'amélioration que nous venons d'obtenir en utilisant deux qubits de contrôle plutôt qu'un, conjointement avec l'inverse de la transformée de Fourier quantique à $4$ dimensions, il est naturel d'envisager de le généraliser davantage — en ajoutant plus de qubits de contrôle. Lorsque nous faisons cela, nous obtenons la procédure d'estimation de phase générale. Nous verrons comment cela fonctionne sous peu, mais pour le décrire avec précision, nous allons devoir aborder la transformée de Fourier quantique de manière plus générale, pour voir comment elle est définie pour d'autres dimensions et comment nous pouvons l'implémenter (ou son inverse) avec un circuit quantique.

Transformée de Fourier quantique

La transformée de Fourier quantique est une opération unitaire qui peut être définie pour toute dimension entière positive $N.$ Dans cette section, on va voir comment cette opération est définie et comment elle peut être implémentée avec un circuit quantique sur $m$ qubits à un coût $O(m^2)$ quand $N = 2^m.$

Les matrices qui décrivent la transformée de Fourier quantique sont dérivées d'une opération analogue sur des vecteurs de dimension $N$ connue sous le nom de transformée de Fourier discrète. On peut penser à cette opération de différentes façons. Par exemple, on peut concevoir la transformée de Fourier discrète en termes purement abstraits et mathématiques, comme un mapping linéaire. Ou on peut y penser en termes calculatoires, où on dispose d'un vecteur de dimension $N$ de nombres complexes (en utilisant la notation binaire pour encoder les parties réelles et imaginaires des entrées, supposons) et le but est de calculer le vecteur de dimension $N$ obtenu en appliquant la transformée de Fourier discrète. Notre focus sera sur une troisième façon de voir les choses, à savoir considérer cette transformation comme une opération unitaire qui peut être effectuée sur un système quantique.

Il existe un algorithme efficace pour calculer la transformée de Fourier discrète sur un vecteur d'entrée donné, connu sous le nom de transformée de Fourier rapide. Elle a des applications en traitement du signal et dans de nombreux autres domaines, et est considérée par beaucoup comme l'un des algorithmes les plus importants jamais découverts. Il s'avère que l'implémentation de la transformée de Fourier quantique quand $N$ est une puissance de 2, que l'on va étudier, repose précisément sur la même structure sous-jacente qui rend la transformée de Fourier rapide possible.

Définition de la transformée de Fourier quantique

Pour définir la transformée de Fourier quantique, on va d'abord définir un nombre complexe $\omega_N,$ pour chaque entier positif $N,$ comme suit :

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

C'est le nombre sur le cercle unité complexe qu'on obtient en partant de $1$ et en se déplaçant dans le sens antihoraire d'un angle de $2\pi/N$ radians, ou d'une fraction $1/N$ de la circonférence du cercle. Voici quelques exemples :

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

On peut maintenant définir la transformée de Fourier quantique de dimension $N,$ décrite par une matrice $N\times N$ dont les lignes et les colonnes sont associées aux états de la base standard $\vert 0\rangle,\ldots,\vert N-1\rangle.$ On n'aura besoin de cette opération que lorsque $N = 2^m$ est une puissance de $2$ pour l'estimation de phase, mais l'opération peut être définie pour tout entier positif $N.$

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

Comme on l'a déjà mentionné, c'est la matrice associée à la transformée de Fourier discrète de dimension $N.$ Souvent le facteur préfixe $1/\sqrt{N}$ n'est pas inclus dans la définition de cette matrice, mais on doit l'inclure pour obtenir une matrice unitaire.

Voici la transformée de Fourier quantique, écrite comme une matrice, pour quelques petites valeurs de $N.$

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

Remarque : $\mathrm{QFT}_2$ est un autre nom pour l'opération de Hadamard.

Unitarité

Vérifions que $\mathrm{QFT}_N$ est unitaire, pour tout choix de $N.$ Une façon de le faire est de montrer que ses colonnes forment une base orthonormale. On peut définir un vecteur correspondant à la colonne numéro $y,$ en commençant à $y = 0$ jusqu'à $y = N-1,$ comme ceci :

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

Le produit scalaire entre deux quelconques de ces vecteurs nous donne l'expression suivante :

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

On peut évaluer des sommes de ce type en utilisant la formule suivante pour la somme des $N$ premiers termes d'une série géométrique.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{si } \alpha\neq 1\\[2mm] N & \text{si } \alpha=1 \end{cases}$$

Plus précisément, on peut utiliser cette formule quand $\alpha = \omega_N^{y-z}.$ Quand $y = z,$ on a $\alpha = 1,$ donc en appliquant la formule et en divisant par $N$ on obtient

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

Quand $y\neq z,$ on a $\alpha \neq 1,$ et la formule révèle ceci :

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

Cela se produit parce que $\omega_N^N = e^{2\pi i} = 1,$ donc $\omega_N^{N(y-z)} = 1^{y-z} = 1,$ ce qui rend le numérateur nul, tandis que le dénominateur est non nul parce que $\omega_N^{y-z} \neq 1.$ Intuitivement, ce qu'on fait c'est sommer un ensemble de points distribués autour du cercle unité, et ils s'annulent et donnent $0$ lorsqu'on les additionne.

On a donc établi que $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ est un ensemble orthonormal,

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

ce qui révèle que $\mathrm{QFT}_N$ est unitaire.

Portes à phase contrôlée

Pour implémenter la transformée de Fourier quantique avec un circuit quantique, on va avoir besoin d'utiliser des portes à phase contrôlée. Rappelons qu'une opération de phase est une opération unitaire à un qubit de la forme

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

pour tout nombre réel $\alpha.$ Une version contrôlée de cette porte a la matrice suivante :

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

Pour cette porte contrôlée, peu importe quel qubit est le contrôle et lequel est la cible, car les deux possibilités sont équivalentes. On peut utiliser l'un ou l'autre des symboles suivants pour représenter cette porte dans les diagrammes de circuits quantiques.

Pour la troisième forme, l'étiquette $\alpha$ est aussi parfois placée sur le côté du fil de contrôle ou sous le contrôle inférieur selon ce qui est le plus commode.

Pour effectuer la transformée de Fourier quantique quand $N = 2^m$ et $m\geq 2,$ on va avoir besoin d'effectuer une opération sur $m$ qubits dont l'action sur les états de la base standard peut être décrite comme

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

où $a$ est un bit et $y \in \{0,\ldots,2^{m-1} - 1\}$ est un nombre encodé en notation binaire comme une chaîne de $m-1$ bits. Cela peut être fait en utilisant des portes à phase contrôlée en généralisant l'exemple suivant, pour lequel $m=5.$

En général, pour un choix arbitraire de $m\geq 2,$ le qubit du haut correspondant au bit $a$ peut être vu comme le contrôle, avec les portes de phase $P_{\alpha}$ allant de $\alpha = \pi/2^{m-1}$ sur le qubit correspondant au bit le moins significatif de $y$ à $\alpha = \frac{\pi}{2}$ sur le qubit correspondant au bit le plus significatif de $y.$ Ces portes à phase contrôlée commutent toutes entre elles et peuvent être exécutées dans n'importe quel ordre.

Implémentation en circuit de la QFT

On va maintenant voir comment on peut implémenter la transformée de Fourier quantique avec un circuit quand la dimension $N = 2^m$ est une puissance de $2.$ Il existe en fait plusieurs façons d'implémenter la transformée de Fourier quantique, mais c'est sans doute la méthode la plus simple connue. Une fois qu'on sait comment implémenter la transformée de Fourier quantique avec un circuit quantique, implémenter son inverse est simple : on peut remplacer chaque porte par son inverse (ou, de manière équivalente, le transposé conjugué) et appliquer les portes dans l'ordre inverse. Tout circuit quantique composé uniquement de portes unitaires peut être inversé de cette façon.

L'implémentation est récursive par nature, c'est donc ainsi qu'elle se décrit le plus naturellement. Le cas de base est $m=1,$ auquel cas la transformée de Fourier quantique est une opération de Hadamard.

Pour effectuer la transformée de Fourier quantique sur $m$ qubits quand $m \geq 2,$ on peut effectuer les étapes suivantes, dont on décrira les actions pour des états de la base standard de la forme $\vert x \rangle \vert a\rangle,$ où $x\in\{0,\ldots,2^{m-1} - 1\}$ est un entier encodé sur $m-1$ bits en notation binaire et $a$ est un seul bit.

1. D'abord appliquer la transformée de Fourier quantique de dimension $2^{m-1}$ aux $m-1$ qubits du bas/gauche pour obtenir cet état :

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   Cela se fait en appliquant récursivement la méthode décrite ici pour un qubit en moins, en utilisant l'opération de Hadamard sur un seul qubit comme cas de base.

2. Utiliser le qubit du haut/droite comme contrôle pour injecter la phase $\omega_{2^m}^y$ pour chaque état de la base standard $\vert y\rangle$ des $m-1$ qubits restants (comme décrit ci-dessus) afin d'obtenir cet état :

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. Effectuer une porte de Hadamard sur le qubit du haut/droite pour obtenir cet état :

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. Permuter l'ordre des qubits de sorte que le bit le moins significatif devienne le bit le plus significatif, avec tous les autres décalés vers le haut/droite :

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

Par exemple, voici le circuit qu'on obtient pour $N = 32 = 2^5.$ Dans ce diagramme, les qubits sont nommés de façon à correspondre aux vecteurs de la base standard $\vert x\rangle \vert a\rangle$ (pour l'entrée) et $\vert b\rangle \vert y\rangle$ (pour la sortie) par souci de clarté.

Analyse

La formule clé qu'on doit vérifier pour s'assurer que le circuit décrit ci-dessus implémente la transformée de Fourier quantique de dimension $2^m$ est celle-ci :

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

Cette formule fonctionne pour tout choix d'entiers $a,$ $b,$ $x,$ et $y,$ mais on n'en aura besoin que pour $a,b\in\{0,1\}$ et $x,y\in\{0,\ldots,2^{m-1}-1\}.$ On peut la vérifier en développant le produit dans l'exposant du membre de droite,

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

où la seconde égalité utilise l'observation que

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

La transformée de Fourier quantique de dimension $2^m$ est définie comme suit pour tout $u\in\{0,\ldots,2^m - 1\}.$

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

Si on écrit $u$ et $v$ comme

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

pour $a,b\in\{0,1\}$ et $x,y\in\{0,\ldots,2^{m-1} - 1\},$ on obtient

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

Enfin, en considérant les états de la base standard $\vert x \rangle \vert a\rangle$ et $\vert b \rangle \vert y \rangle$ comme des encodages binaires d'entiers dans la plage $\{0,\ldots,2^m-1\},$

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

on voit que le circuit ci-dessus implémente bien l'opération requise. Si cette méthode pour effectuer la transformée de Fourier quantique te semble remarquable, c'est parce qu'elle l'est : c'est essentiellement la transformée de Fourier rapide sous la forme d'un circuit quantique.

Enfin, comptons combien de portes sont utilisées dans le circuit décrit. Les portes à phase contrôlée ne font pas partie du jeu de portes standard dont on a parlé dans la leçon précédente, mais pour commencer on va les ignorer et compter chacune d'elles comme une seule porte.

Notons $s_m$ le nombre de portes dont on a besoin pour chaque choix possible de $m.$ Si $m=1,$ la transformée de Fourier quantique n'est qu'une opération de Hadamard, donc

$$s_1 = 1.$$

Si $m\geq 2,$ alors dans le circuit ci-dessus on a besoin de $s_{m-1}$ portes pour la transformée de Fourier quantique sur $m-1$ qubits, plus $m-1$ portes à phase contrôlée, plus une porte de Hadamard, plus $m-1$ portes d'échange, donc

$$s_m = s_{m-1} + (2m - 1).$$

On peut obtenir une expression sous forme fermée en sommant :

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

En réalité, on n'a pas besoin d'autant de portes d'échange que ce que la méthode décrit. Si on réorganise un peu les portes, on peut repousser toutes les portes d'échange vers la droite et réduire le nombre de portes d'échange nécessaires à $\lfloor m/2\rfloor.$ D'un point de vue asymptotique, ce n'est pas une amélioration majeure : on obtient toujours des circuits de taille $O(m^2)$ pour effectuer $\mathrm{QFT}_{2^m}.$

Si on souhaite implémenter la transformée de Fourier quantique en utilisant uniquement des portes de notre jeu de portes standard, on doit construire ou approcher chacune des portes à phase contrôlée avec des portes de notre ensemble. Le nombre requis dépend du niveau de précision souhaité, mais en fonction de $m$ le coût total reste quadratique.

Il est en fait possible d'approcher la transformée de Fourier quantique assez fidèlement avec un nombre sous-quadratique de portes, en utilisant le fait que $P_{\alpha}$ est très proche de l'opération identité quand $\alpha$ est très petit — ce qui signifie qu'on peut simplement omettre la plupart des portes à phase contrôlée sans perdre beaucoup en termes de précision.

Procédure générale et analyse

Nous allons maintenant examiner la procédure d'estimation de phase dans le cas général. L'idée est d'étendre la version à deux qubits de l'estimation de phase que nous avons étudiée ci-dessus, de la manière naturelle suggérée par le schéma suivant.

Remarque : pour chaque nouveau qubit de contrôle ajouté en haut, on double le nombre d'applications de l'opération unitaire $U$. C'est indiqué dans le schéma par les puissances sur $U$ pour chacune des opérations unitaires contrôlées.

La façon la plus directe d'implémenter une opération $U^k$ contrôlée pour un certain choix de $k$ est simplement de répéter $k$ fois une opération $U$ contrôlée. Si c'est effectivement la méthode utilisée, il faut reconnaître que l'ajout de qubits de contrôle contribue de manière significative à la taille du circuit : si l'on dispose de $m$ qubits de contrôle, comme le montre le schéma, un total de $2^m - 1$ copies de l'opération $U$ contrôlée sont nécessaires. Cela signifie qu'un coût de calcul significatif est engagé à mesure que $m$ augmente — mais comme nous le verrons, cela conduit aussi à une approximation nettement plus précise de $\theta.$

Il est important de noter, cependant, que pour certains choix de $U$ il peut être possible de créer un circuit qui implémente l'opération $U^k$ pour de grandes valeurs de $k$ de manière plus efficace qu'en répétant simplement $k$ fois le circuit de $U.$ Nous verrons un exemple concret de cela dans le contexte de la factorisation d'entiers plus loin dans la leçon, où l'algorithme efficace d'exponentiation modulaire présenté dans la leçon précédente vient à la rescousse.

Analysons maintenant le circuit qui vient d'être décrit. L'état juste avant la transformée de Fourier quantique inverse ressemble à ceci :

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

Un cas particulier

Dans le même esprit que ce que nous avons fait dans le cas $m=2$, nous allons d'abord considérer le cas particulier où $\theta = y/2^m$ pour $y\in\{0,\ldots,2^m-1\}.$ Dans ce cas, l'état avant la transformée de Fourier quantique inverse peut s'écrire autrement comme suit :

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

Ainsi, lorsque la transformée de Fourier quantique inverse est appliquée, l'état devient

$$\vert\psi\rangle \vert y\rangle$$

et les mesures révèlent $y$ (encodé en binaire).

Borner les probabilités

Pour d'autres valeurs de $\theta,$ c'est-à-dire celles qui ne prennent pas la forme $y/2^m$ pour un entier $y,$ les résultats de mesure ne seront pas certains, mais on peut démontrer des bornes sur les probabilités des différents résultats. Considérons désormais un choix arbitraire de $\theta$ vérifiant $0\leq \theta < 1.$

Après l'application de la transformée de Fourier quantique inverse, l'état du circuit est le suivant :

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

Ainsi, lorsque les mesures sur les $m$ qubits du haut sont effectuées, on observe chaque résultat $y$ avec la probabilité

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

Pour mieux comprendre ces probabilités, nous allons utiliser la même formule que précédemment, pour la somme de la portion initiale d'une série géométrique.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

On peut simplifier la somme apparaissant dans la formule de $p_y$ en prenant $\alpha = e^{2\pi i (\theta - y/2^m)}.$ Voici ce qu'on obtient.

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

Donc, dans le cas où $\theta = y/2^m,$ on trouve que $p_y = 1$ (comme on le savait déjà en considérant ce cas particulier), et dans le cas où $\theta \neq y/2^m,$ on trouve que

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

On peut en apprendre davantage sur ces probabilités en réfléchissant à la relation entre les longueurs des arcs et des cordes sur le cercle unité. Voici une figure qui illustre les relations nécessaires pour tout nombre réel $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr].$

D'abord, la longueur de la corde (tracée en bleu) ne peut pas être plus grande que la longueur de l'arc (tracée en violet) :

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

En reliant ces longueurs dans l'autre sens, on constate que le rapport de la longueur de l'arc à la longueur de la corde est maximal quand $\delta = \pm 1/2$, et dans ce cas le rapport est la moitié de la circonférence du cercle divisée par le diamètre, soit $\pi/2.$ Ainsi, on a

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

et donc

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

Une analyse fondée sur ces relations révèle les deux faits suivants.

1. Suppose que $\theta$ est un nombre réel et que $y\in \{0,\ldots,2^m-1\}$ vérifie

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

   Cela signifie que $y/2^m$ est soit la meilleure approximation à $m$ bits de $\theta$, soit exactement à mi-chemin entre $y/2^m$ et $(y-1)/2^m$ ou $(y+1)/2^m$, donc l'une des deux meilleures approximations de $\theta.$

   Nous allons montrer que $p_y$ doit être assez grand dans ce cas. Avec l'hypothèse considérée, il s'ensuit que $\vert 2^m \theta - y \vert \leq 1/2$, donc on peut utiliser la deuxième observation ci-dessus reliant les longueurs d'arc et de corde pour conclure que

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   On peut également utiliser la première observation sur les longueurs d'arc et de corde pour conclure que

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   En appliquant ces deux inégalités à $p_y$, on obtient

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   Cela explique notre observation que le meilleur résultat se produit avec une probabilité supérieure à $40\%$ dans la version $m=2$ de l'estimation de phase présentée plus tôt. Ce n'est pas vraiment 40%, c'est $4/\pi^2$, et cette borne vaut en fait pour tout choix de $m.$

2. Suppose maintenant que $y\in \{0,\ldots,2^m-1\}$ vérifie

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   Cela signifie qu'il existe une meilleure approximation $z/2^m$ de $\theta$ entre $\theta$ et $y/2^m.$

   Cette fois, nous allons montrer que $p_y$ ne peut pas être trop grand. On commence par la simple observation que

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   qui découle du fait que deux points quelconques du cercle unité peuvent différer en valeur absolue d'au plus $2.$

   On peut aussi utiliser la deuxième observation sur les longueurs d'arc et de corde ci-dessus, cette fois en travaillant avec le dénominateur de $p_y$ plutôt que le numérateur, pour conclure

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   En combinant les deux inégalités, on obtient

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   À noter que, bien que cette borne soit suffisante pour nos besoins, elle est assez grossière — la probabilité est en général bien inférieure à $1/4.$

La conclusion importante à retenir de cette analyse est que les approximations très proches de $\theta$ ont de grandes chances de se produire — on obtient la meilleure approximation à $m$ bits avec une probabilité supérieure à $40\%$ — alors que les approximations s'écartant de plus de $2^{-m}$ sont moins susceptibles de se produire, avec une probabilité bornée supérieurement par $25\%.$

Grâce à ces garanties, il est possible de renforcer notre confiance en répétant plusieurs fois la procédure d'estimation de phase, afin de recueillir des preuves statistiques sur $\theta.$ Il est important de noter que l'état $\vert\psi\rangle$ de l'ensemble inférieur de qubits n'est pas modifié par la procédure d'estimation de phase, il peut donc être utilisé pour exécuter la procédure autant de fois que l'on veut. En particulier, à chaque exécution du circuit, on obtient la meilleure approximation à $m$ bits de $\theta$ avec une probabilité supérieure à $40\%$, tandis que la probabilité de s'écarter de plus de $2^{-m}$ est bornée par $25\%.$ Si on exécute le circuit plusieurs fois et qu'on prend le résultat le plus fréquent parmi les exécutions, il est donc extrêmement probable que le résultat le plus fréquent ne soit pas l'un de ceux qui se produisent au plus $25\%$ du temps. En conséquence, on sera très probablement en mesure d'obtenir une approximation $y/2^m$ à $1/2^m$ près de la valeur $\theta.$ En effet, la probabilité peu probable de s'écarter de plus de $1/2^m$ décroît exponentiellement avec le nombre d'exécutions de la procédure.

Voici deux graphiques montrant les probabilités pour trois valeurs consécutives de $y$ quand $m = 3$ et $m=4$ en fonction de $\theta.$ (Seuls trois résultats sont affichés par souci de clarté. Les probabilités des autres résultats s'obtiennent en décalant cycliquement la même fonction sous-jacente.)