11. Intrication et non localité quantiques
441
principe d’un tel calcul est le suivant : un registre de données à n qubits stocke
un état |Φ (11.124). On construit ensuite le produit tensoriel |Ψ de |Φ avec
l’état |0
⊗m d’un registre de résultats à 2
m
qubits
|Ψ = |Φ ⊗ 0
⊗m =
1
2 n/2
x
|x ⊗ 0
⊗m
(11.126)
Étant donné une fonction f (x) prenant 2
m
valeurs différentes stockées dans
le registre de résultats, on construit une opération unitaire
26 U f telle que
U f |x ⊗ y = |x ⊗ [y ⊕ f (x)]
où ⊕ est l’addition modulo 2 sans retenue. Il est clair que U
2
f = I,e tq u e
U f , qui est une simple permutation des vecteurs de base est une opération
unitaire. Si U f est appliqué sur |Ψ (11.126), le résultat est
|Ψ→|Ψ
′ = U f |Ψ =
1
2 n/2
x
|x ⊗ f (x)
L’ensemble des deux registres contient simultanément les 2
n+m
valeurs du
couple (x, f (x)), bien qu’une mesure donne toujours un couple unique. L’art
du calcul quantique consiste à construire des transformations unitaires conduisant à des états finaux tels que les valeurs de x qui nous intéressent soient
associées à des probabilités |a x |
2
importantes. C’est une caractéristique des
algorithmes quantiques de ne pas donner un résultat certain, mais de donner
le résultat avec une certaine probabilité que l’on essaie de rendre aussi grande
que possible. Un algorithme classique permet ensuite de vérifier rapidement
que le résultat est correct : par exemple, dans le cas de l’algorithme de Shor
qui permet de décomposer un nombre entier en facteurs premiers, une fois que
l’algorithme quantique a proposé une solution possible pour la factorisation,
cette solution peut être vérifiée rapidement sur un ordinateur classique. Nous
allons illustrer la méthode sur l’algorithme de recherche de Grover.C ’ e s tu n
algorithme qui permet de rechercher une entrée dans une base de données non
structurée, par exemple un numéro de téléphone dans un annuaire lorsque l’on
connaît le numéro, mais pas la personne dont on veut trouver le nom. Si N
est le nombre d’entrées dans la base, un algorithme classique doit effectuer en
moyenne N/2 essais : il n’y a pas d’autre possibilité que d’examiner une à une
toutes les entrées. L’algorithme de Grover permet de résoudre le problème en
∼
√
N opérations.
Soit n le nombre minimum de qubits nécessaire pour représenter le nombre
N ; afin de simplifier les notations, nous prendrons N =2
n
. L’algorithme
de Grover va utiliser n qubits stockés dans le registre de données, plus un
26. En dehors du cas où la correspondance x ↔ f (x) est bijective, la transformation
x → f (x) ne peut pas être réversible : on ne peut pas avoir de transformation U |x = |f (x).
441
principe d’un tel calcul est le suivant : un registre de données à n qubits stocke
un état |Φ (11.124). On construit ensuite le produit tensoriel |Ψ de |Φ avec
l’état |0
⊗m d’un registre de résultats à 2
m
qubits
|Ψ = |Φ ⊗ 0
⊗m =
1
2 n/2
x
|x ⊗ 0
⊗m
(11.126)
Étant donné une fonction f (x) prenant 2
m
valeurs différentes stockées dans
le registre de résultats, on construit une opération unitaire
26 U f telle que
U f |x ⊗ y = |x ⊗ [y ⊕ f (x)]
où ⊕ est l’addition modulo 2 sans retenue. Il est clair que U
2
f = I,e tq u e
U f , qui est une simple permutation des vecteurs de base est une opération
unitaire. Si U f est appliqué sur |Ψ (11.126), le résultat est
|Ψ→|Ψ
′ = U f |Ψ =
1
2 n/2
x
|x ⊗ f (x)
L’ensemble des deux registres contient simultanément les 2
n+m
valeurs du
couple (x, f (x)), bien qu’une mesure donne toujours un couple unique. L’art
du calcul quantique consiste à construire des transformations unitaires conduisant à des états finaux tels que les valeurs de x qui nous intéressent soient
associées à des probabilités |a x |
2
importantes. C’est une caractéristique des
algorithmes quantiques de ne pas donner un résultat certain, mais de donner
le résultat avec une certaine probabilité que l’on essaie de rendre aussi grande
que possible. Un algorithme classique permet ensuite de vérifier rapidement
que le résultat est correct : par exemple, dans le cas de l’algorithme de Shor
qui permet de décomposer un nombre entier en facteurs premiers, une fois que
l’algorithme quantique a proposé une solution possible pour la factorisation,
cette solution peut être vérifiée rapidement sur un ordinateur classique. Nous
allons illustrer la méthode sur l’algorithme de recherche de Grover.C ’ e s tu n
algorithme qui permet de rechercher une entrée dans une base de données non
structurée, par exemple un numéro de téléphone dans un annuaire lorsque l’on
connaît le numéro, mais pas la personne dont on veut trouver le nom. Si N
est le nombre d’entrées dans la base, un algorithme classique doit effectuer en
moyenne N/2 essais : il n’y a pas d’autre possibilité que d’examiner une à une
toutes les entrées. L’algorithme de Grover permet de résoudre le problème en
∼
√
N opérations.
Soit n le nombre minimum de qubits nécessaire pour représenter le nombre
N ; afin de simplifier les notations, nous prendrons N =2
n
. L’algorithme
de Grover va utiliser n qubits stockés dans le registre de données, plus un
26. En dehors du cas où la correspondance x ↔ f (x) est bijective, la transformation
x → f (x) ne peut pas être réversible : on ne peut pas avoir de transformation U |x = |f (x).