Algorithme de Shor

En arithmétique modulaire, l'algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O 3) et en espace O, appelé en l'honneur de Peter Shor.

Catégories :

Informatique quantique - Mécanique quantique - Physique quantique - Algorithme de factorisation des entiers

Source image : interstices.info
Cette image est un résultat de recherche de Google Image. Elle est peut-être réduite par rapport à l'originale et/ou protégée par des droits d'auteur.

Page(s) en rapport avec ce sujet :

L'algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O ( (log N) 3) et en espace O (log N), appelé en l'honneur de Peter Shor.... (source : dictionnaire.sensagent)
Comment se présentera l'ordinateur quantique dont certains prévoient des ... Identifier la factorisation grâce à l'algorithme de Shor est revenu à contrôler... (source : editions-bayol)
Il faudra par conséquent de l'ordre de n3 opérations pour factoriser P : la complexité de l'algorithme de Shor est polynomiale, tandis que celle du meilleur algorithme... (source : interstices)

En arithmétique modulaire, l'algorithme de Shor est un algorithme quantique pour factoriser un nombre N en temps O $( (l o g N) 3)$ et en espace $O (l o g N)$ , appelé en l'honneur de Peter Shor.

Énormément de cryptodispositifs à clé publique, tels que le RSA, deviendraient cassables par un tiers si l'algorithme de Shor était un jour programmé dans un calculateur quantique pratique. Un message chiffré avec RSA peut être déchiffré par factorisation de sa clé publique N, qui est le produit de deux nombres premiers. En l'état actuel des connaissances, il n'existe pas d'algorithme classique capable de faire cela en temps $O ( (l o g N) k)$ pour n'importe quel k, par conséquent, les algorithmes classiques connus deviennent rapidement impraticables lorsque N augmente, à la différence de l'algorithme de Shor qui peut casser le RSA en temps polynomial. Il a été aussi étendu pour attaquer énormément d'autres cryptodispositifs à clé publique.

Comme l'ensemble des algorithmes pour calculateur quantique, l'algorithme de Shor est probabiliste : il donne la réponse correcte avec une haute probabilité et la probabilité d'échec peut être diminuée en répétant l'algorithme.

L'algorithme de Shor fut utilisé en 2001 par un groupe d'IBM, qui factorisa 15 en 3 et 5, en utilisant un calculateur quantique de 7 qubits.

Procédure

Le problème que nous allons essayer de résoudre est le suivant, soit un entier donné N, nous essayons de trouver un autre entier p compris entre 1 et N qui divise N.

L'algorithme de Shor consiste en deux parties :

Une réduction du problème de factorisation en un problème de recherche d'ordre, qui peut être effectué sur un ordinateur classique.
Un algorithme quantique pour résoudre le problème de recherche d'ordre.

Partie classique

Prendre un nombre pseudo-aléatoire a < N
Calculer le PGCD (a, N). Ceci peut être effectué par l'utilisation de l'algorithme d'Euclide.
Si PGCD (a, N) ≠ 1, alors c'est un facteur non-trivial de N, par conséquent effectué.
Autrement, utiliser la sous-routine de recherche de période (ci-dessous) pour trouver r, la période de la fonction suivante :
$f(x) = aˆx\ \mbox{mod}\ N$ ,
c. a. d. le plus petit entier r pour lequel $f (x + r) = f (x)$ .
Si r est impair, retourner à l'étape 1.
Si a ^r/2 ≡ -1 (mod N), retourner à l'étape 1.
Les facteurs de N sont PGCD (a^r/2 ± 1, N). Effectué.

Partie quantique : sous-routine de recherche de période

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

$Nˆ{-1/2} \sum_x \left|x\right\rangle \left|0\right\rangle$

où x va de 0 à N - 1.
Construire f (x) comme une fonction quantique et l'appliquer à l'état précédent, pour obtenir

$Nˆ{-1/2} \sum_x \left|x\right\rangle \left|f(x)\right\rangle$
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 :

$U_{QFT} \left|x\right\rangle = Nˆ{-1/2} \sum_y eˆ{2\pi i x y/N} \left|y\right\rangle$

Ce qui donne l'état suivant :

$Nˆ{-1} \sum_x \sum_y eˆ{2\pi i x y/N} \left|y\right\rangle \left|f(x)\right\rangle$
Effectuer une mesure. On obtient ainsi une certaine valeur y dans le registre d'entrée et $f (x 0)$ dans le registre de sortie. Comme f est périodique, la probabilité de mesurer un certain y est donnée par

$\left| Nˆ{-1} \sum_{x:\, f(x)=f(x_0)} eˆ{2\pi i x y/N} \right|ˆ2 = \left| Nˆ{-1} \sum_{b} eˆ{2\pi i (x_0 + r b) y/N} \right|ˆ2$

Le calcul montre que cette probabilité est plus haute lorsque yr/N est proche d'un entier.
Mettre y/N sous forme irréductible, et extraire le dénominateur r′, qui est un candidat pour r.
Vérifier si f (x) = f (x + r′). Si c'est le cas, c'est terminé.
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é.
Sinon, retourner à l'étape 1 de la sous-routine.

Explication de l'algorithme

L'algorithme se compose 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.

I. Obtenir des facteurs à partir de la période

Les entiers inférieurs à N et premiers avec N forment un groupe fini pourvu de la multiplication modulo N, qui est typiquement noté (Z/NZ) ^×. Par la fin de l'étape 3, nous avons un entier a dans ce groupe. Comme le groupe est fini, a doit avoir un ordre fini r, le plus petit entier positif tel que

$aˆr \equiv 1\ \mbox{mod}\ N$

Donc, N | (a ^r - 1). Supposons que nous somme capable d'obtenir r et qu'il est pair. Alors

$aˆr - 1 = (aˆ{r/2} - 1) (aˆ{r/2} + 1) \equiv 0\ \mbox{mod}\ N$

$\Rightarrow N\ | (aˆ{r/2} - 1) (aˆ{r/2} + 1)$

r est le plus petit entier positif tel que a ^r ≡ 1, par conséquent 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 : Pour simplifier, notons (a ^{r / 2} - 1) et (a ^{r / 2} + 1) par u et v respectivement. N | uv, par conséquent kN = uv pour certain entier k. Supposons que PGCD (u, N) = 1; alors mu + nN = 1 pour certains entiers m et n (ceci est une propriété du PGCD. ) En multipliant les deux cotés par v, nous trouvons que mkN + nvN = v, par conséquent N | v. Par contradiction, PGCD (u, N) ≠ 1. Par un argument identique, PGCD (v, N) ≠ 1.

Ceci nous apporte une factorisation de N. Si N est le produit de deux nombres premiers, ceci est la seule factorisation envisageable.

II. Trouver la période

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 nomment 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 apportera uniquement une parmi l'ensemble des valeurs envisageables en détruisant l'ensemble des autres. Donc nous avons à transformer avec précaution la superposition en un autre état qui retournera la réponse correcte avec une haute probabilité. Ceci est achevé 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 $log N$ .

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

Après toutes ces transformations, une mesure apportera 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

$eˆ{2 \pi i b yr/N} = 1\,$

Pour l'ensemble des entiers b. Donc, 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 par conséquent 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é.

Références

Préimpression de l'article original de Peter Shor :

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor

Un ouvrage généraliste sur le calcul quantique :

Quantum Computation and Quantum Information, Michæl A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000

Recherche sur Amazone (livres) :

Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Algorithme_de_Shor.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 12/04/2009.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.