Algorithme de Shor

Nous allons maintenant nous intéresser au problème de la factorisation des nombres 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 allons obtenir est l' algorithme de Shor pour la factorisation des nombres 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 discuter d'un problème intermédiaire connu sous le nom de problème de recherche d'ordre et nous verrons comment l'estimation de phase apporte une solution à ce problème. Nous verrons ensuite comment une solution efficace au problème de recherche d'ordre nous permet d'obtenir une solution efficace au problème de factorisation des nombres entiers. (Lorsqu'une solution à un problème permet de résoudre un autre problème de ce type, on dit que le second problème se réduit au premier - dans ce cas, nous réduisons la factorisation des nombres entiers à la recherche d'ordre) Cette deuxième partie de l'algorithme de Shor ne fait pas du tout appel à l'informatique quantique; elle est tout à fait classique. L'informatique quantique n'est nécessaire que pour résoudre les problèmes de recherche d'ordre.

---

Le problème de la recherche de commandes

Quelques notions élémentaires de théorie des nombres

Pour expliquer le problème de la recherche d'ordre et la manière dont il peut être résolu à l'aide de l'estimation de phase, il sera utile de commencer par quelques concepts de base de la théorie des nombres et d'introduire quelques notations pratiques en cours de route.

Pour commencer, pour tout entier positif donné $N,$, définissez 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.

Il s'agit d'ensembles de nombres, mais nous pouvons considérer qu'il ne s'agit pas seulement d'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 acceptons de toujours prendre nos réponses modulo $N$ (c'est-à-dire diviser par $N$ et prendre le reste comme résultat), nous resterons toujours dans cet ensemble lorsque nous effectuerons ces opérations. Les deux opérations spécifiques que sont l'addition et la multiplication, toutes deux effectuées modulo $N,$, font de $\mathbb{Z}_N$ 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 ensemble, nous obtenons $3\cdot 5 = 15,$ qui laisse un reste de $1$ lorsqu'il est divisé par $7.$ Nous exprimons parfois cela de la manière suivante.

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

Mais nous pouvons aussi écrire simplement $3 \cdot 5 = 1,$ à condition qu'il ait été précisé que nous travaillons en $\mathbb{Z}_7,$, pour que notre notation soit la plus simple possible.

A titre d'exemple, voici les tables d'addition et de multiplication de $\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 éléments $N$ de $\mathbb{Z}_N,$, les éléments $a\in\mathbb{Z}_N$ qui satisfont à $\gcd(a,N) = 1$ sont particuliers. L'ensemble contenant ces éléments est souvent désigné par une étoile.

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

Si nous concentrons notre attention 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. Un fait fondamental concernant ces ensembles (et les groupes finis en général) est que si l'on choisit n'importe quel élément $a\in\mathbb{Z}_N^{\ast}$ et que l'on multiplie de façon répétée $a$ par lui-même, on finira toujours par obtenir le nombre $1.$

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

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

Prenons un deuxième exemple $N = 21.$ Si nous parcourons les nombres de $0$ à $20,$, ceux dont le PGCD est égal à $1$ avec $21$ 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 à l'intérieur de $\mathbb{Z}_{21}$ pour toutes ces équations, que nous n'avons pas pris la peine d'écrire - nous les considérons comme implicites pour éviter d'encombrer les choses. Nous continuerons à le faire pendant le reste de la leçon.

Problématique et lien avec l'estimation de phase

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

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

Alternativement, en termes de notation que nous venons d'introduire ci-dessus, 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{(for each $x\in\mathbb{Z}_N$)}$$

Pour être clair, nous effectuons la multiplication sur $\mathbb{Z}_N,$, il est donc implicite que nous prenons le produit modulo $N$ à l'intérieur du ket du côté droit de l'équation.

