L'algorithme de Shor

Nous allons maintenant nous intéresser au problème de la factorisation des entiers, et voir comment il peut être résolu efficacement sur un ordinateur quantique à l'aide de l'estimation de phase. L'algorithme que nous obtiendrons est l'algorithme de Shor pour la factorisation des entiers. Shor n'a pas décrit son algorithme spécifiquement en termes d'estimation de phase, mais c'est une façon naturelle et intuitive d'expliquer son fonctionnement.

Nous commencerons par étudier un problème intermédiaire connu sous le nom de problème de recherche d'ordre, et nous verrons comment l'estimation de phase fournit une solution à ce problème. Nous verrons ensuite comment une solution efficace au problème de recherche d'ordre nous donne une solution efficace au problème de factorisation des entiers. (Lorsque la solution d'un problème fournit une solution à un autre problème de cette manière, on dit que le second problème se réduit au premier — donc, dans ce cas, nous réduisons la factorisation des entiers à la recherche d'ordre.) Cette seconde partie de l'algorithme de Shor n'a recours à aucun calcul quantique ; elle est entièrement classique. Le calcul quantique n'est nécessaire que pour résoudre la recherche d'ordre.

Le problème de recherche d'ordre

Quelques notions de base en théorie des nombres

Pour expliquer le problème de recherche d'ordre et la façon dont il peut être résolu par estimation de phase, il sera utile de commencer par quelques notions de base en théorie des nombres, et d'introduire au passage une notation pratique.

Pour commencer, pour tout entier positif $N$ donné, définissons l'ensemble $\mathbb{Z}_N$ comme suit.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

Par exemple, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ et ainsi de suite.

Ce sont des ensembles de nombres, mais nous pouvons les considérer comme davantage que de simples ensembles. En particulier, nous pouvons penser à des opérations arithmétiques sur $\mathbb{Z}_N$, telles que l'addition et la multiplication — et si nous convenons de toujours prendre nos résultats modulo $N$ (c'est-à-dire, diviser par $N$ et prendre le reste comme résultat), nous resterons toujours dans cet ensemble lorsque nous effectuons ces opérations. Les deux opérations spécifiques d'addition et de multiplication, toutes deux prises modulo $N$, transforment $\mathbb{Z}_N$ en un anneau, qui est un type d'objet fondamentalement important en algèbre.

Par exemple, $3$ et $5$ sont des éléments de $\mathbb{Z}_7$, et si nous les multiplions entre eux nous obtenons $3\cdot 5 = 15$, qui laisse un reste de $1$ lorsqu'il est divisé par $7$. Parfois, on exprime cela comme suit.

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

Mais nous pouvons aussi simplement écrire $3 \cdot 5 = 1$, à condition qu'il soit clair que nous travaillons dans $\mathbb{Z}_7$, simplement pour garder notre notation aussi simple que possible.

À titre d'exemple, voici les tables d'addition et de multiplication pour $\mathbb{Z}_6.$

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

Parmi les $N$ éléments de $\mathbb{Z}_N,$ les éléments $a\in\mathbb{Z}_N$ qui satisfont $\gcd(a,N) = 1$ sont particuliers. On note souvent l'ensemble contenant ces éléments à l'aide d'une étoile, comme ceci.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

Si nous nous concentrons sur l'opération de multiplication, l'ensemble $\mathbb{Z}_N^{\ast}$ forme un groupe — plus précisément un groupe abélien — qui est un autre type d'objet important en algèbre. C'est un fait fondamental à propos de ces ensembles (et des groupes finis en général) que si nous prenons n'importe quel élément $a\in\mathbb{Z}_N^{\ast}$ et que nous le multiplions plusieurs fois par lui-même, nous finirons toujours par obtenir le nombre $1.$

Pour un premier exemple, prenons $N=6.$ Nous avons $5\in\mathbb{Z}_6^{\ast}$ car $\gcd(5,6) = 1,$ et si nous multiplions $5$ par lui-même nous obtenons $1,$ comme le confirme la table ci-dessus.

$$5^2 = 1 \quad \text{(en travaillant dans $\mathbb{Z}_6$)}$$

