3.6 Algorithme quantique de Shor [Jorrand, 2012]
- La factorisation des entiers
Le nombre d'opérations nécessaires au meilleur
algorithme classique actuellement connu pour factoriser un entier est
exponentiel en la taille (nombre de chiffres) du nombre à
factoriser : de l'ordre de e1551/3 pour RSA-155.
Le nombre d'opérations nécessaires à
l'algorithme quantique de Peter Shor (1994) pour factoriser un entier est
polynomial en la taille du nombre à factoriser : de l'ordre
de1553 pour RSA-155. picture
chapitre3 : Les algorithmes quantiques
- Algorithme de Shor pour factoriser P
E N
Début
Choisir a au hasard, 1 < a < P
Si PGCD(a, P) = 1, continuer. Sinon, le
problème est résolu!
Trouver la période r de
fa(k) = ak mod P.
On a alors : ar = 1 mod P.
Si r est pair, alors (ar/2 + 1)
(ar/2 - 1) = 0 mod P.
Si r est aussi tel que ar/2
=6 1 mod P, alors :
PGCD (ar/2 + 1, P) et PGCD
(ar/2 - 1, P) sont des facteurs de P : stop!
Sinon, retourner au pas 1.
Fin
- P=15, Pour voir fonctionner cet
algorithme
On choisit a au hasard, 1 < a < P :
a = 7
PGCD(a, P) = PGCD(7, 15) =
1 : on continue.
fa(k) = 7k mod 15 :
« !On voit !» que r = 4 est pair et
ar/2 = 72 = 49 = 4 mod 15 =6 1 mod
P
PGCD (ar 2 + 1, P) =
PGCD(50, 15) = 5
PGCD (ar 2 - 1, P) =
PGCD(48, 15) = 3
Stop!
|
k
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
...
|
|
fá(k)
|
1
|
7
|
4
|
13
|
1
|
7
|
4
|
13
|
1
|
7
|
4
|
13
|
1
|
7
|
...
|
- Rappel : superposer 2n
valeurs dans n qubit Etat
initial : un registre de n qubits dans l'état
00...0)
27
FIGURE 3.7 - Superposition des 2n valeurs dans n
qubit
chapitre3 : Les algorithmes quantiques
Rsultat :2 valeurs, uniformément
superposées dans le même registre de n qubits, obtenues
avec seulement n opérations.
- Tirer parti de l'intrication
FIGURE 3.8 - L'intrication
Si la mesure du deuxième registre retourne la valeur
y0, alors le premier registre contient tous les x E f-1
(y0)
- Si f est une fonction périodique, de
période r
Soit y0 la valeur de f(x) pour un
certain x, soit x0 le plus petit des x pour lesquels
f(x) = y0, alors : f-1
(y0) = {x0, x0 + r, x0 + 2r, ...,
x0 + kr, ...}
FIGURE 3.9 - Utilisation de la période
r
- Trouver la période r d'une fonction f : ZN
-+ ZP
Pour trouver r : par calcul classique, N = 2
calculs de f. par calcul quantique, combien de calculs de f
?
Premier calcul de f -+ 1er registre
après mesure du 2me registre :
37.png
Deuxieme calcul de f -+ 1er registre
après mesure du 2me registre :
28
29
chapitre3 : Les algorithmes quantiques
- Solution : Transformée de
Fourier Discrète
- Combien de calcul de f pour trouver r ?
FIGURE 3.10 - Comment trouver r?
- Espérance de logN = n
itérations pour trouver r
- Mais ... DFTN est exponentielle :
N2 = 22n multiplications à
chaque itération!
chapitre3 : Les algorithmes quantiques
- DFTN est un produit tensoriel de n termes
- Vers une Transformée de Fourier
Quantique
FIGURE 3.11 - Transformée de Fourier Quantique
30
31
chapitre3 : Les algorithmes quantiques
- Complexité de l'algorithme de Shor
- O(m) itérations pour trouver r
- O(m2) opérations pour
calculer QFTN
- L'algorithme de Shor est en
O(m3).[PHJ3 06]
| 