Par exemple, si nous prenons $N = 15$ et $a=2,$, 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 à condition que $\gcd(a,N)=1;$ mélange les éléments de la base standard $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$, de sorte qu'en tant que 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 est de penser à l'ordre $r$ de $a$ modulo $N,$ et de 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 chaque élément $a\in\mathbb{Z}_N^{\ast}$, il existe toujours un élément unique $b\in\mathbb{Z}_N^{\ast}$ qui satisfait aux conditions suivantes $ab=1.$ Nous désignons cet élément $b$ par $a^{-1},$ et il peut être calculé efficacement; une extension de l'algorithme GCD d'Euclide le fait avec un coût quadratique en $\operatorname{lg}(N).$ Et donc

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

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

Réfléchissons 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 le voir, cette hypothèse nous indique que $M_a$ est unitaire.

Il y a $N$ valeurs propres de $M_a,$, y compris éventuellement la même valeur propre répétée plusieurs fois, et en général il y a une certaine liberté dans le choix des vecteurs propres correspondants - mais nous n'aurons 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 elle n'est pas modifiée lorsque nous la 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 base standard $\vert a^k \rangle$ est déplacé vers $\vert a^{k+1} \rangle$ pour $k\leq r-1,$ et $\vert a^{r-1} \rangle$ est déplacé à nouveau vers $\vert 1\rangle.$ D'un point de vue informel, c'est comme si nous remuions lentement le site $\vert \psi_0 \rangle,$, mais qu'il était déjà complètement remué et que rien ne changeait.

Voici un autre exemple de vecteur propre de $M_a.$ Celui-ci est 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}}$$

Nous pouvons également écrire ce vecteur en utilisant une sommation comme suit.

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

Ici, le nombre complexe $\omega_r = e^{2\pi i/r}$ apparaît naturellement, en raison de la façon dont la multiplication par $a$ fonctionne 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, parce que $\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 de vecteurs propres/valeurs propres 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 ce faire, nous devons implémenter efficacement non seulement $M_a$ avec un circuit quantique, 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 de la procédure d'estimation de la phase. Nous expliquons ici comment procéder, et nous déterminerons plus tard le degré de précision nécessaire.

Commençons par l'opération $M_a$ en elle-même. Naturellement, comme nous travaillons avec le modèle de circuit quantique, 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,$ et le nombre de bits dont nous avons besoin est donc

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

Voici maintenant une définition précise de la façon dont $M_a$ est défini comme une opération $n$ -qubit.

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

Le fait est que, même si nous ne nous intéressons qu'au fonctionnement de $M_a$ pour $\vert 0\rangle,\ldots,\vert N-1\rangle,$, nous devons spécifier son fonctionnement pour les états de base standard restants de $2^n - N$ - et nous devons le faire d'une manière qui nous permette toujours d'obtenir une opération unitaire. Définir $M_a$ de manière à ce qu'il n'affecte en rien les états de base standard restants permet d'atteindre cet objectif.

En utilisant les algorithmes de multiplication et de division des entiers présentés dans la leçon précédente, ainsi que la méthodologie pour les implémenter de manière réversible et sans déchets, nous pouvons construire un circuit quantique qui effectue $M_a,$ pour n'importe quel choix de $a\in\mathbb{Z}_N^{\ast},$ à un coût donné $O(n^2).$ Voici une façon de procéder.

1. Construire un circuit pour effectuer 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. On obtient ainsi un circuit de taille $O(n^2).$

2. Permuter les deux systèmes $n$ -qubit en utilisant $n$ swap gates pour permuter les qubits individuellement.

3. De la même manière que pour la première étape, construisez 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$ en $\mathbb{Z}_N^{\ast}.$

En initialisant les qubits inférieurs $n$ et en composant les trois étapes, nous obtenons cette transformation :

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 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 d'espace de travail, mais ils sont ramenés à leur état initialisé à la fin, ce qui nous permet d'utiliser ces circuits pour l'estimation de la phase. Le coût total du circuit obtenu est de $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}.$ Autrement dit, pour toute puissance $k$ que nous choisissons, nous pouvons créer un circuit pour $M_a^k$ non pas en itérant $k$ fois le circuit pour $M_a,$ mais plutôt en calculant $b = a^k \in \mathbb{Z}_N^{\ast}$ et en utilisant ensuite le circuit pour $M_b.$

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

