Substitut de Communication Par Intrication Quantique

Substitut de Communication Par Substitut de Communication Par Intrication QuantiqueIntrication Quantique

(Article de Richard Cleve et Harry Buhrman)(Article de Richard Cleve et Harry Buhrman)

IQ – 2006 – Matthieu CastebrunetIQ – 2006 – Matthieu Castebrunet

SommaireSommaire

IntroductionIntroduction QuestionQuestion Réponse et explication 1Réponse et explication 1 Réponse et explication 2Réponse et explication 2 Apport supplémentaireApport supplémentaire ConclusionConclusion

IntroductionIntroduction

Physique classique :Physique classique : phénomène d'intrication => communicationphénomène d'intrication => communication

Physique quantique :Physique quantique : pas de communication, pas même simuléepas de communication, pas même simulée

ExempleExemplef(x, y) = x1 + · · · + xn + y1 + · · · + yn

=> 1 bit transféré

f(x, y) = x1 · y1 + · · · + xn · yn => n bits transférés

Complexité de communicationComplexité de communication de de ff

QuestionQuestion

Est-ce que Est-ce que l'intrication peut réduire lal'intrication peut réduire lacomplexité de communication de complexité de communication de ff ? ?

ConsidérationsConsidérations Réponses pour n Réponses pour n 3 : 3 :

=> avec intrication, 2 bits sont => avec intrication, 2 bits sont suffisantssuffisants

=> sans intrication, 3 bits sont => sans intrication, 3 bits sont nécessairesnécessaires=> sans intrication, 3 bits sont => sans intrication, 3 bits sont suffisantssuffisants

Réponse et explication 1Réponse et explication 1

Avec intrication, 2 bits sont suffisantsAvec intrication, 2 bits sont suffisants

L'intrication concerne 3n qubits, n pour chacune L'intrication concerne 3n qubits, n pour chacune des parties A(lice), B(ob) et C(arol)des parties A(lice), B(ob) et C(arol)

Notation : Notation : Les N bits d'entrée de Y sont notés Les N bits d'entrée de Y sont notés xY = xY = xYxY11, … , xY, … , xYnn

Les N qubits de Y sont notés Les N qubits de Y sont notés qYqY11, … , qY, … , qYnn

Pour chaque Pour chaque ii, le triplet qA, le triplet qAii, qB, qBii, qC, qCii est dans est dans l'état:l'état:

½ (|001> + |010> + |100> - |111>)½ (|001> + |010> + |100> - |111>)

Réponse et explication 1Réponse et explication 1

Avec intrication, 2 bits sont suffisantsAvec intrication, 2 bits sont suffisants But de A : Calculer f(xA, xB, xC)But de A : Calculer f(xA, xB, xC) Protocole :Protocole :

Pour chaque partie P dans {A, B, C}Pour chaque partie P dans {A, B, C} Pour chaque i de {1, … , n}Pour chaque i de {1, … , n}

Si xPi = 0 Alors appliquer H à qPiSi xPi = 0 Alors appliquer H à qPi (H: Hadamard)(H: Hadamard)sPi = Mesurer qPi sPi = Mesurer qPi (base standard)(base standard)

sP = sP1 + … + sPnsP = sP1 + … + sPn (+ mod 2)(+ mod 2)B (resp. C) envoie sB (resp. sC) à AB (resp. C) envoie sB (resp. sC) à AA calcule sA + sB + sCA calcule sA + sB + sC

Selon la condition originale, xA + xB + xC = 1Selon la condition originale, xA + xB + xC = 1

On a On a sA + sB + sC = f(xA, xB, xC)sA + sB + sC = f(xA, xB, xC)

Réponse et explication 1Réponse et explication 1

Avec intrication, 2 bits sont suffisantsAvec intrication, 2 bits sont suffisants Preuve : Preuve :

sA + sB + sC = f(xA, xB, xC)sA + sB + sC = f(xA, xB, xC) car car sAi + sBi + sCi = xAi sAi + sBi + sCi = xAi · xBi xBi · xCi xCi Selon condition originelle, xAi xBi xCi Selon condition originelle, xAi xBi xCi {001, 010, 100, 111} {001, 010, 100, 111}