Pour un second exemple, prenons $N = 21.$ Si nous parcourons les nombres de $0$ à $20,$ ceux dont le PGCD avec $21$ vaut $1$ sont les suivants.

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

Pour chacun de ces éléments, il est possible d'élever ce nombre à une puissance entière positive pour obtenir $1.$ Voici les plus petites puissances pour lesquelles cela fonctionne :

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

Naturellement, nous travaillons dans $\mathbb{Z}_{21}$ pour toutes ces équations, ce que nous n'avons pas pris la peine d'écrire — nous le considérons comme implicite pour éviter d'alourdir les notations. Nous continuerons à faire ainsi tout au long de la leçon.

Énoncé du problème et lien avec l'estimation de phase

Nous pouvons maintenant énoncer le problème de recherche d'ordre.

Recherche d'ordre

Entrée : entiers positifs $N$ et $a$ satisfaisant $\gcd(N,a) = 1$
Sortie : le plus petit entier positif $r$ tel que $a^r \equiv 1$ $(\textrm{mod } N)$

De manière équivalente, avec la notation que nous venons d'introduire, on nous donne $a \in \mathbb{Z}_N^{\ast},$ et nous cherchons le plus petit entier positif $r$ tel que $a^r = 1.$ Ce nombre $r$ est appelé l'ordre de $a$ modulo $N.$

Pour relier le problème de recherche d'ordre à l'estimation de phase, considérons l'opération définie sur un système dont les états classiques correspondent à $\mathbb{Z}_N,$ où l'on multiplie par un élément fixe $a\in\mathbb{Z}_N^{\ast}.$

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(pour chaque $x\in\mathbb{Z}_N$)}$$

Pour être précis, nous effectuons la multiplication dans $\mathbb{Z}_N,$ donc il est sous-entendu que nous prenons le produit modulo $N$ à l'intérieur du ket, dans le membre de droite de l'équation.

Par exemple, si nous prenons $N = 15$ et $a=2,$ alors l'action de $M_2$ sur la base standard $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ est la suivante.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

Il s'agit d'une opération unitaire pourvu que $\gcd(a,N)=1;$ elle mélange les éléments de la base standard $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ de sorte que sous forme de matrice, il s'agit d'une matrice de permutation. Il est évident, d'après sa définition, que cette opération est déterministe, et une façon simple de voir qu'elle est inversible consiste à penser à l'ordre $r$ de $a$ modulo $N,$ et à reconnaître que l'inverse de $M_a$ est $M_a^{r-1}.$

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

Il existe une autre façon de penser à l'inverse qui ne nécessite aucune connaissance de $r$ (qui, après tout, est ce que nous essayons de calculer). Pour tout élément $a\in\mathbb{Z}_N^{\ast}$ il existe toujours un unique élément $b\in\mathbb{Z}_N^{\ast}$ qui satisfait $ab=1.$ Nous notons cet élément $b$ par $a^{-1},$ et il peut être calculé efficacement ; une extension de l'algorithme du PGCD d'Euclide le fait avec un coût quadratique en $\operatorname{lg}(N).$ Et ainsi

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

Ainsi, l'opération $M_a$ est à la fois déterministe et inversible. Cela implique qu'elle est décrite par une matrice de permutation, et qu'elle est donc unitaire.

Intéressons-nous maintenant aux vecteurs propres et aux valeurs propres de l'opération $M_a,$ en supposant que $a\in\mathbb{Z}_N^{\ast}.$ Comme nous venons de l'établir, cette hypothèse nous indique que $M_a$ est unitaire.

Il y a $N$ valeurs propres de $M_a,$ éventuellement avec répétition d'une même valeur propre plusieurs fois, et en général il existe une certaine liberté dans le choix des vecteurs propres correspondants — mais nous n'avons pas besoin de nous préoccuper de toutes les possibilités. Commençons simplement et identifions un seul vecteur propre de $M_a.$

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

Le nombre $r$ est l'ordre de $a$ modulo $N,$ ici et dans le reste de la leçon. La valeur propre associée à ce vecteur propre est $1$ car il n'est pas modifié lorsque nous multiplions par $a.$

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

