***Pour revenir à la page d’accueil** ICI
David Deutsch en 1985 a posé ce problème et proposé une solution partielle, complétée par A.Ekert en 1996.
Cet exemple met en exergue le parallélisme intrinsèque du calcul quantique.
NOTA : Pour une amusante introduction au calcul quantique sous forme de bande dessinée :
https://www.smbc-comics.com/comic/t...
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>.
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.
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.
|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)
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.
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.