Cas 111 :Cas 111 :Pas de H appliquée à Pas de H appliquée à qAi, qBi ou qCi, donc |qAi qBi qCi> est mesuré dans qAi, qBi ou qCi, donc |qAi qBi qCi> est mesuré dans l'état : l'état : ½ (|001> + |010> + |100> - |111>)½ (|001> + |010> + |100> - |111>)

=> => sAi + sBi + sCi = 1 = sAi + sBi + sCi = 1 = xAi xAi · xBi xBi · xCi xCi

Cas 001 (et par symétrie, 010 et 100) :Cas 001 (et par symétrie, 010 et 100) : |qAi qBi qCi> est mesuré dans l'état : |qAi qBi qCi> est mesuré dans l'état :

H H H H I ( I (½ (|001> + |010> +|100> +|111>)) = ½ (|001> + |010> +|100> +|111>)) = ½ (|011> + |101> + |000> - |110>)½ (|011> + |101> + |000> - |110>)

=> => sAi + sBi + sCi = 0 = sAi + sBi + sCi = 0 = xAi xAi · xBi xBi · xCi xCi

Réponse et explication 2Réponse et explication 2

Sans intrication, 3 bits sont nécessairesSans intrication, 3 bits sont nécessaires Principe : Prouver que 2 bits ne suffisent pas. Principe : Prouver que 2 bits ne suffisent pas.

Avec deux bits, seule solution enviseageable : Avec deux bits, seule solution enviseageable : B broadcast 1 bit à A et CB broadcast 1 bit à A et C, puis , puis C envoie un bit à AC envoie un bit à A..

Solution : partitionner l'espace des possibilités de chacun Solution : partitionner l'espace des possibilités de chacun en deux sous-groupes et communiquer l'indice de ce sous-en deux sous-groupes et communiquer l'indice de ce sous-groupe ( 0 ou 1)groupe ( 0 ou 1)

B communique son sous-groupe à A et C.B communique son sous-groupe à A et C. C doit pouvoir envoyer un bit qui permette à A de C doit pouvoir envoyer un bit qui permette à A de

déterminer le résultat du calcul.déterminer le résultat du calcul.=> Dans toutes les situations, il y a ambiguité pour A sur les => Dans toutes les situations, il y a ambiguité pour A sur les

données de C ou C ne peut pas construire de partition données de C ou C ne peut pas construire de partition binaire permettant d'indiquer son résultat.binaire permettant d'indiquer son résultat.

Apport supplémentaireApport supplémentaireSans intrication, 3 bits sont Sans intrication, 3 bits sont suffisantssuffisants

Idée : Compter le nombre de 0 total dans toutes les 3n entrées (Ce nombre est Idée : Compter le nombre de 0 total dans toutes les 3n entrées (Ce nombre est pair selon la condition originelle)pair selon la condition originelle)

Si xi Si xi · yi yi · zi = 1 alors pas de 0 dans {xi zi = 1 alors pas de 0 dans {xi , yi yi , zi }zi }

Si xi Si xi · yi yi · zi = 0 alors deux 0 dans {xi zi = 0 alors deux 0 dans {xi , yi yi , zi } (cf. xi+yi+zi =1) zi } (cf. xi+yi+zi =1)

Np est le nombre de 0 dans xP (Na + Nb + Nc =2k, où k est le nombre total Np est le nombre de 0 dans xP (Na + Nb + Nc =2k, où k est le nombre total de termes égal à 0 dans {x1de termes égal à 0 dans {x1·y1y1·z1, … ,xnz1, … ,xn·ynyn·zn} )zn} )

A peut calculer A peut calculer f(x, y, z) = (n-k) mod 2f(x, y, z) = (n-k) mod 2 avec uniquement la parité de k. B avec uniquement la parité de k. B et C peuvent envoyer le mod 4 de leur N (et C peuvent envoyer le mod 4 de leur N (4bit tranférés4bit tranférés). ).

Comme on a parité du nombre de 0, l'un des deux peux envoyer seulement le Comme on a parité du nombre de 0, l'un des deux peux envoyer seulement le bit de poids fort => bit de poids fort => 3 bits transférés3 bits transférés

ConclusionConclusion

Dans certains cas, l'intrication permet de Dans certains cas, l'intrication permet de réduire la complexité de communication réduire la complexité de communication d'une fonction à données répartiesd'une fonction à données réparties

L'approche de l'intrication Quantique ne L'approche de l'intrication Quantique ne simule pas une communicationsimule pas une communication

Classique / QuantiqueClassique / Quantique