Algorithme de Shor

1. Prendre un nombre pseudo-aléatoire a < N
2. Calculer PGCD(a, N). Ceci peut être effectué par l'utilisation de l'algorithme d'Euclide.
3. Si PGCD(a, N) ≠ 1, alors c'est un facteur non trivial de N, ce qui donne une solution au problème.
4. Sinon, utiliser le sous-programme de recherche de période (ci-dessous) pour trouver r, la période de la fonction ${\displaystyle f:x\mapsto a^{x}\ {\mbox{mod}}\ N}$, c’est-à-dire le plus petit entier r pour lequel ${\displaystyle f(x+r)=f(x)}$.
5. Si r est impair, retourner à l'étape 1.
6. Si a ^r/2 ≡ −1 (mod N), retourner à l'étape 1.
7. Les facteurs de N sont PGCD(a^r/2 ± 1, N), ce qui résout le problème.

1. Commencer avec des registres d'entrée et de sortie de chacun log₂N qubits, et les initialiser à :

   ${\displaystyle N^{-1/2}\sum _{x}\left|x\right\rangle \left|0\right\rangle }$

   où x va de 0 à N – 1.

2. Construire f(x) comme une fonction quantique et l'appliquer à l'état précédent, pour obtenir

   ${\displaystyle N^{-1/2}\sum _{x}\left|x\right\rangle \left|f(x)\right\rangle }$

3. Appliquer la transformée de Fourier quantique au registre d'entrée. La transformée de Fourier quantique sur N points est définie par :

   ${\displaystyle U_{QFT}\left|x\right\rangle =N^{-1/2}\sum _{y}e^{2\pi ixy/N}\left|y\right\rangle }$

   Ce qui donne l'état suivant :

   ${\displaystyle N^{-1}\sum _{x}\sum _{y}e^{2\pi ixy/N}\left|y\right\rangle \left|f(x)\right\rangle }$

4. Effectuer une mesure. On obtient ainsi une certaine valeur y dans le registre d'entrée et ${\displaystyle f(x_{0})}$ dans le registre de sortie. Comme f est périodique, la probabilité de mesurer un certain y est donnée par

   ${\displaystyle \left|N^{-1}\sum _{x:\,f(x)=f(x_{0})}e^{2\pi ixy/N}\right|^{2}=\left|N^{-1}\sum _{b}e^{2\pi i(x_{0}+rb)y/N}\right|^{2}}$

   Le calcul montre que cette probabilité est plus haute quand yr/N est proche d'un entier.

5. Mettre y/N sous forme irréductible, et extraire le dénominateur r′, qui est un candidat pour r.
6. Vérifier si f(x) = f(x + r′). Si c'est le cas, c'est terminé.
7. Autrement, obtenir plus de candidats pour r en utilisant des valeurs proches de y, ou multiples de r′. Si un autre candidat marche, c'est terminé.
8. Sinon, retourner à l'étape 1 du sous-programme.

L'algorithme est composé de deux parties. La première partie transforme le problème de factorisation en un problème de recherche de période d'une fonction et peut être implémentée de façon classique. La seconde partie trouve la période en utilisant la transformée de Fourier quantique et est responsable de l'accélération quantique.

Les entiers inférieurs à N et premiers avec N forment un groupe fini muni de la multiplication modulo N, qui est typiquement noté (Z/NZ)^×. La fin de l'étape 3 permet de déterminer un entier a dans ce groupe. Comme le groupe est fini, a possède (d'après le théorème d'Euler) un ordre fini r, défini comme plus petit entier positif tel que

${\displaystyle a^{r}\equiv 1\ {\mbox{mod}}\ N}$

Par conséquent, N | (a ^r – 1). Supposons qu’il soit possible de déterminer r, et que celui-ci est pair. Alors

${\displaystyle a^{r}-1=(a^{r/2}-1)(a^{r/2}+1)\equiv 0\ {\mbox{mod}}\ N}$, d’où ${\displaystyle N\ |(a^{r/2}-1)(a^{r/2}+1)}$

r est le plus petit entier positif tel que N divise (a ^r – 1), donc N ne peut pas diviser (a ^{r / 2} – 1). Si N ne divise pas non plus (a ^{r / 2} + 1), alors N doit avoir un facteur commun non-trivial avec chacun des (a ^{r / 2} – 1) et (a ^{r / 2} + 1).

Preuve : notons (a ^{r / 2} – 1) et (a ^{r / 2} + 1) par u et v respectivement. N | uv, donc kN = uv pour un certain entier k. Supposons que PGCD(u, N) = 1 ; alors mu + nN = 1 pour certains entiers m et n (identité de Bézout). En multipliant de part et d’autre par v, l’on trouve que mkN + nvN = v, donc N | v. Par contradiction, PGCD(u, N) ≠ 1. Par un argument similaire, PGCD(v, N) ≠ 1.

Ceci fournit une factorisation de N. Si N est le produit de deux nombres premiers, elle est la seule factorisation possible.

L'algorithme de recherche de période de Shor est fortement relié à la capacité d'un calculateur quantique d'être dans de nombreux états simultanément. Les physiciens appellent ce comportement une « superposition » d'états. Pour calculer la période d'une fonction f, nous évaluons la fonction en tous ses points simultanément.

Pourtant, la physique quantique ne nous permet pas d'accéder à toute l'information directement. Une mesure fournira seulement une parmi toutes les valeurs possibles en détruisant toutes les autres. Par conséquent nous avons à transformer avec précaution la superposition en un autre état qui retournera la réponse correcte avec une haute probabilité. Ceci est accompli par la transformée de Fourier quantique.

Shor eut ainsi à résoudre trois problèmes d'« implémentation ». Tous ont été implémentés « rapidement », ce qui veut dire qu'ils peuvent être implémentés avec un nombre de portes quantiques qui est polynomial en ${\displaystyle \log N}$.

1. Créer une superposition d'états. Ceci peut être fait en appliquant des portes d'Hadamard à tous les qubits dans le registre d'entrée. Une autre approche serait d'utiliser la transformée de Fourier quantique (voir ci-dessous).
2. Implémenter la fonction f comme une transformation quantique. Pour accomplir cela, Shor utilisa l'élévation au carré pour sa transformation d'exponentiation modulaire.
3. Exécuter une transformation de Fourier quantique. En utilisant les portes NON contrôlées et les portes qubit à rotation unique, Shor conçut un circuit pour la transformée de Fourier quantique qui utilise juste ${\displaystyle O((\log N)^{2})}$ portes.

Après toutes ces transformations, une mesure fournira une approximation de la période r. Pour simplifier, assurons-nous qu'il existe un y tel que yr/N soit un entier. Alors la probabilité de mesurer y est 1. Pour voir cela, notons qu'alors ${\displaystyle e^{2\pi ibyr/N}=1\,}$ pour tous les entiers b. Par conséquent, la somme qui nous donne la probabilité de mesurer y sera de N/r comme b prend globalement N/r valeurs et ainsi, la probabilité est 1/r. Il existe r y tels que yr/N soit un entier donc les probabilités totalisent 1.

Note : une autre manière d'expliquer l'algorithme de Shor est de noter que c'est juste l'algorithme d'estimation de phase quantique déguisé.

• (en) Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. « quant-ph/9508027 », texte en accès libre, sur arXiv.
• (en) Michael A. Nielsen et Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2000
  Un livre généraliste sur le calcul quantique

• Information quantique
• Algorithme de Grover
• Algorithme de Deutsch-Jozsa

• Une explication de l'algorithme de Shor, sans calculs, sur le blog de Scott Aaronson