11. Intrication et non localité quantiques
443
1
GG
OX
H
H
H
H
H
H
H
H
0
0
0
H
H
Fig. 11.13 – Circuits logiques de l’algorithme de Grover pour n =3: 3 qubits et
un qubit auxiliaire, qui reste non intriqué. Les circuits de G sont détaillés sur la
figure de droite. L’action de l’oracle O est O|x =(−1)
f (x) |x et celle de la boîte X :
X|x = −(−1)
δ x0 |x.
La première itération de l’algorithme va nous montrer comment le résultat
souhaité est obtenu en utilisant un mécanisme d’interférences. Après application de l’opérateur de Grover sur H
⊗n |0, le vecteur d’état du registre de
données est
|Φ
′ =
1
√
N
x
(−1)
f (x)
2|ΦΦ|−I
|x
=
z
2
N
(−1)
f (z)
|Φ−
1
√
N
x
(−1)
f (x) |x
=
1
√
N
x
2
N
z
(−1)
f (z) − (−1)
f (x)
|x
=
x
a x |x
(11.130)
où nous avons utilisé Φ|x =1 /
√
N . Prenons pour fixer les idées n =4 ,
N =16. Les amplitudes a x=y et a x =y sont différentes ; d’après (11.130)
a x =y =
3
16
a x=y =
11
16
Au départ, chaque valeur de x avait une probabilité de 1/16 ≃ 0.06,alorsque
la probabilité de trouver la valeur y dans la base de données après application
de G est 121/256 ≃ 0.47, soit près de 50 %. Le raisonnement précédent peut
manifestement servir à établir une relation de récurrence pour les applications
successives de G, mais il est plus commode d’avoir recours à une méthode
géométrique que le lecteur trouvera exposée dans les références.
443
1
GG
OX
H
H
H
H
H
H
H
H
0
0
0
H
H
Fig. 11.13 – Circuits logiques de l’algorithme de Grover pour n =3: 3 qubits et
un qubit auxiliaire, qui reste non intriqué. Les circuits de G sont détaillés sur la
figure de droite. L’action de l’oracle O est O|x =(−1)
f (x) |x et celle de la boîte X :
X|x = −(−1)
δ x0 |x.
La première itération de l’algorithme va nous montrer comment le résultat
souhaité est obtenu en utilisant un mécanisme d’interférences. Après application de l’opérateur de Grover sur H
⊗n |0, le vecteur d’état du registre de
données est
|Φ
′ =
1
√
N
x
(−1)
f (x)
2|ΦΦ|−I
|x
=
z
2
N
(−1)
f (z)
|Φ−
1
√
N
x
(−1)
f (x) |x
=
1
√
N
x
2
N
z
(−1)
f (z) − (−1)
f (x)
|x
=
x
a x |x
(11.130)
où nous avons utilisé Φ|x =1 /
√
N . Prenons pour fixer les idées n =4 ,
N =16. Les amplitudes a x=y et a x =y sont différentes ; d’après (11.130)
a x =y =
3
16
a x=y =
11
16
Au départ, chaque valeur de x avait une probabilité de 1/16 ≃ 0.06,alorsque
la probabilité de trouver la valeur y dans la base de données après application
de G est 121/256 ≃ 0.47, soit près de 50 %. Le raisonnement précédent peut
manifestement servir à établir une relation de récurrence pour les applications
successives de G, mais il est plus commode d’avoir recours à une méthode
géométrique que le lecteur trouvera exposée dans les références.