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