Cela se produit parce que $a^r = 1,$ donc chaque état de la base standard $\vert a^k \rangle$ est décalé vers $\vert a^{k+1} \rangle$ pour $k\leq r-1,$ et $\vert a^{r-1} \rangle$ est renvoyé vers $\vert 1\rangle.$ Pour parler de façon informelle, c'est comme si nous remuions lentement $\vert \psi_0 \rangle,$ mais il est déjà complètement mélangé, donc rien ne change.

Voici un autre exemple de vecteur propre de $M_a.$ Celui-ci se révèle plus intéressant dans le contexte de la recherche d'ordre et de l'estimation de phase.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

De manière équivalente, nous pouvons écrire ce vecteur à l'aide d'une somme, comme suit.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

Nous voyons ici apparaître naturellement le nombre complexe $\omega_r = e^{2\pi i/r},$ en raison de la manière dont fonctionne la multiplication par $a$ modulo $N.$ Cette fois, la valeur propre correspondante est $\omega_r.$ Pour le voir, nous pouvons d'abord calculer comme suit.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

Ensuite, puisque $\omega_r^{-r} = 1 = \omega_r^0$ et $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle,$ nous voyons que

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

donc $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle.$

En utilisant le même raisonnement, nous pouvons identifier des paires vecteur propre/valeur propre supplémentaires pour $M_a.$ Pour tout choix de $j\in\{0,\ldots,r-1\}$ nous avons que

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

est un vecteur propre de $M_a$ dont la valeur propre correspondante est $\omega_r^j.$

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

Il existe d'autres vecteurs propres de $M_a,$ mais nous n'avons pas besoin de nous en préoccuper — nous nous concentrerons uniquement sur les vecteurs propres $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ que nous venons d'identifier.

Recherche d'ordre par estimation de phase

Pour résoudre le problème de recherche d'ordre pour un choix donné de $a\in\mathbb{Z}_N^{\ast},$ nous pouvons appliquer la procédure d'estimation de phase à l'opération $M_a.$

Pour cela, nous devons implémenter efficacement, avec un circuit quantique, non seulement $M_a,$ mais aussi $M_a^2,$ $M_a^4,$ $M_a^8,$ et ainsi de suite, en allant aussi loin que nécessaire pour obtenir une estimation suffisamment précise à partir de la procédure d'estimation de phase. Nous expliquerons ici comment cela peut être fait, et nous déterminerons plus tard exactement quelle précision est nécessaire.

Commençons par l'opération $M_a$ seule. Naturellement, comme nous travaillons avec le modèle des circuits quantiques, nous utiliserons la notation binaire pour coder les nombres entre $0$ et $N-1.$ Le plus grand nombre que nous devons coder est $N-1,$ donc le nombre de bits dont nous avons besoin est

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

Par exemple, si $N = 21$ nous avons $n = \operatorname{lg}(N-1) = 5.$ Voici à quoi ressemble le codage des éléments de $\mathbb{Z}_{21}$ sous forme de chaînes binaires de longueur $5.$

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

Et maintenant, voici une définition précise de la façon dont $M_a$ est défini comme une opération à $n$ qubits.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

L'important est que, même si seul le comportement de $M_a$ pour $\vert 0\rangle,\ldots,\vert N-1\rangle$ nous intéresse, nous devons tout de même préciser comment elle agit sur les $2^n - N$ états restants de la base standard — et nous devons le faire de manière à obtenir malgré tout une opération unitaire. Définir $M_a$ de sorte qu'elle ne fasse rien aux états restants de la base standard permet d'y parvenir.

En utilisant les algorithmes de multiplication et de division entières abordés dans la leçon précédente, ainsi que la méthodologie pour leurs implémentations réversibles et sans déchets, nous pouvons construire un circuit quantique qui réalise $M_a,$ pour tout choix de $a\in\mathbb{Z}_N^{\ast},$ à un coût de $O(n^2).$ Voici une façon de procéder.

1. Construire un circuit réalisant l'opération

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

   où

   $$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

   en utilisant la méthode décrite dans la leçon précédente. Cela nous donne un circuit de taille $O(n^2).$

2. Échanger les deux systèmes de $n$ qubits en utilisant $n$ portes swap pour échanger les qubits individuellement.

