Algorithmes quantiques.

David Deutsch Peter Shor

1
Simulation du calcul d’une fonction par réseau de portes quantiques.

En agençant un nombre arbitraire de portes quantiques de toutes les manières

possibles, on construit des réseaux qui transforment globalement n qubits d’entrée en n qubits
de sortie. On peut naturellement concevoir la transformation résultante comme l’exercice du
calcul d’une fonction, f(x) : { 0 ,1 } n → { 0 ,1 } n . Toutefois c’est la question inverse et
généralisée qui est la plus intéressante : peut-on toujours associer un réseau quantique à une
fonction donnée, f(x) : { 0 ,1 } m → { 0 ,1 } k ? L’universalité au sens de Turing l’exige mais cela
ne se fait pas sans précautions. L’ordinateur quantique ne considère que les portes unitaires
donc invertibles ce qui exige que le nombres des bits d’entrée et de sortie coïncident (m=k) et
encore cela ne suffit pas car même lorsque m=k, la majorité des portes restent non invertibles
ainsi que le montre un simple argument de comptage.
m
Il existe 2 k 2 fonctions binaires, { 0 ,1 } m → { 0 ,1 } k . Chacune de ces fonctions peut
être vue comme une porte dont la table logique exprime les instances de la fonction. En
n
particulier, il existe 2 n 2 fonctions binaires, { 0 ,1 } n → { 0 ,1 } n , parmi lesquelles 2 n !
seulement sont invertibles. Voici par exemple, dans le cas, n=2 :

0 0 0 1 1 1 1 0
une des 24 portes invertibles : → → → → ,
0 0 1 0 0 1 1 1

0 0 0 1 1 1 1 0
une des 232 (= 256-24) portes non invertibles : → → → → .
0 0 1 0 0 0 1 1

Il est, en général, inutile d’espérer construire un réseau quantique équivalent au calcul

strict et rien de plus d’une fonction donnée, du type :

x m
f (x) k

Si m≠k, c’est évident car un réseau quantique est toujours invertible et ce schéma ne
l’est pas. Même lorsque m=k, nous savons qu’un calcul invertible exige qu’on ajoute aux
données spécifiques du problème posé (les arguments de la fonction) un certain nombre de
qubits de contrôle qui peuvent sans inconvénients être posés à zéro au début du calcul. A la
fin du calcul, on récupère les résultats escomptés plus des qubits de déchet, inutiles en regard
du problème posé mais indispensables pour garantir l’invertibilité du calcul. Le schéma
précédent peut, par contre, toujours être remplacé par le suivant.

Quelle que soit la fonction classique, f(x) : { 0 ,1 } m → { 0 ,1 } k , qui calcule k bits de

sortie à partir de m bits d’entrée, il est possible de trouver une transformation unitaire (qui est
d’ailleurs sa propre inverse), Uf, agissant sur les m qubits d’entrée plus k qubits
supplémentaires, y, dits de contrôle tels qu’on retrouve intacts à la sortie les m qubits de

2
données flanqués de k qubits, y Xor f(x). En particulier, le calcul de f(x) s’obtient en posant
les k qubits de y égaux à zéro.

x m
x m

Uf
y k
y ⊕ f (x ) k

On voit que le calcul quantique d’une fonction, f(x) : { 0 ,1 } m → { 0 ,1 } k , ne se fait en

toute certitude qu’à l’aide d’une porte de dimension, n=m+k, que l’on note :

Uf x m
y k
= x m
y⊕ f(x) k.

Dans la base calculatoire, la représentation matricielle de Uf prend la forme d’une des

2n! matrices de permutations. Illustrons ce qui vient d’être dit sur l’exemple, m=k=1.

Il existe 4 fonctions binaires, f(x) : { 0 ,1 } → { 0 ,1 } , notées, f0, f1, f2 et f3. La table de

leurs valeurs s’écrit :

x f0(x) f1(x) f2(x) f3(x)

0 0 0 1 1
1 0 1 0 1

La fonction, f2(x), par exemple, est telle que :

 B f 2 0 y = 0 y ⊕ 1

 B f 2 1 y = 1 y ⊕ 0

et les autres suivent sur le même modèle. Les représentations matricielles des opérateurs, Bf,
se notent, dans la base calculatoire habituelle :

1 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0
       
0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 0
B f0 =  B f1 =  B f2 =  B f3 = 
0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1
       
0 0 0 1  0 0 1 0  0 0 0 1  0 0 1 0 
   

3
Calcul parallèle des valeurs d’une fonction.

La grande ambition de l’ordinateur quantique est d’être capable de traiter en parallèle

un grand nombre, N, d’instances d’un problème donné. Dans l’exemple du calcul d’une
fonction, f(x), il doit être capable d’évaluer en un seul passage l’application à tous les entiers
binaires allant de 0 à 2m-1. On y parvient comme suit.

On commence par préparer les données, x m

, dans l’état de base particulier, 0000 .
Si on s’en tenait là, le réseau ne calculerait que f(0). Si on leur applique en sus l’opérateur de
m
Walsh-Hadamard, W = ⊗ H , elles entrent dans un état de superposition maximum :
i= 1

2m −1
1
W 000 00 =
2m
i
i =0
,

qui peut être vu comme la superposition de tous les entiers binaires allant de 0 à 2m-1. Le
réseau de portes quantiques appliqué à ce nouvel état calculera, par linéarité, les 2m instances
1 2 −1
m

de f(x) ,  i m f ( i ) . Cette relation exprime le parallélisme quantique.

2 m i =0

x m
x m

W Uf
y k
y ⊕ f (x ) k

On pourrait se demander ce qu’on gagne concrètement du fait que pour prendre

connaissance du résultat du calcul, une mesure effectuée sur les qubits de sortie est nécessaire
qui ne révélera jamais qu’un seul des résultats calculés en parallèle et encore sans certitude a
priori duquel il s’agira ! Cependant, on peut espérer montrer que soit ces probabilités
d’occurrence ne sont pas égales et qu’elles favorisent à la longue certaines occurrences de
solutions facilement vérifiables soit que quels que soient les tirages, certains invariants
subsistent qui mènent à la solution cherchée.

On voit que la programmation quantique est un art très différent de son homologue
classique. On ne connaît actuellement que fort peu d’algorithmes viables mais les recherches
se poursuivent sur ce terrain neuf. Voici quelques exemples connus basés sur des principes
d’action fort différents. Ils s’inspirent largement d’un exposé dû à John Watrous.

4
L’oracle de Deutsch.

Le problème apparenté suivant, encore dû à Deutsch, illustre la notion d’invariant. Un

oracle est un système uniquement capable de répondre par oui ou part non à une question
posée. Reconsidérons les 4 fonctions binaires, f(x) : { 0 ,1 } → { 0 ,1 } , notées, f0, f1, f2 et f3.
Deux, f0 et f3, sont dites constantes (f(0)=f(1)) et deux, f1 et f2, sont dites balancées (f(0)≠f(1)).
Imaginons que le réseau quantique qui calcule une de ces quatre fonctions est effectivement
prisonnier d’une boîte noire dont le contenu est inaccessible sauf qu’on peut lui soumettre
deux qubits d’entrée et mesurer les deux qubits de sortie, une opération qu’on appellera un
« passage ». Combien de passages sont-ils nécessaires pour découvrir si la fonction cachée
est constante ou balancée ?

Le même problème posé en informatique classique exige deux passages qui

soumettent successivement l’argument x=’0’ puis x=’1’. L’ordinateur quantique fait mieux :
un seul passage suffit avec un coût minime d’un qubit additionnel de contrôle. Voici le
design du réseau.

0
H H m
Bf
1 H

On peut suivre l’évolution du registre initial, 0 ⊗ 1 , à mesure que les différentes

portes sont franchies :

W 1 1 1
0 ⊗ 1 → ( 0 + 1 )⊗ ( 0 − 1 ) = 0 ⊗ ( 0 − 1 )+ 1 ⊗ ( 0 − 1 )
2 2 2
( )
Bf H
1 1 1
→ ( −1 ) f ( 0 ) 0 + ( −1 ) f ( 1 ) 1 ⊗ ( 0 − 1 ) →( − 1 ) f ( 0 ) f ( 0 ) ⊕ f ( 1 ) ⊗ (0 − 1 )
2 2 2

