Le problème posé
Pour decider d’un achat en Bourse pour le lendemain, une certaine fonction f doit être calculée pour les deux valeurs 0 et 1 de la variable, soit f(0)et f(1).
L’objectif est de determiner si f(0) = f(1) ou au contraire si f(0)et f(1) diffèrent.Il n’est pas nécessaire de connaitre ces valeurs.
Le calcul de chaque valeur prend 20 heures.
L’approche classique consistant à calculer les deux valeurs prenant 40 heures est inutilisable.
On va donc utiliser une approche quantique à deux qbits, b1 et b2, placés tous deux à l’origine en état |0>, soit pour le système |0>|0>.
Etat du système en Z1
On applique à b1 une porte Hadamard ce qui le place dans l’ état superposé |0>+|1>, dans la zone Z1.En réalité il faut multiplier par racine de 2, mais pour des raisons de clarté on négligera ces facteurs de normalisation dans la suite.
On rappel qu’un porte Hadamard transforme l’état |0> en état |0>+|1> et l’état |1> en état |0>-|1>.
On inverse b2 par une porte X, donc b2=|1>, puis via une porte Hadamard, on le place en état superposé |0>-|1>, dans la zone Z1.
Calcul parallèle
On applique la fonction f à b1 en état superposé.
f(0) et f(1) à la sortie de la porte f sont les bits de contrôle ( de la porte C Not) agissant sur b2.
On rappelle que le bit de contrôle(ici f(0), f(1)) d’une porte C Not, effectue un XOR avec la bit cible (ici b2).Ceci revient à inverser b2 si le bit de contrôle =1.
Etat du système en Z2
Avec b11 = 0, b12 = 1, b2= 0-1, du fait de la linéarité, l’état du système devient :|b11>|b2 xor f(0)> + |b12>|b2 xor f(1)>
soit
********|0>|(|0>-|1>)xorf(0)> + |1>|(|0>-|1>)xorf(1)>*******
et en notation allégée
*********(0)(0-1)xorf(0) + (1)(0-1)xorf(1)**********
On va maintenant distinguer les 4 cas possibles pour f :
f(0) = f(1) = 0 valeurs identiques
les deux xor laissent b2 inchangé.
L’état du système en Z3 devient :
*****0(0-1) + 1(0-1) = (0+1)(0-1)
f(0) = f(1) = 1 valeurs identiques
les deux xor inversent l’état de b2
*****0(1-0) + 1(1-0) = (0+1)(1-0)
f(0)=1, f(1)=0 valeurs différentes
le premier xor inverse b2
****0(1-0) + 1(0-1) = (0-1)(1-0)
f(0)=0, f(1)=1 valeurs différentes
le deuxième xor inverse b2
****0(0-1) + 1(1-0) = (0-1)(0-1)
Etat du système en Z3
On ne s’occupe plus du qbit b2.
On applique d’abord une porte Hadamard sur b1.
Les 4 cas precedents deviennent :
f(0) = f(1) = 0 valeurs identiques
(0+1)(0-1) devient
(0+1 + 0-1)(0-1)=2*0(0-1)
donc après mesure b1=0.
f(0) = f(1) = 1 valeurs identiques
(0+1)(1-0) devient
(0+1 +0-1)(1-0) = 2*0(1-0)
donc après mesure b1=0.
f(0)=1, f(1)=0 valeurs différentes
(0-1)(1-0) devient
(0+1 -0+1)(1-0) = 2*1(1-0)
donc après mesure b1=1.
f(0)=0, f(1)=1 valeurs différentes
(0-1)(0-1) devient
(0+1 -0+1)(0-1) = 2*1(0-1)
donc après mesure b1=1.
Conclusion
Après 20 heures de calcul, le bit b1 fournit donc le resultat attendu, sans ambiguïté : b1 = 0, les deux valeurs de f sont
égales
b1 = 1, les deux valeurs de f sont
différentes
Reference :Minds, Machines, and the Multiverse : THE QUEST FOR THE QUANTUM COMPUTER par Julian Brown.