En fait, ce que nous faisons ici, c'est décharger le problème de l'itération de $M_a$ jusqu'à $2^{m-1}$ fois sur un calcul classique efficace. Et c'est une chance que cela soit possible! Pour un choix arbitraire de circuit quantique dans le problème de l'estimation de phase, il est peu probable que cela soit possible - et dans ce cas, le coût résultant de l'estimation de phase croît de manière exponentielle en fonction du nombre de qubits de contrôle $m.$

Solution donnée un vecteur propre pratique

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.$ Il n'est pas facile de mettre la main sur ce vecteur propre, et ce n'est donc 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 la réciproque, nous pourrons apprendre $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 hypothèse pour $\theta,$, qui est $1/r$ dans le cas présent. Pour déterminer la valeur de $r$ à partir de cette approximation, la chose naturelle à faire est de calculer la réciproque 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 nous effectuons une estimation de phase sur $M_a$ avec le vecteur propre $\vert\psi_1\rangle$ en utilisant les bits de contrôle $m = 5$. La meilleure approximation $5$ -bit 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$ à partir de l'estimation de la phase. Nous avons

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

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

En revanche, si nous ne sommes pas assez précis, 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 la phase, nous pourrions obtenir la meilleure approximation $4$ -bit de $1/r = 1/6,$ qui est $3/16.$ En prenant la réciproque, on obtient

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

et en arrondissant à l'entier le plus proche, on obtient une réponse incorrecte de $5.$

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

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

Ainsi, si nous voulons être sûrs de ne pas confondre $1/r$ avec $1/(r+1),$, il suffit d'utiliser suffisamment de précision pour garantir qu'une meilleure approximation entre $y/2^m$ et $1/r$ est plus proche de $1/r$ qu'elle ne l'est de $1/(r+1).$ Si nous utilisons suffisamment de précision 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 la réciproque, on obtient

$$\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 déterminer la distance qui nous sépare de $r$ de la manière suivante.

$$\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,$ et, comme prévu, nous obtiendrons $r$ lorsque nous arrondirons.

Malheureusement, comme nous ne savons pas encore ce qu'est $r$, nous ne pouvons pas l'utiliser pour déterminer le degré de précision dont nous avons besoin. Nous pouvons plutôt utiliser le fait que $r$ doit être plus petit que $N$ pour nous assurer que nous utilisons suffisamment de précision. 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 suffisamment de précision pour déterminer correctement $r$ lorsque nous prenons la réciproque. En prenant $m = 2\operatorname{lg}(N)+1$, on s'assure d'avoir de grandes chances d'obtenir une estimation avec cette précision en utilisant la méthode décrite précédemment. (Prendre $m = 2\operatorname{lg}(N)$ est suffisant si nous sommes à l'aise avec une limite inférieure de 40 % pour la probabilité de succès)

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 apprendre $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,$ et nous devons donc trouver une façon de procéder.

Supposons momentanément que nous procédions de la même manière que ci-dessus, à l'exception du vecteur propre $\vert\psi_k\rangle$ à la place de $\vert\psi_1\rangle,$ pour tout choix de $k\in\{0,\ldots,r-1\}$ auquel nous choisissons de penser. Le résultat obtenu par la procédure d'estimation de la phase sera une approximation

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

En partant de l'hypothèse que nous ne connaissons ni $k$ ni $r,$, cela nous permet ou non d'identifier le nom du site $r.$ Par exemple, si $k = 0$, nous obtiendrons une approximation de $y/2^m$ à $0,$, ce qui ne nous dit malheureusement rien. Il s'agit toutefois d'un cas inhabituel; pour d'autres valeurs de $k,$, nous serons au moins en mesure d'apprendre quelque chose à propos de $r.$

