442
Physique quantique : Fondements
qubit auxiliaire stocké dans le registre de résultats. On part de l’état (voir la
figure 11.13)
|Ψ =(H
⊗n |0
⊗n ) ⊗ H|1 =
1
2 n/2
x
|x
⊗ (|0−|1)=|Φ⊗(|0−|1)
où le dernier qubit est le qubit auxiliaire et |Φ le vecteur (11.124). On applique
la porte U f
U f |Ψ =
1
2 n/2
x
(−1)
f (x) |x
⊗ (|0−|1)
En effet,
• Si f (x)=0, (|0−|1) → (|0−|1)
• Si f (x)=1, (|0−|1) →−(|0−|1).
Dans cette opération, le qubit auxiliaire reste non intriqué avec les n autres
qubits. Il est commode de définir un opérateur O, “l’oracle”, dont l’action est
la suivante dans la base de calcul
O|x =(−1)
f (x) |x
(11.127)
ce qui permet de limiter le raisonnement aux n qubits du registre de données.
La base de données est stockée au moyen de n qubits et on définit la
fonction f (x), x = {0, 1,...,2
n − 1} telle que f (x)=0si x = y et f (x)=1
si x = y est solution : f (x)=δ xy . Rappelons que la valeur de y est connue,
mais on ne sait pas où cette valeur se trouve dans la base
27
. Pour simplifier
l’argument, on suppose que la valeur de y est unique. L’opérateur de Grover G
est défini par
G=H
⊗n XH
⊗n O=H
⊗n
2|00|−I
H
⊗n O
(11.128)
où
X|x = −(−1)
δx0 |x =(2|00|−I)|x
Pour simplifier l’écriture, nous allons nous servir du vecteur |Φ (11.124).
Compte tenu de H
2 = I, on déduit
H
⊗n
2|00|−I
H
⊗n =2H
⊗n |00|H
⊗n − I =2|ΦΦ|−I
et donc
G=
2|ΦΦ|−I
O
(11.129)
Cette construction permet de dessiner le circuit logique quantique correspondant à G (figure 11.13).
27. On connaît la valeur de y (le numéro de téléphone), mais pas les données associées
à y dans la base (le nom de l’abonné).