444
Physique quantique : Fondements
Le gain de l’algorithme de Grover est limité : on passe de N opérations à
√
N opérations. Un exemple où le gain est exponentiel est celui de la détermination de la période d’une fonction f (x). Supposons f (x) définie sur Z N ,l e
groupe additif des entiers modulo N ; un algorithme mis en œuvre sur un ordinateur classique exige un nombre d’opérations de l’ordre de N , alors qu’avec
un ordinateur quantique, ce nombre serait O(ln
2 N ).C er é s u l t a te s tàl ab a s e
de l’algorithme de Shor pour la décomposition d’un nombre en facteurs premiers, la fonction f (x) étant alors a
x mod.N, a entier. Pour un entier N , cet
algorithme requiert O(ln
3 N ) opérations sur un ordinateur quantique, alors
que les meilleurs algorithmes classiques exigent O(exp[(ln N )
1/3 ]) opérations.
Le principe d’algorithmes fonctionnant sur des ordinateurs quantiques
étant acquis, reste la réalisation concrète d’un tel ordinateur. Les avis sur
cette question sont partagés : ils vont du pessimisme intégral à un optimisme
mesuré. À l’heure actuelle, le record en nombre de qubits est détenu par un
groupe d’IBM (Vandersypen et al. [2001]), qui a obtenu la factorisation de 15 :
15 = 3 × 5 ( !) à l’aide d’un ordinateur quantique utilisant la RMN, mais on
est encore très loin de résultats utiles. Un autre schéma prometteur est fondé
sur la manipulation d’ions piégés (exercice 11.6.15). Le principal problème
est celui de la décohérence : en effet, les algorithmes quantiques exigent que
l’évolution soit unitaire, ce qui implique l’absence d’interactions incontrôlées
avec l’environnement, Bien sûr, isoler complètement l’ordinateur quantique
est impossible : il s’agit de réduire au maximum les perturbations induites
par l’environnement et de concevoir des algorithmes de correction d’erreurs
inévitables en utilisant une information redondante. En dépit des difficultés,
le domaine du calcul quantique est en pleine expansion.
11.5.3 Téléportation quantique
La téléportation quantique permet de transférer de l’information quantique
d’un endroit à un autre sans que ce transfert s’accompagne de la propagation
entre ces deux endroits d’une particule qui porte l’information. Elle pourrait
avoir des applications pour la cryptographie quantique (figure 11.14). Supposons qu’Alice souhaite transférer à Bob l’information sur l’état de spin |ϕ A
d’une particule A de spin 1/2
|ϕ A = λ|0 A + µ|1 A
(11.131)
qui lui est a priori inconnu, sans lui transmettre directement cette particule.
Elle ne peut pas faire une mesure du spin, car elle ne connaît pas l’orientation
du spin de la particule A, et toute mesure projetterait en général |ϕ A sur
un autre état. Le principe du transfert de l’information consiste à utiliser une
paire auxiliaire de particules intriquées B et C de spin 1/2 partagées par Alice
et Bob : la particule B est utilisée par Alice et la particule C est envoyée vers
Bob (figure 11.14). Ces particules B et C se trouvent, par exemple, dans l’état
Physique quantique : Fondements
Le gain de l’algorithme de Grover est limité : on passe de N opérations à
√
N opérations. Un exemple où le gain est exponentiel est celui de la détermination de la période d’une fonction f (x). Supposons f (x) définie sur Z N ,l e
groupe additif des entiers modulo N ; un algorithme mis en œuvre sur un ordinateur classique exige un nombre d’opérations de l’ordre de N , alors qu’avec
un ordinateur quantique, ce nombre serait O(ln
2 N ).C er é s u l t a te s tàl ab a s e
de l’algorithme de Shor pour la décomposition d’un nombre en facteurs premiers, la fonction f (x) étant alors a
x mod.N, a entier. Pour un entier N , cet
algorithme requiert O(ln
3 N ) opérations sur un ordinateur quantique, alors
que les meilleurs algorithmes classiques exigent O(exp[(ln N )
1/3 ]) opérations.
Le principe d’algorithmes fonctionnant sur des ordinateurs quantiques
étant acquis, reste la réalisation concrète d’un tel ordinateur. Les avis sur
cette question sont partagés : ils vont du pessimisme intégral à un optimisme
mesuré. À l’heure actuelle, le record en nombre de qubits est détenu par un
groupe d’IBM (Vandersypen et al. [2001]), qui a obtenu la factorisation de 15 :
15 = 3 × 5 ( !) à l’aide d’un ordinateur quantique utilisant la RMN, mais on
est encore très loin de résultats utiles. Un autre schéma prometteur est fondé
sur la manipulation d’ions piégés (exercice 11.6.15). Le principal problème
est celui de la décohérence : en effet, les algorithmes quantiques exigent que
l’évolution soit unitaire, ce qui implique l’absence d’interactions incontrôlées
avec l’environnement, Bien sûr, isoler complètement l’ordinateur quantique
est impossible : il s’agit de réduire au maximum les perturbations induites
par l’environnement et de concevoir des algorithmes de correction d’erreurs
inévitables en utilisant une information redondante. En dépit des difficultés,
le domaine du calcul quantique est en pleine expansion.
11.5.3 Téléportation quantique
La téléportation quantique permet de transférer de l’information quantique
d’un endroit à un autre sans que ce transfert s’accompagne de la propagation
entre ces deux endroits d’une particule qui porte l’information. Elle pourrait
avoir des applications pour la cryptographie quantique (figure 11.14). Supposons qu’Alice souhaite transférer à Bob l’information sur l’état de spin |ϕ A
d’une particule A de spin 1/2
|ϕ A = λ|0 A + µ|1 A
(11.131)
qui lui est a priori inconnu, sans lui transmettre directement cette particule.
Elle ne peut pas faire une mesure du spin, car elle ne connaît pas l’orientation
du spin de la particule A, et toute mesure projetterait en général |ϕ A sur
un autre état. Le principe du transfert de l’information consiste à utiliser une
paire auxiliaire de particules intriquées B et C de spin 1/2 partagées par Alice
et Bob : la particule B est utilisée par Alice et la particule C est envoyée vers
Bob (figure 11.14). Ces particules B et C se trouvent, par exemple, dans l’état