3. De la même manière que pour la première étape, construire un circuit pour l'opération

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

   où $a^{-1}$ est l'inverse de $a$ dans $\mathbb{Z}_N^{\ast}.$

En initialisant les $n$ qubits du bas et en composant les trois étapes, nous obtenons la transformation suivante :

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{étape 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{étape 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{étape 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

La méthode nécessite des qubits de travail, mais ceux-ci sont ramenés à leur état initialisé à la fin, ce qui nous permet d'utiliser ces circuits pour l'estimation de phase. Le coût total du circuit que nous obtenons est $O(n^2).$

Pour réaliser $M_a^2,$ $M_a^4,$ $M_a^8,$ et ainsi de suite, nous pouvons utiliser exactement la même méthode, sauf que nous remplaçons $a$ par $a^2,$ $a^4,$ $a^8,$ et ainsi de suite, en tant qu'éléments de $\mathbb{Z}_N^{\ast}.$ C'est-à-dire que, pour toute puissance $k$ choisie, nous pouvons créer un circuit pour $M_a^k$ non pas en itérant $k$ fois le circuit de $M_a,$ mais en calculant plutôt $b = a^k \in \mathbb{Z}_N^{\ast}$ puis en utilisant le circuit de $M_b.$

Le calcul des puissances $a^k \in \mathbb{Z}_N$ est le problème d'exponentiation modulaire mentionné dans la leçon précédente. Ce calcul peut être effectué classiquement, à l'aide de l'algorithme d'exponentiation modulaire mentionné dans la leçon précédente (souvent appelé l'algorithme des puissances en théorie algorithmique des nombres). En fait, nous n'avons besoin que des puissances de $a$ qui sont des puissances de 2, en particulier $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast},$ et nous pouvons obtenir ces puissances en élevant au carré de manière itérative $m-1$ fois. Chaque élévation au carré peut être réalisée par un circuit booléen de taille $O(n^2).$

En substance, ce que nous faisons ici revient à déléguer le problème consistant à itérer $M_a$ jusqu'à $2^{m-1}$ fois à un calcul classique efficace. Et c'est une chance que cela soit possible ! Pour un choix arbitraire de circuit quantique dans le problème d'estimation de phase, cela n'est en général pas possible — et dans ce cas, le coût résultant pour l'estimation de phase croît exponentiellement avec le nombre de qubits de contrôle $m.$

Solution étant donné un vecteur propre commode

Pour comprendre comment nous pouvons résoudre le problème de recherche d'ordre à l'aide de l'estimation de phase, commençons par supposer que nous exécutons la procédure d'estimation de phase sur l'opération $M_a$ en utilisant le vecteur propre $\vert\psi_1\rangle.$ Mettre la main sur ce vecteur propre n'est pas simple, comme nous le verrons, donc ce ne sera pas la fin de l'histoire — mais il est utile de commencer par là.

La valeur propre de $M_a$ correspondant au vecteur propre $\vert \psi_1\rangle$ est

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

C'est-à-dire, $\omega_r = e^{2\pi i \theta}$ pour $\theta = 1/r.$ Ainsi, si nous exécutons la procédure d'estimation de phase sur $M_a$ en utilisant le vecteur propre $\vert\psi_1\rangle,$ nous obtiendrons une approximation de $1/r.$ En calculant l'inverse, nous pourrons déterminer $r$ — à condition que notre approximation soit suffisamment bonne.

Plus précisément, lorsque nous exécutons la procédure d'estimation de phase en utilisant $m$ qubits de contrôle, ce que nous obtenons est un nombre $y\in\{0,\ldots,2^m-1\}.$ Nous prenons alors $y/2^m$ comme estimation de $\theta,$ qui vaut $1/r$ dans le cas présent. Pour déterminer ce qu'est $r$ à partir de cette approximation, la chose naturelle à faire est de calculer l'inverse de notre approximation et d'arrondir à l'entier le plus proche.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

Par exemple, supposons que $r = 6$ et que nous effectuions l'estimation de phase sur $M_a$ avec le vecteur propre $\vert\psi_1\rangle$ en utilisant $m = 5$ bits de contrôle. La meilleure approximation sur $5$ bits de $1/r = 1/6$ est $5/32,$ et nous avons de bonnes chances (environ $68\%$ dans ce cas) d'obtenir le résultat $y=5$ lors de l'estimation de phase. Nous avons

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

et en arrondissant à l'entier le plus proche nous obtenons $6,$ qui est la bonne réponse.

En revanche, si nous n'utilisons pas suffisamment de précision, nous risquons de ne pas obtenir la bonne réponse. Par exemple, si nous prenons $m = 4$ qubits de contrôle dans l'estimation de phase, nous pourrions obtenir la meilleure approximation sur $4$ bits de $1/r = 1/6,$ qui est $3/16.$ En prenant l'inverse, nous obtenons

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

et en arrondissant à l'entier le plus proche, nous obtenons la réponse incorrecte $5.$

Alors, de combien de précision avons-nous besoin pour obtenir la bonne réponse ? Nous savons que l'ordre $r$ est un entier, et intuitivement, ce dont nous avons besoin est d'une précision suffisante pour distinguer $1/r$ des possibilités voisines, notamment $1/(r+1)$ et $1/(r-1).$ Le nombre le plus proche de $1/r$ dont nous devons nous soucier est $1/(r+1),$ et la distance entre ces deux nombres est

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

Ainsi, si nous voulons nous assurer de ne pas confondre $1/r$ avec $1/(r+1),$ il suffit d'utiliser une précision suffisante pour garantir qu'une meilleure approximation $y/2^m$ de $1/r$ est plus proche de $1/r$ que de $1/(r+1).$ Si nous utilisons une précision suffisante pour que

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

de sorte que l'erreur soit inférieure à la moitié de la distance entre $1/r$ et $1/(r+1),$ alors $y/2^m$ sera plus proche de $1/r$ que de toute autre possibilité, y compris $1/(r+1)$ et $1/(r-1).$

Nous pouvons le vérifier comme suit. Supposons que

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

pour $\varepsilon$ satisfaisant

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

En prenant l'inverse, nous obtenons

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

En maximisant le numérateur et en minimisant le dénominateur, nous pouvons majorer l'écart par rapport à $r$ comme suit.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

Nous sommes à moins de $1/2$ de $r,$ donc, comme prévu, nous obtiendrons $r$ en arrondissant.

Malheureusement, comme nous ne savons pas encore ce qu'est $r,$ nous ne pouvons pas l'utiliser pour déterminer la précision dont nous avons besoin. Ce que nous pouvons faire à la place, c'est utiliser le fait que $r$ doit être inférieur à $N$ pour nous assurer d'utiliser une précision suffisante. En particulier, si nous utilisons une précision suffisante pour garantir que la meilleure approximation $y/2^m$ de $1/r$ satisfait

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

alors nous aurons une précision suffisante pour déterminer correctement $r$ lorsque nous prendrons l'inverse. Prendre $m = 2\operatorname{lg}(N)+1$ garantit une forte probabilité d'obtenir une estimation avec cette précision, à l'aide de la méthode décrite précédemment. (Prendre $m = 2\operatorname{lg}(N)$ suffit si l'on se contente d'une probabilité de succès minorée par 40%.)

Solution générale

Comme nous venons de le voir, si nous disposons du vecteur propre $\vert \psi_1 \rangle$ de $M_a,$ nous pouvons déterminer $r$ par estimation de phase, à condition d'utiliser suffisamment de qubits de contrôle pour le faire avec une précision suffisante. Malheureusement, il n'est pas facile de mettre la main sur le vecteur propre $\vert\psi_1\rangle,$ nous devons donc déterminer comment procéder.

Supposons un instant que nous procédions comme ci-dessus, mais avec le vecteur propre $\vert\psi_k\rangle$ à la place de $\vert\psi_1\rangle,$ pour n'importe quel choix de $k\in\{0,\ldots,r-1\}$ que nous décidons de considérer. Le résultat que nous obtenons de la procédure d'estimation de phase sera une approximation

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

En supposant que nous ne connaissons ni $k$ ni $r,$ cela peut ou non nous permettre de déterminer $r.$ Par exemple, si $k = 0$ nous obtiendrons une approximation $y/2^m$ de $0,$ ce qui malheureusement ne nous apprend rien. Cependant, il s'agit d'un cas inhabituel ; pour les autres valeurs de $k,$ nous pourrons au moins apprendre quelque chose sur $r.$

Nous pouvons utiliser un algorithme connu sous le nom d'algorithme des fractions continues pour transformer notre approximation $y/2^m$ en fractions voisines — y compris $k/r$ si l'approximation est suffisamment bonne. Nous n'expliquerons pas ici l'algorithme des fractions continues. Voici plutôt l'énoncé d'un résultat connu à propos de cet algorithme.

Fait

Étant donné un entier $N\geq 2$ et un nombre réel $\alpha\in(0,1),$ il existe au plus un choix d'entiers $u,v\in\{0,\ldots,N-1\}$ avec $v\neq 0$ et $\gcd(u,v)=1$ satisfaisant $\vert \alpha - u/v\vert < \frac{1}{2N^2}.$ Étant donné $\alpha$ et $N,$ l'algorithme des fractions continues trouve $u$ et $v,$ ou signale qu'ils n'existent pas. Cet algorithme peut être implémenté sous forme d'un circuit booléen de taille $O((\operatorname{lg}(N))^3).$

Si nous disposons d'une approximation très proche $y/2^m$ de $k/r,$ et que nous exécutons l'algorithme des fractions continues pour $N$ et $\alpha = y/2^m,$ nous obtiendrons $u$ et $v,$ tels que décrits dans ce résultat. Une analyse de ce résultat nous permet de conclure que

$$\frac{u}{v} = \frac{k}{r}.$$

Remarquons en particulier que nous n'apprenons pas nécessairement $k$ et $r,$ nous apprenons seulement $k/r$ sous forme irréductible.

Par exemple, comme nous l'avons déjà remarqué, nous n'apprendrons rien pour $k=0.$ Mais c'est la seule valeur de $k$ pour laquelle cela se produit. Lorsque $k$ est non nul, il peut avoir des facteurs communs avec $r,$ mais le nombre $v$ que nous obtenons à partir de l'algorithme des fractions continues doit au moins diviser $r.$

Cela est loin d'être évident, mais il est vrai que si nous avons la possibilité d'apprendre $u$ et $v$ pour $u/v = k/r$ avec $k\in\{0,\ldots,r-1\}$ choisi uniformément au hasard, alors nous avons de très bonnes chances de retrouver $r$ après seulement quelques échantillons. En particulier, si notre estimation de $r$ est le plus petit commun multiple de toutes les valeurs du dénominateur $v$ que nous observons, nous aurons raison avec une forte probabilité. Intuitivement, certaines valeurs de $k$ ne sont pas favorables car elles partagent des facteurs communs avec $r,$ et ces facteurs communs nous restent cachés lorsque nous apprenons $u$ et $v.$ Mais des choix aléatoires de $k$ ne sont pas susceptibles de cacher longtemps les facteurs de $r,$ et la probabilité de ne pas deviner correctement $r$ en prenant le plus petit commun multiple des dénominateurs observés décroît de façon exponentielle avec le nombre d'échantillons.

Il reste à traiter la question de la façon dont nous mettons la main sur un vecteur propre $\vert\psi_k\rangle$ de $M_a$ sur lequel exécuter la procédure d'estimation de phase. Il s'avère que nous n'avons en réalité pas besoin de les créer !

Ce que nous ferons à la place, c'est exécuter la procédure d'estimation de phase sur l'état $\vert 1\rangle,$ par lequel nous entendons le codage binaire sur $n$ bits du nombre $1,$ à la place d'un vecteur propre $\vert\psi\rangle$ de $M_a.$ Jusqu'à présent, nous n'avons parlé que d'exécuter la procédure d'estimation de phase sur un vecteur propre particulier, mais rien ne nous empêche d'exécuter la procédure sur un état d'entrée qui n'est pas un vecteur propre de $M_a,$ et c'est ce que nous faisons ici avec l'état $\vert 1\rangle.$ (Ce n'est pas un vecteur propre de $M_a$ à moins que $a=1,$ ce qui n'est pas un choix qui nous intéresse.)

La raison pour laquelle nous choisissons l'état $\vert 1\rangle$ à la place d'un vecteur propre de $M_a$ est que l'équation suivante est vraie.

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

Une façon de vérifier cette équation consiste à comparer les produits scalaires des deux membres avec chaque état de la base standard, en utilisant les formules mentionnées précédemment dans la leçon pour aider à évaluer les résultats du membre de droite. Par conséquent, nous obtiendrons exactement les mêmes résultats de mesure que si nous avions choisi $k\in\{0,\ldots,r-1\}$ uniformément au hasard et utilisé $\vert\psi_k\rangle$ comme vecteur propre.

Plus en détail, imaginons que nous exécutions la procédure d'estimation de phase avec l'état $\vert 1\rangle$ à la place de l'un des vecteurs propres $\vert\psi_k\rangle.$ Après application de la transformée de Fourier quantique inverse, il nous reste l'état

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

où

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

Le vecteur $\vert\gamma_k\rangle$ représente l'état des $m$ qubits du haut après application de l'inverse de la transformée de Fourier quantique sur ceux-ci.

Ainsi, en vertu du fait que $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ est un ensemble orthonormé, nous constatons qu'une mesure des $m$ qubits du haut produit une approximation $y/2^m$ de la valeur $k/r$ où $k\in\{0,\ldots,r-1\}$ est choisi uniformément au hasard. Comme nous en avons déjà discuté, cela nous permet de déterminer $r$ avec un haut degré de confiance après plusieurs exécutions indépendantes, ce qui était notre objectif.

Coût total

Le coût d'implémentation de chaque unitaire contrôlée $M_a^k$ est $O(n^2).$ Il y a $m$ opérations unitaires contrôlées, et nous avons $m = O(n),$ donc le coût total des opérations unitaires contrôlées est $O(n^3).$ De plus, nous avons $m$ portes de Hadamard (qui contribuent $O(n)$ au coût), et la transformée de Fourier quantique inverse contribue $O(n^2)$ au coût. Ainsi, le coût des opérations unitaires contrôlées domine le coût de l'ensemble de la procédure — qui est donc $O(n^3).$

Outre le circuit quantique lui-même, quelques calculs classiques doivent être effectués en cours de route. Cela inclut le calcul des puissances $a^k$ dans $\mathbb{Z}_N$ pour $k = 2, 4, 8, \ldots, 2^{m-1},$ qui sont nécessaires pour créer les portes unitaires contrôlées, ainsi que l'algorithme des fractions continues qui convertit les approximations de $\theta$ en fractions. Ces calculs peuvent être réalisés par des circuits booléens dont le coût total est $O(n^3).$

Comme c'est généralement le cas, toutes ces bornes peuvent être améliorées à l'aide d'algorithmes asymptotiquement plus rapides ; ces bornes supposent que nous utilisons des algorithmes standards pour les opérations arithmétiques de base.

Factorisation par recherche d'ordre

La toute dernière chose que nous devons aborder est la façon dont la résolution du problème de recherche d'ordre nous aide à factoriser. Cette partie est entièrement classique — elle n'a rien à voir spécifiquement avec le calcul quantique.

Voici l'idée de base. Nous voulons factoriser le nombre $N,$ et nous pouvons le faire récursivement. Plus précisément, nous pouvons nous concentrer sur la tâche consistant à scinder $N,$ c'est-à-dire trouver deux entiers quelconques $b,c\geq 2$ pour lesquels $N = bc.$ Ce n'est pas possible si $N$ est un nombre premier, mais nous pouvons tester efficacement si $N$ est premier à l'aide d'un algorithme de test de primalité d'abord, et si $N$ n'est pas premier nous tenterons de le scinder. Une fois que nous avons scindé $N,$ nous pouvons simplement récurer sur $b$ et $c$ jusqu'à ce que tous nos facteurs soient premiers et que nous obtenions la factorisation en nombres premiers de $N.$

Scinder les entiers pairs est facile : il suffit de donner $2$ et $N/2.$

Il est également facile de scinder les puissances parfaites, c'est-à-dire les nombres de la forme $N = s^j$ pour des entiers $s,j\geq 2,$ simplement en approximant les racines $N^{1/2},$ $N^{1/3},$ $N^{1/4},$ et ainsi de suite, et en vérifiant les entiers proches comme candidats pour $s.$ Nous n'avons pas besoin d'aller au-delà de $\log(N)$ étapes dans cette suite, car à partir de ce point la racine passe sous $2$ et ne révèle plus de candidats supplémentaires.

Il est heureux que nous puissions faire ces deux choses, car la recherche d'ordre ne nous aidera pas à factoriser les nombres pairs ni les puissances de nombres premiers, où le nombre $s$ se trouve être premier. Si $N$ est impair et n'est pas une puissance d'un nombre premier, en revanche, la recherche d'ordre nous permet de scinder $N.$

Algorithme probabiliste pour scinder un entier composé impair N qui n'est pas une puissance d'un nombre premier

1. Choisir aléatoirement $a\in\{2,\ldots,N-1\}.$

2. Calculer $d=\gcd(a,N).$

3. Si $d > 1,$ donner $b = d$ et $c = N/d$ et s'arrêter. Sinon, passer à l'étape suivante en sachant que $a\in\mathbb{Z}_N^{\ast}.$

4. Soit $r$ l'ordre de $a$ modulo $N.$ (C'est ici que nous avons besoin de la recherche d'ordre.)

5. Si $r$ est pair :

   5.1 Calculer $x = a^{r/2} - 1$ modulo $N$
   5.2 Calculer $d = \gcd(x,N).$
   5.3 Si $d>1,$ donner $b=d$ et $c = N/d$ et s'arrêter.

6. Si ce point est atteint, l'algorithme n'a pas réussi à trouver un facteur de $N.$

Une exécution de cet algorithme peut échouer à trouver un facteur de $N.$ Cela se produit précisément dans deux situations :

• L'ordre de $a$ modulo $N$ est impair.
• L'ordre de $a$ modulo $N$ est pair et $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1.$

En utilisant des notions de base en théorie des nombres, on peut prouver que, pour un choix aléatoire de $a,$ avec une probabilité d'au moins $1/2,$ aucun de ces événements ne se produit. En fait, la probabilité que l'un ou l'autre de ces événements se produise est d'au plus $2^{-(m-1)}$ où $m$ est le nombre de facteurs premiers distincts de $N,$ ce qui explique pourquoi l'hypothèse selon laquelle $N$ n'est pas une puissance d'un nombre premier est nécessaire. (L'hypothèse selon laquelle $N$ est impair est également nécessaire pour que ce fait soit vrai.)

Cela signifie que chaque exécution a au moins 50% de chances de scinder $N.$ Par conséquent, si nous exécutons l'algorithme $t$ fois, en choisissant $a$ aléatoirement à chaque fois, nous réussirons à scinder $N$ avec une probabilité d'au moins $1 - 2^{-t}.$

L'idée de base derrière l'algorithme est la suivante. Si nous disposons d'un choix de $a$ pour lequel l'ordre $r$ de $a$ modulo $N$ est pair, alors $r/2$ est un entier et nous pouvons considérer les nombres

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{et} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

En utilisant la formule $Z^2 - 1 = (Z+1)(Z-1),$ nous concluons que

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

Or, nous savons que $a^r \; (\textrm{mod}\; N) = 1$ par définition de l'ordre — ce qui revient à dire que $N$ divise exactement $a^r - 1.$ Cela signifie que $N$ divise exactement le produit

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

Pour que cela soit vrai, tous les facteurs premiers de $N$ doivent également être des facteurs premiers de $a^{r/2} - 1$ ou de $a^{r/2} + 1$ (ou des deux) — et pour un choix aléatoire de $a,$ il s'avère peu probable que tous les facteurs premiers de $N$ divisent l'un des deux termes sans qu'aucun ne divise l'autre. Sinon, dès lors que certains des facteurs premiers de $N$ divisent le premier terme et que d'autres divisent le second terme, nous pourrons trouver un facteur non trivial de $N$ en calculant le PGCD avec le premier terme.