Nous pouvons utiliser un algorithme connu sous le nom d' algorithme de fraction continue pour transformer notre approximation $y/2^m$ en fractions proches - y compris $k/r$ si l'approximation est suffisamment bonne. Nous n'expliquerons pas ici l'algorithme de la fraction continue. Au lieu de cela, voici l'énoncé d'un fait connu à propos de cet algorithme.

É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 la forme d'un circuit booléen de taille $O((\operatorname{lg}(N))^3).$

Si nous avons une approximation très proche de $y/2^m$ à $k/r,$ et que nous exécutons l'algorithme de la fraction continue pour $N$ et $\alpha = y/2^m,$, nous obtiendrons $u$ et $v,$ tels qu'ils sont décrits dans le fait. L'analyse des faits permet de conclure que

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

Remarquez en particulier que nous n'apprenons pas nécessairement $k$ et $r,$, mais seulement $k/r$ dans les termes les plus bas.

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

C'est loin d'être évident, mais il est vrai que si nous avons la capacité d'apprendre $u$ et $v$ pour $u/v = k/r$ pour $k\in\{0,\ldots,r-1\}$ choisis uniformément au hasard, alors il est très probable que nous puissions retrouver $r$ après seulement quelques échantillons. En particulier, si notre estimation de $r$ est le multiple le moins commun 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 bonnes parce qu'elles partagent des facteurs communs avec $r,$ et que ces facteurs communs nous sont cachés lorsque nous apprenons $u$ et $v.$ Mais les choix aléatoires de $k$ ne sont pas susceptibles de cacher les facteurs de $r$ pendant longtemps, et la probabilité que nous ne devinions pas $r$ correctement en prenant le plus petit multiple commun des dénominateurs que nous observons diminue de façon exponentielle dans le nombre d'échantillons.

Il reste à déterminer comment mettre la main sur un vecteur propre $\vert\psi_k\rangle$ de $M_a$ sur lequel exécuter la procédure d'estimation de la phase. En fait, nous n'avons pas besoin de les créer!

Nous allons plutôt exécuter la procédure d'estimation de phase sur l'état $\vert 1\rangle,$, c'est-à-dire le codage binaire $n$ du nombre $1,$ à la place d'un vecteur propre $\vert\psi\rangle$ de $M_a.$ Jusqu'à présent, nous n'avons parlé que de l'exécution de 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.$ (Il ne s'agit pas d'un vecteur propre de $M_a$ à moins que $a=1,$ ne soit un choix qui ne nous intéresse pas)

Le choix de l'état $\vert 1\rangle$ au lieu d'un vecteur propre de $M_a$ se justifie par le fait 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 est de comparer les produits intérieurs des deux côtés avec chaque état de base standard, en utilisant les formules mentionnées précédemment dans la leçon pour aider à évaluer les résultats du côté droit. 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 précisément, imaginons que nous exécutions la procédure d'estimation de la phase avec l'état $\vert 1\rangle$ à la place de l'un des vecteurs propres $\vert\psi_k\rangle.$ Après l'exécution de la transformée de Fourier quantique inverse, nous obtenons l'état suivant

$$\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 qubits supérieurs $m$ après que l'inverse de la transformée de Fourier quantique a été effectué sur eux.

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 qubits supérieurs $m$ donne 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 l'avons déjà mentionné, cela nous permet d'apprendre $r$ avec un degré élevé de confiance après plusieurs exécutions indépendantes, ce qui était notre objectif.

Coût total

Le coût de mise en œuvre de chaque opération unitaire contrôlée $M_a^k$ est le suivant $O(n^2).$ Il y a $m$ opérations unitaires contrôlées, et nous avons $m = O(n),$ donc le coût total pour les opérations unitaires contrôlées est de $O(n^3).$ En outre, 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 de $O(n^3).$

Outre le circuit quantique lui-même, quelques calculs classiques doivent être effectués en cours de route. Il s'agit notamment de calculer les 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 de fraction continue qui convertit les approximations de $\theta$ en fractions. Ces calculs peuvent être effectués par des circuits booléens avec un coût total de $O(n^3).$