On constate que quelle que soit la fonction cachée, fj(x) (j = 0, 1, 2, 3), la mesure du premier
qubit donne ‘0’ si f est constante et ‘1’ si elle est balancée. Le deuxième qubit est inutile et il
n’a pas besoin d’être mesuré. Cet algorithme fonctionne donc sur base de l’existence d’un
invariant, f ( 0 ) ⊕ f ( 1 ) , commun aux solutions cherchées.

On peut rechercher la représentation matricielle de l’opérateur, R, qui condense à lui

seul la totalité des portes du réseau et vérifier qu’elle a bien le comportement annoncé. Voici
l’exemple, R2, associé à la fonction f2 (attention à l’ordre !):

1 0 0 − 1
 
1 1 0 0 1 
R2 = ( H A ⊗ Id B ) ⋅ B f 2 ⋅ ( H A ⊗ H B ) =
2  0 − 1 1 0 

0 1 1 0 


5
 1 0 0 − 1  0   0 
    
1 1 0 0 1  1  1  0  0 1  − 1
R2 ⋅ ( 0 ⊗ 1 )= = =   ⊗  
A B
2 0 − 1 1 0 0     
2 − 1  1A 2  1  B
    
0 1 1 0  0   1 
  

On voit que l’état final est factorisable et que la mesure du premier qubit le révèle
0
obligatoirement dans l’état, 1 =   , signe que la fonction, f2, est balancée.
 1

Algorithme d’identification.

Il existe 16 fonctions binaires, f(x) : { 0 ,1 } 2 → { 0 ,1 } , ce sont les fonctions booléennes

de base. Nous allons enfermer une de ces fonctions dans une boîte noire mais pour ne pas
compliquer l’exposé, nous convenons de nous restreindre à quatre d’entre elles, précisément :

pq f 8 = Nor ( p , q ) pq f4 = p < q pq f2 = p > q pq f 1 = And ( p , q )

00 1 00 0 00 0 00 0
01 0 01 1 01 0 01 0
10 0 10 0 10 1 10 0
11 0 11 0 11 0 11 1

Le problème posé consiste à découvrir en un seul passage laquelle de ces quatre

fonctions la boîte noire calcule. Cette performance est manifestement hors de portée d’un
ordinateur classique. Le circuit suivant répond à la question posée.

On peut le vérifier en suivant pas à pas l’évolution du registre ou en calculant la

représentation matricielle équivalente, nécessairement 8x8, ou encore en recourant à la
notation tensorielle. Il s’avère que le troisième qubit est inutile et que la mesure des deux
premiers livre la réponse cherchée selon le code :

00 AB
→ f8 01 AB → f 4 10 AB
→ f2 11 AB → f1 .

6
Algorithme de recherche dans une base de données.

Les problèmes qui précèdent sont artificiels à plus d’un titre. D’une part, la question
posée n’est pas particulièrement intéressante et d’autre part, personne ne passera jamais son
temps à enfermer un système dans une boîte noire pour le plaisir de compliquer la situation.
n
Le problème suivant est nettement plus réaliste. Rappelons qu’il existe 2 2 fonctions,
f(x) : { 0 ,1 } n → { 0 ,1 } parmi lesquelles 2n sont est nulles pour toutes les valeurs de ses
variables sauf une, disons xa. Le problème est précisément de trouver xa tel que f(xa) =1. Vu
que xa est assimilable à une suite, s, de ‘0’ et de ‘1’, on voit que ce problème est apparenté à la
recherche d’un abonné dans un annuaire classé dans l’ordre alphabétique quand on ne connaît
que son numéro d’appel.

La fonction que nous avons en vue et son implémentation quantique se

notent respectivement :

0 si x≠s
f s (x)= 
1 si x=s

U fs x y = x y ⊕ f s (x) .

Le circuit suivant, imaginé par Grover résout par itération le problème posé :

0
x k
x k +1
0

0 H H
⊗H ⊗H ⊗ Not ⊗ Not ⊗H

C
1 H Ufs

Il se compose de n lignes (on n’en a dessiné que trois) qui encodent le vecteur d’état,
x , du système, à tout instant plus une ligne de contrôle, C. On prépare initialement le
registre dans l’état de base, 00 0 , que l’on fait entrer dans l’état de superposition
maximum grâce à n portes de Hadamard disposées en parallèle :

n 2 n −1
1
x0 = ⊗ H 00 0 =
1 2n / 2
k
k =0
.

7
Quant au qubit de contrôle, C, on l’initialise dans l’état, 1 , qu’une porte de Hadamard
1
transforme immédiatement en : 1 → ( 0 − 1 ) . En résumé, le système démarre dans
2
1
l’état, x0 ⊗ ( 0 − 1 ).
2

Dans l’écriture du vecteur d’état, x0 , les N états de base sont mis sur un pied
d’égalité. La probabilité qu’une mesure du registre révèle, à ce stade, la valeur k cherchée ne
2
vaut évidemment que x0 s = 1 / N , soit la valeur prédite par un tirage au sort honnête.
C’est cette situation que le réseau conçu par Grover se propose d’améliorer. Ce réseau
fonctionne itérativement, transformant à chaque passage le vecteur d’état, x k ( k = 0 ,1 , ) ,
en un nouveau vecteur d’état, x k + 1 , qui se rapproche de s .

Il est commode de décomposer à tout instant le vecteur d’état selon la direction définie
par s et la résultante des composantes orthogonales qui s’aligne sur u . Au départ, on a :

N −1 1
x0 = u + s = cos( θ / 2 ) u + sin( θ / 2 ) s
N N

et on cherche λk et μk tels que l’on a encore à tout instant ultérieur,

xk = λk u + μ k s .

Le bloc itératif se compose de deux unités distinctes que la figure a séparé par un trait
pointillé. Lors de la kième itération, la première unité, qui est une porte Uf, a pour seul effet
d’inverser le signe de la composante de x k selon s (le qubit de contrôle n’est pas altéré) :

x k ⊗ ( 0 ⊕ f s ( x k ) − 1 ⊕ f s ( x k ) ) = ( −1 ) f s ( x ) x k ⊗
1 1 1
U fs xk ⊗ (0 − 1 ) = (0 − 1 )
2 2 2

= (1 − 2 s s ) xk ⊗
1 1
( 0 − 1 ) = ( λk u − μ k s ) ⊗ (0 − 1 )
2 2

La deuxième unité est d’apparence plus complexe bien que l’effet global soit simple :
elle correspond à l’opérateur, 2 x0 x0 − Id , ce que l’on peut vérifier directement. Les
calculs se résument comme suit :

xk +1 = λk +1 u + μk +1 s =
(2(cos( θ / 2 ) u + sin( θ / 2 ) s )(cos( θ / 2 ) u + sin( θ / 2 ) s ) − Id ) ⋅ ( λ k u − μ k s )

d’où le système récurrent satisfait par λk et μk :

8
λk + 1 = λk cos θ − μ k sinθ μ k + 1 = μ k cos θ + λk sinθ
.
λ0 = cos( θ / 2 ) μ0 = sin( θ / 2 )

On trouve que le système complet se trouve, après k itérations, dans l’état :

x k = cos[( k + 1 / 2 )θ ] u + sin[( k + 1 / 2 )θ ] s

et le qubit de contrôle n’est toujours pas altéré.

On constate que lorsque k est l’entier le plus proche de (π/2θ)-0.5, soit encore de
l’ordre de ,

π 1
k≈ N− ,
4 2

xk se confond quasiment avec s . On voit qu’en gros, N = 2 n / 2 passages sont

nécessaires, un gain appréciable par rapport à l’algorithme classique qui en exigerait 2n. Par
exemple, si N=106, θ = 2 arcsin( 1 / 1000 ) , et la probabilité qu’une mesure du registre, à
l’étape k=785, fournisse l’ensemble des qubits encodés par s vaut
2
xk s = 0.9999999584 .

Factorisation des entiers longs : algorithme de Shor.

On sait que la confiance que l’on porte à la méthode désormais classique de

cryptographie RSA repose sur deux conjectures jamais démontrées : 1) que la brisure du code
RSA est synonyme de factorisation et 2) que cette factorisation n’est pas possible par des
procédures classiques en un temps polynomial.

Aucune méthode classique de factorisation, de la plus naïve (Erathostène, en Ο( N ) )

{ }
à la plus évoluée (Pollard-Strassen, en Ο exp[ (cgN ) ( ggN )2 / 3 ] ), ne résout le
1/ 3

problème en un temps polynomial. Par contre, on sait, depuis 1994, qu’il existe un algorithme
quantique, dû à Shor, qui est susceptible d’y parvenir à condition qu’un ordinateur quantique
digne de ce nom voie jamais le jour. En 2001, le record est détenu par un groupe IBM qui a
« réussi » à factoriser l’entier 15 mais ce n’est peut-être qu’un début. Il va donc de soi que cet
algorithme ne menace pas immédiatement la cryptographie à clefs publiques à tel point que
beaucoup pensent que la probabilité que l’ordinateur quantique devienne une réalité est bien
moindre que celle d’une brisure du code RSA par une méthode différente de la factorisation.
L’algorithme de Shor n’en vaut pas moins le détour.

La méthode de Shor déploie, en fait, une stratégie probabiliste qui lui assure de trouver
un facteur premier de n’importe quel nombre composite avec une bonne probabilité. Toute
tentative qui a échoué peut être recommencée jusqu’à ce qu’un facteur se dégage presque à
coup sûr en un temps raisonnable. La méthode de Shor est un mélange de stratégies classique
et quantique et il va de soi que les premières ne sont utilisées que lorsqu’elles sont effectives

9
en un temps polynomial. Nous commençons par l’exposé du principe de la méthode. Soit à
trouver un facteur premier de l’entier N.

1) Tester la primalité de N. On connaît depuis 2002 un algorithme (AKS) effectif en un

temps polynomial. Si N est premier le problème est résolu : il n’existe pas de facteur
premier autre que lui-même.

2) Sinon, choisir un entier, a (1<a<N), au hasard. Calculer, par l’algorithme d’Euclide, le

pgcd de a et de N. S’il est différent de 1 on a, par chance, trouvé un facteur premier de
N et le problème est résolu. Sinon on poursuit comme suit.

3) On construit la suite, sk = Mod [ a k , N ] , inévitablement périodique de période, r,

sk + r = sk .

4) Si r est impair ou si Mod [ a r / 2 , N ] = ±1 , la procédure est en échec et il y a lieu de la

reprendre au point 2 sur base d’une nouvelle valeur de a.

5) Sinon, deux facteurs de N sont respectivement : p gcd[ a r / 2 ± 1 , N ] .

Toutes ces étapes sont effectives en un temps polynomial sauf une : celle qui calcule la
période, r, de la suite. Il est utile, à ce stade, de rappeler la méthode classique de détection de
la période d’une suite. Elle est basée sur la transformée de Fourier discrète (TFD).

1) Extraction de la période d’une suite par transformée de Fourier discrète.

Soit une suite sk , ( k = 0 ,1 , , N − 1 ) , on définit ainsi sa TFD,

~
s j , ( j = 0 ,1 , , N − 1 ) :

N −1 N −1
1 jk 1 jk ~
~
sj =
N

k =0
exp[ 2 iπ
N
] sk ⇔ sk =
N
 exp[ −2 iπ
j =0 N
] sj

Lorsque la suite sk est réelle, sa TFD ne l’est en général pas à l’exception de son
premier élément qui vaut toujours la moyenne arithmétique de ses éléments. Les autres
éléments de la TFD sont reliés par la relation : ~
sj = ~
s N* − j ( j = 1 , , N − 1 ) . Cette propriété
ne vaut plus si sa suite de départ est complexe.

Il existe un rapport étroit entre TFD et suites périodiques. On le met en évidence en