Comme d'habitude, toutes ces limites peuvent être améliorées à l'aide d'algorithmes asymptotiquement rapides; ces limites supposent l'utilisation d'algorithmes standard pour les opérations arithmétiques de base.

---

Affacturage par recherche de commandes

La toute dernière chose que nous devons discuter est la façon dont la résolution du problème de recherche d'ordre nous aide à factoriser. Cette partie est tout à fait classique - elle n'a rien à voir avec l'informatique quantique.

Voici l'idée de base. Nous voulons factoriser le nombre $N,$ et nous pouvons le faire de manière récursive. Plus précisément, nous pouvons nous concentrer sur la tâche consistant à diviser $N,$, ce qui signifie trouver deux entiers $b,c\geq 2$ pour lesquels $N = bc.$ Cela n'est pas possible si $N$ est un nombre premier, mais nous pouvons tester efficacement si $N$ est premier en utilisant d'abord un algorithme de test de primalité, et si $N$ n'est pas premier, nous essaierons de le diviser. Une fois que nous avons divisé $N,$, il nous suffit de récidiver sur $b$ et $c$ jusqu'à ce que tous nos facteurs soient premiers et que nous obtenions la factorisation première de $N.$

Il est facile de diviser les entiers pairs : il suffit de sortir $2$ et $N/2.$

Il est également facile de diviser les puissances parfaites, c'est-à-dire les nombres de la forme $N = s^j$ pour les entiers $s,j\geq 2,$, en approximant les racines et ainsi de suite approximant les racines $N^{1/2},$ $N^{1/3},$ $N^{1/4},$ et ainsi de suite, et en vérifiant les entiers proches en tant que suspects pour les puissances parfaites $s.$ Nous n'avons pas besoin d'aller plus loin que $\log(N)$ pas dans cette séquence, parce qu'à ce stade, la racine tombe en dessous de $2$ et ne révèlera pas de candidats supplémentaires.

C'est une bonne chose que nous puissions faire ces deux choses, car la recherche d'ordre ne nous aidera pas à factoriser les nombres pairs ou les puissances premières, lorsque le nombre $s$ est un nombre premier. Si $N$ est impair et n'est pas une puissance première, la recherche d'ordre nous permet de diviser $N.$

1. Choisir au hasard $a\in\{2,\ldots,N-1\}.$

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

3. Si $d > 1$, alors il faut éditer $b = d$ et $c = N/d$ et s'arrêter. Sinon, passez à 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 d'une recherche d'ordre)

5. Si $r$ est égal :

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

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

L'exécution de cet algorithme peut échouer à trouver un facteur de $N.$ Plus précisément, cela se produit 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 la théorie des nombres de base, 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 événement se produise est au plus de $2^{-(m-1)}$ pour $m$ étant le nombre de facteurs premiers distincts de $N,$ c'est pourquoi l'hypothèse selon laquelle $N$ n'est pas une puissance première 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 d'aboutir à une scission $N.$ Par conséquent, si nous exécutons l'algorithme $t$ fois, en choisissant au hasard $a$ à chaque fois, nous réussirons à diviser $N$ avec une probabilité d'au moins $1 - 2^{-t}.$

L'idée de base de l'algorithme est la suivante. Si nous avons 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{and} \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.$$

Maintenant, nous savons que $a^r \; (\textrm{mod}\; N) = 1$ par la définition de l'ordre - ce qui est une autre façon de dire que $N$ divise également le produit $a^r - 1.$ Cela signifie que $N$ divise également 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 $a^{r/2} + 1$ (ou des deux) - et pour une sélection aléatoire de $a$, il s'avère improbable que tous les facteurs premiers de $N$ divisent l'un des termes et qu'aucun ne divise l'autre. Sinon, tant que certains des facteurs premiers de $N$ divisent le premier terme et que certains divisent le second terme, nous pourrons trouver un facteur non trivial de $N$ en calculant le PGCD avec le premier terme.