considérant le prototype de la suite périodique, sk = exp[ 2 iπkν ] , de fréquence, ν ∈ ] 0 ,1 [ ,
ou, si l’on préfère, de période, T = 1 / ν (>1). La TFD de cette suite vaut exactement :

~ 1 sin( Nπν )  j 
sk = exp[ 2 iπkν ] ⇔ sj = exp  iπ [( N − 1 )ν − ] .
N sin( πν + πj / N )  N 

10
 Il existe un cas idéal où la suite ~
s j est nulle partout sauf en un point : il suffit que Nν
soit entier, Nν =  , ou, ce qui revient au même, que la période de la suite, T, divise sa
longueur, N. Dans ce cas, la TFD est nulle partout sauf au point, j, calculé comme suit :

sin( πν + πj / N ) = 0  j = N ( 1 −ν ) ( entier ! )  ~
sj = N ≠ 0 .

Voici le détail de la TFD de la suite de fréquence 1/8, échantillonnée 32 fois, suivie de

son graphe qui est réel dans ce cas particulier :

SimplifyTable   Exp k Exp2  k , j, 0, 31

1 31 2  j


8 32
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4 2 , 0, 0, 0
32 k0

GeneralizedBarChartTablej, Abs FourierTable Exp n, n, 0, 31j  1, 0.0001, j, 0, 31,
2 

PlotRange  All, Axes  False, Frame  True

8

0 2iπ
0 5 10 15 20 25 30 ( sk = exp[ k ] ; ν = 1/8 d’où T = 8; N = 32)
8

Le graphe change lorsque N n’est plus un multiple de T : la suite, ~sj , cesse d’être nulle
presque partout. Toutefois, elle conserve un pic principal au voisinage de N(1 − ν) , qui a
d’ailleurs cessé d’être un entier. Du fait que la TFD devient complexe on ne dessine que son
module :

GeneralizedBarChartTablej, AbsFourierTableExp n, n, 0, 37j  1, 0.0001, j, 0, 37,

2 

PlotRange  All, Axes  False, Frame  True

8

0 2iπ
0 5 10 15 20 25 30 35 ( sk = exp[ k ] ; ν = 1/8 d’où T = 8; N = 38)
8

11
 L’exemple considéré est très particulier. Une suite périodique quelconque possède
une TFD plus compliquée. Considérons la suite, de période 12,

sk = Mod [ 2 k ,35 ] = { 1 ,2 ,4 ,8 ,16 ,32 ,29 ,23 ,11 ,22 ,9 ,18 ,1 ,2 ,4 ,8 , } .

On constate, à nouveau, que si T divise N, la TFD continue d’être nulle sauf en

quelques points isolés, onze dans l’exemple retenu en ignorant l’origine :

GeneralizedBarChartTablej, AbsFourierTableMod2n, 35, n, 0, 119j  1, 0.0001, j, 0, 119,

PlotRange  All, Axes  False, Frame  True

150

125

100

75

50

25

0
0 20 40 60 80 100 120 ( s k = Mod[2k ,35] ; T = 12 ; N = 120)
 
On explique cette démultiplication des pics en exprimant la suite comme combinaison
linéaire de T exponentielles imaginaires du type, exp( 2 iπkν 0 ) (  = 0 ,1 , ,T − 1 ) . Cette
opération est toujours possible à condition d’égaler la valeur de ν0 à l’inverse de la période de
la suite considérée. On trouve un nombre de termes égal à la période, T, soit, dans l’exemple,
la décomposition suivante :
T −1
2 iπ 2 iπ 2 iπ
sk = Mod [ 2 k ,35 ] =  c exp[ 2 iπν 0 k ] =c0 + c1 exp[ k ] + c 2 exp[ 2 k ] +  + c11 exp[ 11k ]
=0 12 12 12

Dans cette expression, le deuxième terme,  = 1 , est toujours présent, c’est le

fondamental de fréquence ν 0 = 1 / T . Les (T-2) termes qui suivent sont ses harmoniques, de
fréquences, ν = ν 0 =  / T et il n’est pas exclu que certains harmoniques soient absents si la
valeur du coefficient, cj, qui lui est associée est nulle. Les cj (j=0, …,11) se calculent
simplement par inversion de la transformée de Fourier, soit, dans l’exemple :

c  SimplifyTable  Mod2j, 35 Exp j k, k, 0, 11

1 11 2 

  

12 j0 12
 2     3 , 113,   1  3  3 ,  2     3 ,
175 35 35 7 7 5 35
, ,

  

12 24 12 6 12 24 24
 2     3 , 1  3  3 ,    123,   116 2     3 
35 35 5 7 7 35 35
 , ,
12 24 24 6 12 12 24

En résumé, le terme constant est responsable de la contribution à l’origine et les autres

termes contribuent chacun pour un pic dans la TFD, qu’on localise, en partant de la droite du
graphe, aux positions, j = N ( 1 − ν 0 ) (  = 1 ,2 , ,11 ) . Les onze termes présentent, en
effet, des fréquences, ν =  / T , égales respectivement à : 1/12, 2/12, …, 11/12. On en

12
conclut que, dans l’exemple choisi, la TFD sera non nulle aux abscisses, 0, 10, 20, 30, …,
110. C’est bien ce qu’on observe.

En pratique on procède plutôt en sens inverse : on cherche la période de la suite sur

base du graphe de sa TFD. On inverse donc le raisonnement et on associe à chaque pic situé
 j
en j une fréquence, ν, valant : ν = ν 0 = = 1 − .
T N

L’ensemble de ces fréquences forment la suite du fondamental et des harmoniques,

soit dans l’exemple, {1/12, 2/12, 3/12, …, 11/12}, les pics étant lus de droite à gauche sur le
graphe. La fréquence la plus basse, ν0, correspond au dernier pic, obligatoirement toujours
présent, et elle vaut l’inverse de la période cherchée, T=12, dans l’exemple.

Il résulte de ce qui précède que dans le cas particulier considéré où la longueur de la

suite est un multiple de la période, la connaissance de la TFD d’une suite périodique
renseigne immédiatement sur la valeur de sa période : il suffit de repérer la position, j, du
dernier pic et d’appliquer la formule, T = N/(N-j). Si l’on applique la même formule en
utilisant la valeur de j correspondant à un autre pic que le dernier, on trouve toujours un sous-
multiple de la période.

Plusieurs problèmes subsistent cependant. Le premier est assez évident : on doit se

fixer une longueur d’échantillonnage, N, pour la suite mais on ne connaît pas sa période, T,
puisque précisément on la cherche. Sauf par chance extraordinaire, on se trouvera donc
rarement dans le cas où T divise N et il convient de voir ce qu’on peut espérer de la méthode
dans ce cas général.

Si T ne divise pas N, la TFD présente encore des pics principaux mais ils sont noyés
dans un ensemble de pics ambiants plus petits d’où il résulte que le succès de l’analyse
précédente n’est plus garanti. L’exemple suivant où la suite test est échantillonnée 128 fois le
montre : le dernier pic principal se situe en j = 117. Or T = N/(N-j) = 128/(128-117) = 128/11
= 11.6364 ne livre certainement pas la période cherchée avec exactitude puisque ce n’est pas
un entier mais elle n’en n’est pas très éloignée et une vérification de sT = s0 est après tout
toujours possible !

GeneralizedBarChartTablej, AbsFourierTableMod2n, 35, n, 0, 127j  1, 0.00001, j, 0, 127,

PlotRange  All, Axes  False, Frame  True

150

125

100

75

50

25

0
0 20 40 60 80 100 120 ( s k = Mod[2k ,35] ; T = 12 ; N = 128)

13
 On peut cependant remédier à cette situation de deux façons le cas échéant
simultanément. La première consiste à allonger la suite. Voyons ce que devient l’exemple
précédent si on double la longueur de l’échantillon, passant de N = 128 à 256 :
GeneralizedBarChartTablej, AbsFourierTableMod2n, 35, n, 0, 255j  1, 0.0001, j, 0, 255,
PlotRange  All, Axes  False, Frame  True

200

150

100

50

0
0 50 100 150 200 250 ( s k = Mod[2k ,35] ; T = 12 ; N = 256)

On constate que les pics s’affinent et que la position du dernier d’entre eux, en j = 235,
nous rapproche de la période cherchée : T = N/(N-j) = 256/(256-235) = 256/21 = 12.19. Si on
localise par erreur le dernier pic principal en j = 234 ou 236, on trouvera une approximation
de la période plus ou moins bonne, respectivement, 11.64 et 12.8. On voit que dans ce cas, la
méthode cesse d’être sûre mais cela dit, il est toujours extrêmement facile de vérifier si on a
bien, sT = s0 , en essayant quelques valeurs qui encadrent l’approximation trouvée. Cette
remarque peut paraître hors de propos dans la mesure où personne ne s’attend à commettre
d’erreur dans le calcul d’une TFD. Elle ne l’est absolument pas dans l’optique d’une
implémentation quantique de la TFD.

2) La transformée de Fourier quantique.

Une question préalable se pose toutefois : la procédure classique qui vient d’être
décrite semble résoudre parfaitement le problème de l’extraction de la période d’une suite
périodique. Dès lors pourquoi ne pas s’en contenter ? Le problème est que cette procédure
n’est pas effective avec des ressources polynomiales. Le calcul complet d’une TFD sur un
ordinateur classique requerrait un nombre d’opérations élémentaires de l’ordre du carré, N2,
du nombre que l’on veut factoriser (en fait, de l’ordre de NgN en recourant à l’algorithme
rapide de Cooley & Tuckey) . A ce prix, autant recourir au crible d’Erathostène en N!

Par contre l’ordinateur quantique fait beaucoup mieux car il est capable de calculer en
parallèle tous les éléments d’une TFD. Considérons un registre, comprenant n qubits, qui
évolue dans un espace de Hilbert à N=2n dimensions. Son vecteur d’état s’écrit :

2 n −1
ψ = c
j =0
j j ,

14
dans la notation abrégée où les 2n vecteurs de base, j , sont ordonnés en suivant l’écriture
binaire, de 0 = 00 0 à 2 n − 1 = 11 1 . Dans cette base, le vecteur d’état est
complètement caractérisé par la suite des amplitudes {cj}, de longueur, 2n. On définit la
transformée de Fourier quantique du vecteur d’état (TFQ), ψ~ , comme le vecteur d’état,

2n −1
ψ~ =  c~
k =0
k k ,

2 n −1
1 jk
où la suite { ~
ck } est la TFD, c~k =
2n
 exp[ 2iπ 2
j =0
n
] c j , de la suite {cj}.

Voici l’opérateur, F̂ , qui transforme ψ en ψ~ , il est unitaire :

2n −1 2 n −1
1 jk
F̂ =
2 n   exp[ 2iπ 2
j =0 k =0
n
]k j  F̂ ψ = ψ~ .

Intéressons-nous au résultat de l’application de F̂ à n’importe lequel des 2n vecteurs

de base, par exemple,  =  1 2  n , on trouve que la TFQ se factorise comme suit :
F̂  =
~
 =
1
(
( 0 + exp[ 2 iπ 0. n 1 ) ⊗ ( 0 + exp[ 2 iπ 0. n−1 n 1 ) ⊗  ⊗ ( 0 + exp[ 2 iπ 0. 1 2   n 1 ) )
2n

Cette factorisation est essentielle pour une conception récursive du circuit quantique
capable d’implémenter la QFT quel que soit le nombre, n, de qubits qui composent le registre.
Le réseau quantique correspondant utilise n portes de Hadamard et n(n-1)/2 portes induisant
sous contrôle des déphasages du type, π/2j (j=0,1,2,…), (n=4 dans l’exemple représenté) :

x0 0 + exp[ 2 iπ / 2 1 ] 1
H
x1 0 + exp[ 2 iπ / 2 2 ] 1
H
x2 0 + exp[ 2 iπ / 2 3 ] 1
H
x3 0 + exp[ 2 iπ / 2 4 ] 1
H
π / 2 2 π / 21 π / 20

Dans ce schéma, la succession des portes s’écrit (attention à l'ordre inverse !) :

HD cΦ (π)CD cΦ (π/2)BD cΦ (π/4)AD HC cΦ (π)BC cΦ (π/2)AC HB cΦ(π)AB HA

L’idée sur laquelle repose l’algorithme de Shor est de se servir de la TFQ pour calculer
en un seul passage la totalité de la TFD. Toutefois ce calcul massivement parallèle a un prix,
celui de ne révéler qu’une valeur particulière de la TFD lors de la lecture du registre de sortie

15
mais on verra que cela suffit à déterminer la période avec une bonne probabilité. Il est alors
aisé de vérifier si s T = s 0 et de recommencer la procédure si, par malchance, elle a échoué.

3) L’algorithme de Shor proprement dit.

Il existe plusieurs présentations plus ou moins économiques de l’algorithme mais nous

avons préféré privilégier la clarté. Un exemple fera mieux comprendre comment il
fonctionne. Soit à factoriser le nombre N=21. On choisit un entier, a<N, premier avec N, soit
a=2, par exemple. La suite, {2k Mod 21} vaut : {1,2,4,8,16,11,1,2,4,8,16,11} et elle est de
période paire, r = 6. Deux facteurs premiers de 21 sont donc : PGCD[2r/2 ±1,21] soit 3 et 7.
Ce raisonnement a été facilité par le fait qu’une simple inspection de la suite a révélé la valeur
de sa période mais cela cesse d’être possible lorsque N comporte quelques centaines de
chiffres. Pour les besoins de l’exemple considéré, nous allons faire comme si r était
effectivement hors d’atteinte immédiate.

Nous optons pour la présentation suivante, empruntée à Lavor et al., pas forcément la
plus économique mais sans doute la plus claire. Nous avons besoin de deux registres. Le
premier comprend τ qubits, τ, tel que N 2 ≤ 2τ < 2 N 2 : τ = 9 est la plus petite valeur qui
convient dans l’exemple considéré. Le deuxième registre comprend n qubits où, n = gN  ,
représente le nombre de bits nécessaires à l’encodage classique de N. Les deux registres sont
initialisés dans les états de base, 0τ et 0 n , et le système est décrit par le vecteur d’état,
ψ 0 = 0τ 0 n , soit, dans l’exemple, ψ 0 = 000000000 00000 , que l’on abrège comme
d’habitude en ψ 0 = 0 0 .

H
0τ  TFD 
H
Vx

0n  

τ portes de Hadamard commencent par transformer cet état en,

2τ − 1 511
1 1
ψ1 =
2τ / 2
j =0
j 0 =
512

j =0
j 0 .

Ensuite, l’opérateur Vx entre en action qui effectue l’opération unitaire :

Vx j k = j ( k + x j ) mod N .

A la sortie de cette porte, le système se trouve dans l’état suivant :

16
 2τ − 1
1
ψ 2 = Vx ψ 1 =
2 τ/2  j =0
j x j mod N .

Dans l’exemple, cela donne :

[ ( 0 + 6 + 12 +  + 510 ) 1 + ( 1 + 7 + 13 +  + 511 ) 2 +
1
ψ2 =
512
( 2 + 8 + 14 +  + 506 ) 4 + ( 3 + 9 + 15 +  + 507 ) 8 +
(4 + 10 + 16 +  + 508 ) 16 + ( 5 + 11 + 17 +  + 509 ) 11 ]

On note que les deux premiers termes contiennent 86 termes alors que les quatre
derniers en contiennent 85. L’état, ψ 2 , a ceci de remarquable que grâce au phénomène de
superposition quantique, il contient la totalité de l’information que constituent les diverses
puissances de x modulo N. Evidemment cette information n’est pas directement accessible
puisque toute mesure a pour effet de ne révéler qu’une seule de ces puissances en détruisant
les autres par projection.

Le moment est venu de mesurer l’état du second registre qui, dans l’exemple, ne peut
livrer que l’un des six résultats suivants, avec des probabilités d’ailleurs égales :
{1,2,4,8,16,11}. Supposons qu’il s’agisse du résultat ‘2’. Le système est projeté sur l’état
propre renormalisé correspondant :

(( 1 + 7 + 13 +  + 511 ) 2 ) =
85
1 1
ψ3 =
86 86
 6 + 1
 =0
2 .

Le premier registre est à présent projeté dans une superposition d’états dont les
numéros d’ordre forment une suite périodique de période précisément égale à r. Peu importe
le détail des termes de la suite, r est le renseignement vital qu’il nous faut extraire. On y
parvient en appliquant une TFD portant sur τ qubits :

2τ − 1 2τ − 1
1 jk
ψ 4 = TFD ψ 3 =
2τ
  exp[ 2 iπ 2τ ] k
j =0 k =0
j ψ3 ,

soit dans l’exemple :

1 1 512
 85
( 6 + 1 ) j  
ψ 4 = TFD ψ 3 =    exp[ 2 iπ ]  j  2
 
512 86 j =0  k =0 512

Une mesure du premier registre, révèle la réponse, ‘j’, avec la probabilité,

2
1 85
( 6 + 1 ) j 1 sin 2 ( 258πj / 256 )
pj =
86 × 512

=0
exp[ 2 i π
512
=
86 × 512 sin 2 ( 3πj / 256 )
( j = 0 ,1 , ,511 ) .

17
Dans cette dernière expression, une indétermination doit être levée en j=0 et 256, elle donne :

86 2
p0 = p256 =
86 × 512
511
On vérifie que l’on a bien que la somme des probabilités vaut 1 : p
j =0
j = 1.

Le graphe de pj est celui d’une fonction qui ne s’écarte notablement de zéro qu’en cinq
endroits bien définis (l’origine étant ignorée), aux voisinages respectifs de :

j=85 j=171 j=256 j=341 j=427

(p85=11.4) (p171=11.4) (p256=16.8) (p341=11.4) (p427=11.4)

Ces cinq valeurs de j représentent à elles seules 62.4% des cas possibles.

0.15

0.125

0.1

0.075

0.05

0.025

0 100 200 300 400 500

Partout ailleurs (sauf en l’origine qui est inexploitable et qui est « tirée au sort par la
mesure dans 16.8% des cas), la probabilité tombe rapidement en-dessous de 0.001. Cela
signifie que la mesure du premier registre révélera le plus fréquemment une des 5 valeurs
intéressantes, 85, 171, 256, 341 ou 427. Il reste à appliquer à ces 5 valeurs de j, prises dans
l’ordre inverse, la formule bien connue, (pour rappel, N=512) :

N-j 85 171 256 341 427

ν=  ν0 = ;ν 1 = ;ν 2 = ;ν 3 = ;ν 4 = ;
N 512 512 512 512 512

La période cherchée vaut l’inverse de la fréquence la plus basse, 1/ν0= 512/85=6.023,

soit plus que probablement la valeur cherchée, T = r = 6.

En pratique l’extraction de la période ou d’un de ses sous-multiples si la mesure a

révélé autre chose que le dernier pic, se fait sur base du développement en fractions continues
de la valeur trouvée pour la fréquence. Le développement de ν4 donne :

18
 427 k 1
ν4 = = =
512 r 1+ 1
1
5+
1
42+
2

soit la suite des approximants, 1/1, 5/6, 211/253,427/512.

On trouve la période cherchée, r, comme le dénominateur de l’approximant le plus

précis dont le dénominateur n’excède toutefois pas N (en effet, r<21). On trouve le période
vaut très probablement 6.

Le même calcul effectué sur ν1 donne :

171 k 1
ν1 = = =
512 r 2+ 1
1
1+
170

soit la suite des approximants, 1/2, 1/3, 171/512. Le meilleur dénominateur est 3 qui n’est pas
la période mais un de ses sous-multiples. Cette technique d’extraction est tout à fait
remarquable car on montre qu’elle continue de fonctionner même si l’on s’écarte modérément
du pic principal. Par exemple, il suffit que la mesure révèle une valeur de j comprise entre
163 et 178 pour que le développement en fraction continue fournisse toujours 3 comme
facteur probable de la période ainsi qu’en attestent les listes des approximants pour des
valeurs de j allant de 162 à 179 :

Table[Convergents[ContinuedFraction[j/512]],{j,162,179}]

0, , 0, , , 0, , ,

1 6 25 81 1 7 78 163 1 8 41
, , , , , ,
3 19 79 256 3 22 245 512 3 25 128
0, , 0, , , 0, , ,
1 9 10 29 68 165 1 11 12 83 1 15 76 167
, , , , , , , , ,
3 28 31 90 211 512 3 34 37 256 3 46 233 512
0, , 0, , , 0, , , 0, , , , 0, , , ,
1 21 1 33 34 169 1 85 1 1 171 1 1 43
, , ,
3 64 3 100 103 512 3 256 2 3 512 2 3 128
0, , 0, , , , 0, , , ,
1 1 24 25 74 173 1 1 17 35 87 1 1 13 27 175
, , , , , , , , ,
2 3 71 74 219 512 2 3 50 103 256 2 3 38 79 512
0, , 0, , , , 0, , , , 0, , , 
1 1 11 1 1 9 28 177 1 1 8 89 1 1 7 43 179
, , , , , , ,
2 3 32 2 3 26 81 512 2 3 23 256 2 3 20 123 512

La procédure échoue en j=162 ou 179 car l’algorithme suggérerait une période erronée
valant 19 ou 20. Toutefois ces événements malencontreux sont extrêmement peu probables,
p162 = 0.000126 ou p179 = 0.0002245. En recommençant toute la procédure un nombre
suffisant de fois, on fait apparaître les facteurs probables de r. Le ppcm de ces facteurs
permet de remonter à r avec une probabilité proche de 1. L’incertitude qui subsiste est facile
à dissiper : il suffit de vérifier que la période convient et que l’on a bien sT = s0 .

19
Corrections d’erreurs.

Les énormes difficultés qu’il y a à préserver tout registre quantique des influences
décohérentes du milieu environnant représentent l’entrave majeure à la réalisation d’un
prototype d’ordinateur quantique. Le problème est si aigu que la solution n’est nullement
écartée de l’adoption d’un protocole massif de corrections d’erreurs. En d’autres termes,
plutôt que d’essayer de maintenir à tout prix la cohérence des registres, on envisage de mettre
en place, à tous les stades du calcul, des transformation qui passent les registres en revue et les
restaurent automatiquement s’ils sont corrompus. Bien entendu de telles procédures
consomment des ressources de qubits supplémentaires mais on estime généralement que ce
coût reste modéré par rapport à ce que représenterait la mise en place d’une cohérence
parfaite.

La correction automatique d’erreurs se fait sur le même principe qu’en théorie

classique de l’information en recourant à des (qu)bits supplémentaires qui créent la
redondance nécessaire. Toutefois le problème se complique en théorie quantique du fait que
les vecteurs d’états ne sont pas forcément dans l’état logique ‘0’ ou ‘1’ mais qu’ils peuvent
être en superposition des deux. Il faut, en particulier, pouvoir corriger des erreurs de
déphasages sans perdre de vue que le clonage pur et simple est impossible. Nous ne faisons
qu’effleurer ce sujet vaste et complexe.

Rappelons le principe du code correcteur classique le plus élémentaire qui soit : il est
question d’envoyer un bit au travers d’un canal de transmission bruité de telle manière que la
probabilité qu’il soit malencontreusement inversé soit égale à p. Le correspondant ne reçoit le
bit correct qu’avec la probabilité (1-p). Une stratégie élémentaire consiste à envoyer trois
copies du même bit que le receveur décodera à la majorité simple. Si p<1/2, on constate que
la probabilité de décodage erroné tombe de p à 3p2-2p3. Ce n’est pas parfait mais il y a un
progrès. Si l’on veut faire beaucoup mieux, il y a lieu de mettre des procédures plus
compliquées.

Cette procédure n’est pas applicable telle qu’elle à la transmission d’un qubit lorsque
celui-ci est en état de superposition inconnu, ψ = α 0 + β 1 . D’une part, le théorème de
non-clonage interdit de réaliser les deux copies nécessaires de ψ et de plus, mesurer les trois
qubits envoyés afin de décoder à la majorité n’aurait aucun sens puisque la mesure a pour
effet de détruire l’état mesuré. En fait, dans le montage qui suit, quatre qubits
supplémentaires, préparés dans l’état de base, 0 , sont utilisés à l’émission :

α 0 + β1

20
 Supposons qu’on veuille protéger un qubit inconnu, α 0 + β 1 , contre l’inversion
accidentelle, ‘0’ ↔ ’1’. On commence par utiliser deux portes CNot afin de l’encoder dans
un registre à trois qubits, sous la forme, ψ 0 = α 000 + β 111 . Rappelons que sur ce genre
de figure, l’axe horizontal, lu de gauche à droite, représente la ligne du temps. Le rectangle
pointillé représente une zone temporelle où une corruption d’inversion menace de se produire
avec une probabilité que nous n’avons pas besoin de connaître. A la sortie de cette zone, le
registre se trouvera dans l’un des quatre états suivants dont trois sont altérés :

Id ⊗ Id ⊗ Id ψ 0 Not ⊗ Id ⊗ Id ψ 0 Id ⊗ Not ⊗ Id ψ 0 Id ⊗ Id ⊗ Not ψ 0 .

Plutôt que d’essayer d’empêcher cette corruption, on préfère l’accepter mais on ajoute
un circuit, composé de cinq portes CNot correctement agencées, qui ont pour effet de
restaurer le registre dans les quatre cas de figure. Avec un peu de patience on peut se
convaincre que le circuit fonctionne comme suit : les trois qubits parviennent à Bob dans
l’état éventuellement altéré, ψ 0 = α 000 + β 111 . Les deux derniers qubits ne sont que
des auxiliaires qui peuvent être mesurés par Bob. Celui-ci trouvera, dans tous les cas, le
numéro binaire du qubit altéré (00 = pas d’altération, 01 = altération du premier qubit, 10 =
altération du deuxième qubit, 11 = altération du troisième qubit). Selon la valeur du
syndrome trouvé, il reste à Bob à réappliquer une porte Not au qubit altéré puis à inverser la
manœuvre réalisée par Alice afin d’extraire ψ = α 0 + β 1 de ψ 0 = α 000 + β 111 .
Ces deux manœuvres peuvent être faites automatiquement sans même qu’une mesure soit
effectuée. Il suffit que Bob utilise le circuit de réception suivant, où les trois premières portes
CNot corrigent l’erreur (le qubit de contrôle gris est inversé : le contrôle ne commande
l’instruction Not que s’il est mis à ‘0’) et les deux dernières portes extraient ψ = α 0 + β 1
de ψ 0 = α 000 + β 111 :

α 0 + β1

Au bilan ce réseau répare l’éventuelle inversion isolée d’un qubit. Hélas l’histoire ne
s’arrête pas là. L’inversion d’un qubit n’est qu’un avatar parmi d’autres que peut subir le
qubit. L’altération la plus générale revêt nécessairement la forme suivante

ψ alt = ( e1 Id + e 2σ x + e 3σ y + e4σ z ) ψ ,

où les coefficients, ei, peuvent être complexes. Dans l’exemple précédent, l’inversion
correspondait au cas particulier, Not = σx. σz = Φ(π) correspondrait à une inversion de phase.
Or les réseaux qui précèdent sont impuissants à corriger ne serait-ce qu’une inversion de
phase et ce qu’il nous faut c’est une procédure effective dans tous les cas.

21
 Il n’est pas question d’étudier ici les détails de cette procédure générale. On peut se
faire une idée des complications auxquelles il faut s’attendre en contemplant la solution que
Shor a trouvée pour régler le cas pas encore général où on veut corriger à la fois une inversion
de bit et de phase. Une solution à ce problème nécessite un encodage préalable du qubit à
protéger, ψ = α 0 + β 1 , sous la forme d’un registre à 9 qubits :

( 000 + 111 )( 000 + 111 )( 000 + 111 ) ( 000 − 111 )( 000 − 111 )( 000 − 111 )
ψ0 = α +β
2 2 2 2
que l’on obtient en utilisant le réseau suivant :

H
α 0 + β1
00

H
0

00

0 H

00

Ce réseau n’est que la première étape, celle de l’encodage redondant. Il faut encore
installer le circuit correcteur puis celui de désencodage qui extrait ψ = α 0 + β 1 de
ψ 0 dans tous les cas d’une inversion de bit ou de phase. On voit que le réseau commence à
prendre de l’ampleur exigeant un nombre croissant de qubits auxiliaires. La situation
s’aggraverait évidemment dans le cas d’une altération supplémentaire par σy ou dans le cas
d’une altération de plusieurs qubits. Toutefois, malgré le caractère inquiétant de ces
complications, on peut montrer que le nombre de portes nécessaires ne croît que
polynomialement ce qui permet de ne pas disqualifier la méthode.

Bob, Alice et les autres.

Les applications qui suivent impliquent, de près ou de loin, une communication à

distance selon un canal de transmission. On ne s’étonnera pas que le photon soit considéré,
dans ces cas, comme le système idéal d’encodage des qubits.

Nous poserons systématiquement le problème de la manière suivante : deux

correspondants, traditionnellement appelés, Alice et Bob, désirent échanger de l’information.
Alice est par convention l’émettrice et Bob le receveur. Nous admettrons que le canal de
transmission n’est pas bruité ou, si ce n’est pas le cas, que toutes les précautions ont été prises
en termes de protocoles de corrections d’erreurs.

22
 La théorie prévoit dans certains cas qui privilégient la confidentialité l’intervention
d’un troisième larron, baptisé Eve ( !), qui a pour mission d’espionner passivement les canaux
de transmission. L’espion actif, qui intercepte et falsifie la transmission dans un but
malveillant se nomme habituellement Oscar : ses interventions sont nettement plus
redoutables que celles d’Eve et elles nécessitent la mise en œuvre de protocoles évolués.
Nettement plus fréquentable est Walter, qui est chargé de certifier le bon déroulement des
transactions effectuées par Alice et Bob, par exemple, du type commerciales à distance.

Les applications qui impliquent une communication à distance sont nombreuses et

nous n’en retiendrons que trois : la cryptographie quantique, le codage dense et la
téléportation. Elles représentent les espoirs les plus sensés de l’informatique quantique de
l’an 2000. Le fait est que la communication n’implique que la maîtrise au compte-gouttes de
photons isolés, faciles à préparer et à mesurer. La technologie sous-jacente est nettement
moins intimidante que celle qui déboucherait sur un ordinateur quantique.

Distribution quantique des clefs.

Nous avons vu par ailleurs qu’aucune méthode cryptographique classique n’est sûre.
Toutes les méthodes imaginables aussi tordues soient-elles contiennent l’information cachée
et sont de ce fait exposées à être dévoilées. La seule perspective qui s’offre aux encrypteurs
est de compliquer la tâche d’espions éventuels afin d’allonger tellement démesurément le
temps de décodage qu’il en devient prohibitif. La méthode RSA, dite à clefs publiques, ne
voit sa sécurité garantie que par la lenteur de l’ordinateur classique et par l’acte de foi que le
problème de la factorisation des entiers longs est incontournable et non polynomial.

Il nous faut quand même tempérer l’affirmation qu’aucune méthode cryptographique

classique n’est sûre : il existe bien une méthode classique fiable à 100% mais elle exige
d’utiliser une clef de (dé)chiffrement aléatoire aussi longue que le texte à encrypter et de ne
l’utiliser qu’une seule fois ! Si cette possibilité paraît ridicule, c’est évidemment que cette
clef doit être échangée entre les correspondants par un canal sûr et que dans ces conditions on
a aussi vite fait d’utiliser ce canal sûr pour échanger le message lui-même ! Elle a pourtant
été mise à l’essai en utilisant des porteurs de confiance, le texte crypté n’étant échangé que
lorsqu’il était certain que la clef était parvenue, sans encombres, à destination. Ces essais
n’ont pas survécu aux coûts de la manœuvre.

La théorie quantique de l’information rend cependant une nouvelle jeunesse à cette

méthode. Bennett et Brassard ont en effet mis au point un protocole peu coûteux qui assure
une transmission inviolable des clefs. Plus exactement les deux correspondants, Alice et Bob,
ont la possibilité d’échanger une clef en ayant la certitude que si elle est interceptée par un
espion, Eve, ils en seront informés. Ce n’est que lorsqu’ils ont la certitude de n’avoir pas été
espionnés qu’il peuvent échanger en toute quiétude le message crypté sur un canal qui n’a
même pas besoin d’être sûr.

La méthode exige deux canaux de communication entre Alice et Bob. Le premier

canal achemine au compte-gouttes des photons, dans divers états de polarisation linéaire, le
long d’une fibre optique par exemple. Le second est une voie de communication classique
dont nous préciserons l’usage ultérieurement. Voyons d’abord comment les choses se passent
dans le cas idéal où aucun espion n’est présent. Alice envoie à Bob des photons qu’elle

23
prépare individuellement et aléatoirement dans un des quatre états de polarisation linéaire, x,
y ou à 45° dans les deux sens, soit schématiquement, {-, | }∈mode(+) et { /, \}∈mode(X).
Alice associe, à sa convenance, les valeurs ‘0’ et ‘1’ à chaque état complémentaire et elle ne
change jamais de convention. Par exemple, elle envoie les photons suivants, en respectant
l’encodage, (- ou \ →’0’ et | ou /→’1’) :

- | / - \ / \ \ \ \ / - / / - - \ \ | / | - - (suite aléatoire sur l’alphabet, - | / \)

01100 100001011 000 0111 00 (sa traduction en ‘0’ et en ‘1’)

+ ++ XX XX ++ + ++ X + + +X ++ X+ X X (bases choisies aléatoirement par Bob)

- || / \ / \ -| - -- / | - -\ - | / | \ / (résultats des mesures faites par Bob)
011 10100100011 000 0111 10 (leur traduction en ‘0’ et ‘1’)

Bob est parfaitement au courant de l’orientation des axes x et y (les deux

correspondants peuvent se mettre d’accord lors d’un échange préparatoire d’information
banale) ainsi que de l’encodage des bits adopté par Alice (en l’occurrence, - et \ pour encoder
‘0’ et | et / pour encoder ‘1’) mais il ignore totalement la suite (aléatoire) des orientations des
polariseurs choisies par Alice lors de l’encodage. Il procède néanmoins à un décodage en
variant lui aussi aléatoirement l’orientation de ses propres polariseurs selon les bases + ou X.
Il va de soi qu’il se trompe d’orientation en moyenne une fois sur deux (les choix erronés ont
été soulignés dans l’exemple cité).

Lorsque cette opération est terminée, les deux correspondants prennent contact par une
voie téléphonique quelconque qui n’a pas besoin d’être sécurisée et dressent la liste des
numéros d’ordre des photons pour lesquels ils ont fortuitement adopté la même orientation
des polariseurs. Les bits restants, en gros la moitié des bits transmis, constituent une clef
secrète potentiellement valable. Dans l’exemple, la clef qui subsisterait s’écrirait : 0 1 0 1 0 0
1 0 0 0 1 1 1. Toutefois il ne serait pas raisonnable de l’utiliser telle quelle. Les
correspondants doivent, en effet, absolument contrôler l’absence d’intervention d’Eve. Pour
ce faire, il existe une méthode élégante qui fait le prix de la cryptographie quantique : il suffit
que Bob et Alice échangent par téléphone une partie de la clef obtenue de part et d’autre, par
exemple les bits impairs ou multiples de 4 et qu’ils les jettent à la poubelle par mesure de
précaution. Si ce sondage révèle une coïncidence parfaite c’est que le canal de transmission
est resté inviolé. Par contre que faut-il penser du cas où Eve a espionné le canal de
transmission ?

Posons-nous la question autrement : de quels moyens Eve dispose-t-elle pour

espionner ce canal ? Au pis, elle pourrait : 1) être informée des orientations utilisées, + et X,
2) intercepter les photons envoyés par Alice et procéder à leur mesure enfin, 3) renvoyer les
photons vers Bob dans l’état où sa mesure les a projeté. Par contre, elle ne connaît aucune des
suites aléatoires des orientations des polariseurs choisies par Alice et par Bob. Elle en est
donc réduite à se choisir sa propre suite mais cela va altérer gravement l’état des photons que
Bob va recevoir. Alice et Bob vont immanquablement s’en apercevoir lors de leur sondage.

En effet, Eve va se tromper dans l’orientation des polariseurs en moyenne une fois sur
deux. Les photons qu’elle va retransmettre à Bob vont provoquer un taux d’erreur sur la clef
de 25% ce dont Alice et Bob vont inévitablement se rendre compte lors de la phase de

24
contrôle. S’il s’avère que la transmission a été interceptée, Alice et Bob interrompent de
commun accord leur échange sinon Alice envoie le message crypté selon la clef définie.

Il existe des stratégies d’espionnage plus subtiles où Eve peut intriquer les photons
interceptés en provenance d’Alice avec des photons ancillaires de sa fabrication avant de les
renvoyer vers Bob dans leur forme altérée. Quelle que soit la méthode retenue par Eve, il lui
est impossible de faire descendre le taux d’erreurs en-dessous de 15%, une valeur largement
suffisante pour être détectée lors du sondage de contrôle. Entre les cas extrêmes où le taux
d’erreur est nul (où l’échange du message codé peut se faire en toute sécurité) et celui où il est
supérieur à 15% (où l’échange doit être interrompu), les choses se compliquent du fait qu’il
est impossible de savoir si les erreurs constatées sont dues à un bruit dans le canal de
transmission ou à un espion qui tenterait de se camoufler en n’interceptant qu’une partie des
photons. Dans de tels cas il faut recourir à des techniques plus sophistiquées qui préservent la
confidentialité. Ces techniques débordent d’un exposé élémentaire.

Il existe une multitude d’attaques variées possibles et de réponses adaptées qu’il est
impossible de détailler dans un exposé élémentaire. Cela étant, la distribution quantique des
clefs n’est plus une fiction : les premiers essais, entrepris à Genève dès 1995, banques
obligent !, sont plus qu’encourageants. Plusieurs sociétés, américaines (NEC et NiCT) et
japonaises (JST) ont commencé à développer un produit commercial et quelques banques
s’intéressent à la publicité que représenterait la protection définitive des données sensibles.

Codage dense.

L’intrication permet à Alice de communiquer deux bits d’informations à Bob en ne lui

envoyant qu’un seul photon, cela s’appelle le codage dense. Cette performance ne contredit
en rien l’affirmation selon laquelle tout qubit ne peut révéler in fine qu’un seul bit
d’information au sens classique du terme : le codage dense implique effectivement deux
photons appartenant à une même paire EPR. Mais le canal qui relie Alice à Bob n’a à en
acheminer qu’un seul. Voici le principe du protocole utilisé.

Alice Bob

Source

Une source EPR émet deux photons intriqués sous la forme,

ψ0 =
1
( 00 + 11 ) ,
2

l’un vers Alice et l’autre vers Bob. Alice reçoit deux bits classiques autorisant l’encodage de
4 messages distincts, numérotés de 0 à 3, qu’elle veut pouvoir envoyer à Bob en n’envoyant
qu’un seul photon. Selon le message à transmettre, elle soumet le photon reçu à l’une des
quatre transformations unitaires suivantes et renvoie le résultat à Bob :

25
0 ψ 0' = Id ⊗ Id ψ 0  ψ 0' =
1
( 00 + 11 )
2
1 ψ 0' = X ⊗ Id ψ 0  ψ 0' =
1
( 10 + 01 )
2
2 ψ 0' = Y ⊗ Id ψ 0  ψ 0' =
1
(− 10 + 01 )
2
3 ψ 0' = Z ⊗ Id ψ 0  ψ 0' =
1
( 10 − 11 )
2

où les opérateurs réels, I, X, Y et Z sont apparentés aux matrices de Pauli :

1 0  0 1  0 1 1 0 
Id =   X =   Y =   Z =   .
 0 1 1 0 − 1 0  0 − 1

Naturellement Alice n’a pu altérer que le premier qubit, celui qu’elle a reçu
physiquement, l’autre est resté intact.

Lorsque Bob reçoit le photon réémis par Alice, il soumet la paire réunie dans son
laboratoire à une porte CNot. Le calcul montre que Bob peut mesurer le second qubit sans
altérer le premier, en effet :

0 ψ 0'' = cNot ψ 0'  ψ 0'' =

1
( 00 + 10 )
2
1 ψ 0'' = cNot ψ 0'  ψ 0'' =
1
( 11 + 01 )
2
2 ψ 0'' = cNot ψ 0'  ψ 0'' =
1
(− 11 + 01 )
2
3 ψ 0'' = cNot ψ 0'  ψ 0'' =
1
( 00 − 10 )
2

Si le second qubit est mesuré par Bob à la valeur ‘0’ (resp. ‘1’), c’est qu’on est dans
les cas 0 ou 3 (resp. 1 ou 2). Bob peut maintenant appliquer une porte de Hadamard au
premier qubit et la mesure permet de trouver le message d’origine, en effet :

0 ψ 0''' = H
1
( 0 + 1 ) 0  ψ 0''' = 00
2
1 ψ 0''' =H
1
( 1 + 0 ) 1  ψ 0''' = 01
2
2 ψ 0''' =H
1
(− 1 + 0 ) 1  ψ 0''' = 11
2
3 ψ 0''' =H
1
( 0 − 1 ) 0  ψ 0''' = 01
2

26
Téléportation.

La téléportation est en un certain sens, que l’on va préciser, l’opération inverse du

codage dense. Il s’agit de transmettre, par voie classique, l’information suffisante pour être en
mesure de reconstruire de toute pièce et à distance un état quantique inconnu mais donné. Il
va de soi que le prix à payer pour cette téléportation est la destruction de l’état quantique
source sinon on aurait contrevenu au « no cloning theorem ».

Imaginons qu’Alice dispose d’un état, φ, qu’elle ne connaît pas mais qu’elle veut
transmettre à Bob par un canal classique,

φ = a0 +b1

Elle dispose pour ce faire d’un des photons d’une paire EPR dont l’autre est en
possession de Bob. L’état de la paire est décrit par :

ψ0 =
1
( 00 + 11 ) .
2

φ = a 0 + b1 Alice Bob

Source

Alice et Bob vont en fait inverser l’ordre des manoeuvres effectuées lors du codage
dense : Alice commence par combiner les états , φ et ψ0, sous la forme,

φ ⊗ Ψ0 =
1
(a 000 + a 011 + b 100 + b 111 ) .
2

En se souvenant qu’elle ne contrôle que les deux premiers bits, elle soumet cet état aux
transformations successives, cNot⊗Id puis H⊗Id⊗Id :

( H ⊗ Id ⊗ Id )( cNot ⊗ Id )( φ ⊗ Ψ 0 ) =
1
( 00 ( a 0 + b 1 ) + 01 ( a 1 + b 0 ) + 10 ( a 0 − b 1 ) + 11 ( a 1 − b 0 ))
2

Ensuite elle mesure les deux premiers bits, trouvant, avec des probabilités égales,
l’une des quatre possibilités, ‘00’, ’01’, ’10 ou ’11’ mais détruisant par là même l’état à
transmettre. Toutefois l’information suffisante est sauvée qui va permettre à Bob de le
reconstruire à distance. En effet celui-ci va recevoir par un canal classique le résultat de la
mesure d’Alice, ‘01’ par exemple. Or il connaît la table de reconversion des bits reçus :

27
‘00’  φ = Id ( a 0 + b 1 )
‘01’  φ = X(a 1 − b 0 )
‘10’  φ = Z( a 0 − b 1 )
‘11’  φ = Y(a 1 − b 0 )

Il suffit à Bob d’appliquer la bonne transformation au photon qu’il a reçu de la source

EPR pour qu’il le projette dans l’état demandé, φ = a 0 + b 1 , dans tous les cas.

28