LOGO
Kvantum-kommunikáció komplexitása I. Gyöngyösi László BME Villamosmérnöki és Informatikai Kar
Klasszikus információ n kvantumbitben Hány klasszikus bitnyi információ nyerhető ki n kvantumbitből? Egy n kvantumbites kvantumállapot leírásához 2n1 komplex szám szükséges: 000000 + 001001 + 010010 + + 111111. Vajon a kvantumbitekben tárolható klasszikus információ mértéke exponenciálisan emelkedik a kvantumállapotok növelésével?
Holevo-tétel [1973] : Egy n kvantumbites rendszerből legfeljebb n bitnyi klasszikus információ nyerhető ki.
Holevo-tétel Unitér transzformáció:
ψ n kvantumbit
U
b1 b2 b3 bn
Az n kvantumbites állapotból legfeljebb n bitnyi információ nyerhető ki. A kimeneti b1b2 ... bn állapotok maximum n bitnyi információt hordozhatnak.
Kiegészítő kvantumállapotokkal:
ψ n kvantumbit
m kvantumbit
0 0 0 0 0
U
b1 b2 b3 bn bn+1 bn+2 bn+3 bn+4 bn+m
Holevo-tétel A Holevo-tétel értelmében egy n bites üzenet elküldéséhez legalább n kvantumbit szükséges. Összefonódott állapotok alkalmazásával a küldendő kvantumállapotok száma azonban n/2re csökkenthető (szupersűrűségű tömörítés) A szupersűrűségű tömörítés sérti a Holevotételt?
Szupersűrűségű tömörítés és Holevo Alice két klasszikus bitnyi üzenetet szeretne megosztani Bobbal, egyetlen kvantumállapot elküldésével
ab
ab A Holevo-tétel alapján azonban erre nincs lehetősége
Szupersűrűségű tömörítés és Holevo A protokoll kezdetén Bob elküldi Alicenek a kommunikáció során felhasznált összefonódott állapot első kvantumbitjét
ab
ab Azonban ezzel hogyan kerülhető el a Holevo-tétel megsértése?
Szupersűrűségű tömörítés és Holevo 1. Bob előállítja a 00 + 11 összefonódott állapotot, majd az első kvantumbitet elküldi Alice-nek 2. Alice: ha a = 1 akkor X -transzformációt alkalmaz a kapott kvantumbitre ha b = 1 akkor Z- transzformációt. A transzformált kvantumállapot visszaküldi Bobnak
0 1 X 1 0
1 0 Z 0 1
ab
állapot
00
00 + 11
01
00 − 11
10
01 + 10
11
01 − 10
3. Bob a kapott állapotát beméri a Bell-bázis elemei szerint.
Mérés a Bell-bázisban Bob egy C-NOT és egy Hadamardkaput alkalmaz a két kvantumállapotra: BE
H
KI
00 + 11
00
00 − 11
01
01 + 10
10
01 − 10
11
A kapott eredményt a Bell-bázis szerint bemérve visszakapja az ab kétbites üzenetet. A két-bites klasszikus üzenet továbbítása során két kvantumbitet küldtünk át a csatornán. A Holevo-tétel így nem sérül, azonban a feleknek csak 1-1 bitet kellett küldeniük! (Költség: n/2)
Kvantum-kommunikáció költsége A kvantum-számítások alkalmazásával jelentős redukció realizálható a klasszikus rendszereken belüli számítások költségéhez képest. Hogyan alakul a kvantumrendszerek kommunikációs költsége a klasszikus kommunikáció bonyolultságához viszonyítva? A kvantum-kommunikáció területén is elérhető a kvantumszámításokhoz hasonló mértékű előrelépés?
Összefonódott állapotok felhasználása Összefonódott állapot Alice és Bob között:
1 ( 00 + 11 ) 2 qubit
qubit
Az EPR-állapotokkal - klasszikus rendszerekben megvalósíthatatlan – kvantum-kommunikációs protokollok konstruálhatók (teleportáció, szupersűrűségű tömörítés) Az összefonódott állapot egyik kvantumbitjén végrehajtott lokális transzformáció nincs kihatással a második kvantumbit állapotára Azonban a kvantumbitek újraegyesíthetőek, a hibák detektálhatóak
A kommunikáció általános megközelítése Cél: Alice n bitjének eljuttatása Bob-hoz
x1x2 xn Erőforrás
x1x2 xn Kvantumrendszerek esetén hogyan alakul a kommunikációhoz felhasznált erőforrások mértéke?
Kommunikációs költségek Klasszikus kommunikáció:
Kvantum-kommunikáció:
Költség: n
Költség: n [Holevo-tétel]
Klasszikus kommunikáció és összefonódott állapotok:
Kvantum kommunikáció és összefonódott állapotok:
Költség: n
Költség: n/2 [szupersűrűségű tömörítés]
Három kvantumbites összefonódottság GHZ állapot: Greenberger, Horne és Zeilinger Alice, Bob és Carol megosztott állapota: |GHZ=(|000+|111)/√2.
A kommunikációban résztvevő felek a birtokukban lévő kvantumállapotot elforgathatják, rendre α,β illetve γ szöggel. A forgatás után a résztvevő felek mindegyike egy Hadamard-transzformációt alkalmaz a birtokában lévő kvantumállapotra, majd bemérik a kvantumbitjeiket a 0/1 rektilineáris bázisban.
GHZ játék szabályai Be:
r
s
t
Ki:
a ←r
b ← ¬s
c ←1
Alice
Bob
Játékszabályok: 1. A bemenetekre mindig teljesüljön:
rst = 0 2. A bemenet vétele utáni kommunikáció tilos 3. Győzelem feltétele: abc = rst
Carol
rst
abc
abc
000
0
011
011
1
001
101
1
111
110
1
101
Létezik tökéletes stratégia? Be:
r
s
t
Ki:
a ←r
b ← ¬s
c ←1
Alice
rst
abc
000
0
011
1
101
1
110
1
Bob
Carol
Létezik determinisztikus stratégia? a0, a1, b0, b1, c0, c1 Nyerési feltételek: a0 b0 c0 = 0 Az egyenletrendszernek a0 b1 c1 = 1 nincs megoldása, így egyértelmű nyerési a1 b0 c1 = 1 stratégia sem található a1 b1 c0 = 1
GHZ állapotok alkalmazása A felek kommunikálhatnak Carol-on keresztül, közvetlenül egymással azonban nem. Carol véletlenszerűen választ kérdést, a begyűjtött válaszok alapján pedig döntést hoz.
Megosztott GHZ állapot A megosztott GHZ-állapot : = 000 – 011 – 101 – 110 r s t Be: Ki:
a Alice
b Bob
c Carol
Alice stratégiája: 1. ha r = 1 akkor H-transzformációt alkalmaz 2. beméri a kvantumbitet, a kimenete: a Bob és Carol stratégiája ugyanez közvetlenül 2. eset: (rst = 000): 011): az új állapot:bemérjük az állapotot … 1. 001 + 010 – 100 + 111 3. és 4. eset: (rst = 101 & 110): hasonlóképpen adódik…
GHZ játék: Összefoglalás Klasszikus rendszereken belül, a GHZ játék nyerési valószínűsége legfeljebb ¾ lehet Az összefonódott állapotok segítségével a felek egymás közt nem képesek kommunikálni, azonban… …az összefonódott állapotokkal megvalósítható az 1 valószínűségű nyerési stratégiát garantáló kommunikáció Az összefonódott kvantumállapotok nem segítik a felek közti közvetlen kommunikációt, így a GHZ játék a rögzített szabályrendszer megsértése nélkül megnyerhető
A Bell egyenlőtlenség sérülése Kvantummechanikai megközelítés
Rejtett változók? Léteznek olyan rejtett változók, amelyek előre meghatározzák egy adott mérés kimenetelét?
Található olyan rejtett szabályszerűség, amely egy kvantumállapot tényleges bemérése előtt determinálja annak kimenetelét? Ha léteznek rejtett változók, akkor feltehetjük, hogy: - ha a {0,1} bázisban mérünk, a mérés kimenetele 0 - ha a {+,−} bázisban, akkor pedig 1: M1
A Bell egyenlőtlenség Legyen adott egy két-kvantumbites rendszer. Mindkét kvantumbitet bemérjük az M0 és M1 mérési operátornak megfelelően
M0 : a0 M1 : a1
Legyen: A0 = (1)a0 A1 = (1)a1 B0 = (1)b0 B1 = (1)b1
A részecskék között nincs fizikai kapcsolat
M0 : b0 M1 : b1
Állítás: A0 B0 + A0 B1 + A1B0 A1 B1 2 Bizonyítás: A0 (B0 + B1) + A1 (B0 B1) 2 az egyik 2, a másik 0
A Bell egyenlőtlenség A0 B0 + A0 B1 + A1B0 A1 B1 2 Kísérletileg is igazolható a Bell egyenlőtlenség? Közvetlenül nem, mivel A0, A1, B0, B1 egyszerre nem mérhetőek be. Egyszerre csak egy As Bt tag bemérése hajtható végre. Közvetetten igen, mivel ha választunk egy véletlen st {00, 01, 10, 11} értéket, majd mérünk az Ms és Mt - nek megfelelően, megkapjuk az As Bt értéket. Ezen folyamatot többször végrehajtva megkapjuk az A0 B0, A0 B1, A1B0, A1 B1 értékeket, amelyekre igaznak kellene lennie, hogy értékük ½.
A Bell egyenlőtlenség megsértése Legyen a rendszer állapota: = 1/√2(|00 – 11) A A és B szögű forgatások eredménye: cos(A + B ) 1/√2(00 – 11) + sin(A + B ) 1/√2(01 + 10) A B = +1
Legyen M0: forgatás /16 -al, majd mérés M1: forgatás +3/16 -al, majd mérés Ekkor az A0 B0, A0 B1, A1B0, A1 B1 tagok átlagértéke (½)√2=1/√2, amely ellentmond az ½ -es átlagértéknek.
AB = 1 st = 11 3/8
st = 01 vagy 10
/8 -/8
st = 00 cos2(/8) = 1/2 + (1/4)√2 = 0.853
A Bell egyenlőtlenség megsértése A0 B0 A0 B1 A1B0 A1B1 2 Bell állapotokra : 1 2 1 2
A0 B0 A0 B1 A1 B0 A1 B1 2
A
0
B0 A1 B1 A0 B1 A1 B0 2
A0B0 A0B1 A1B0 A1B1 2
2.
A0 B0 A0B1 A1B0 A1B1 2 2 4 2 2 1
2
A0 B0 A0B1 A1B0 A1B1 2 4 1 2 .
A0 B0 A0 B1 A1 B0 A1 B1
1 2
.
A Bell egyenlőtlenség megsértése Tegyük fel, hogy a rejtett változók léteznek, így teljesül a Bell egyenlőtlenség:
A0 B0 + A0 B1 + A1B0 A1 B1 2.
A Bell állapotok esetén azonban az egyenlőtlenség sérül (a megjelenő √2 – es szorzó következtében) Vagyis, a rejtett változók létezését kizárhatjuk! Az összefonódott állapotokkal kísérletileg is sikerült ellenőrizni a Bell egyenlőtlenség sérülését, valamint így kizárni a rejtett változók létezését
A Bell egyenlőtlenség megsértése Kvantuminformatikai megközelítés
A Bell egyenlőtlenség sérülése – CHSH Hogyan használhatjuk fel az informatikában a Bell egyenlőtlenség sérülését? s t bemenet:
kimenet:
a
b
Szabályok: 1. Tilos a bemenet vétele utáni kommunikáció 2. Nyerés feltétele: ab = st Klasszikus rendszerekben: Pr[ab = st] ≤ 0.75 Előzetesen megosztott 00 – 11 EPR-állapottal: Pr[ab = st] = cos2(/8) = ½ + ¼√2 = 0.853
st
ab
00
0
01
0
10
0
11
1
A Bell egyenlőtlenség és a CHSH játék Nyerés feltétele: ab = st Klasszikus Bell-egyenlőtlenség: Bchsh ≤ 2 Kvantum Bell-egyenlőtlenség: Bchsh ≤ 2√2 Nyerési valószínűség klasszikus rendszerekben: = 1/2 + (1/8)Bchsh = maximum. 3/4 Nyerési valószínűség kvantumrendszerekben: =1/2 + (1/8)Bchsh = 1/2 + (1/8) 2√2 = 0.853 (cos2(/8) = 1/2 + (1/4)√2 = 0.853) A klasszikus Bell-egyenlőtlenség sérül, nincsenek rejtett változók.
A kvantum stratégia Alice and Bob megosztott összefonódott állapota: = 00 – 11. Alice:
Bob:
ha s = 0: egyébként: ha t = 0: egyébként:
A = /16, majd mérés A = + 3/16, majd mérés
st = 11 3/8
B = /16, majd mérés B = + 3/16, majd mérés
cos(A – B ) (00 – 11) + sin(A – B ) (01 + 10)
A nyerés valószínűsége: Pr[ab = st] = cos2(/8) = ½ + ¼√2 = 0.853
st = 01 vagy 10
/8 -/8
st = 00
A GHZ játékban alkalmazott kvantum stratégia
Kvantumstratégia a GHZ játékban A felek által elvégzett forgatásokat jelölje α,β illetve γ. A megosztott állapot: |GHZ = (|000+|111)/√2.
α?
A forgatások után kialakul a végleges 3 kvantumbites {0,1}3 GHZ állapot.
β?
γ?
A mérési bázisok jelölése
1 2
1 2
0 0
e
i
e i
1 .
1 ,
Kvantumstratégia a GHZ játékban Hogyan függ a végső kimeneti GHZ állapot alakja az α,β,γ szögek értékeitől? Az α,β,γ szögű forgatások hatása a teljes állapotra: GHZ
1 2
000
e i ( ) 111 .
A három Hadamard-transzformáció utáni rendszerállapot: 1 1 e i ( ) 4 1 1 e i ( ) 4
000
001
011 101 110 010 100 111
Ha α+β+γ = 0 (mod 2π), akkor a kimeneti állapot paritása páros. Ha α+β+γ = π (mod 2π), akkor a három bit paritása páratlan lesz.
Kvantumstratégia a GHZ játékban Ha feltesszük, hogy ezen viselkedést rejtett változók irányítják, akkor minden egyes részecskéhez előre determinált mérési operátor rendelhető: M 0A , M 1A , M 0B , M 1B , M 0C , M C1 2
2
2
Mérési operátorok jelentése: Legyen M B 1. Ekkor, ha B részecskéjét a ½π irány szerint mérjük be, a mérés eredménye 1 lesz. 1 2
A szögek a {0,½π} tartományból vehetnek fel értéket, így α,β,γ{0,½π}. Azonban lehetetlen olyan M értékeket konstruálni, amelyekre a kvantummechanikával egyetértésben teljesülne a következő egyenlőség: MAMBMC = (α+β+γ mod 2π)/π.
Nincsenek rejtett változók Vegyünk 3 esetet, ahol α+β+γ = π, így MAMBMC = 1. M0A MB1 π MC1 π 1 2
2
M A1 π MB0 MC1 π 1 2
2
M A1 π MB1 π MC0 1 2
2
A három egyenletet összeadva (modulo 2): M0A MB0 MC0 1
Ekkor azonban ellentmondásra jutunk az α+β+γ = 0 esetén, mivel ekkor a 3 kimeneti bit paritásának párosnak kellene lenni: M0A MB0 MC0 0
Így, rejtett változókkal nem magyarázható a mérések eredménye.
A GHZ játék MAMBMC = (α+β+γ mod 2π)/π
α?
ahol α,β,γ {0,½π}. Található megoldás?
β?
A kvantummechanikai megközelítésben teljesül az egyenlőség! A szögeket módosítjuk a következőképpen: α,β,γ {0,½π,π,1½π}.
γ?
Kvantummechanikai rendszerekben így elérhető a 100%-os sikervalószínűség. Klasszikus rendszerekben legfeljebb 75%-os siker garantálható.
GZH-játék alkalmazása A három kommunikáló fél legyen Alice, Bob és Carol. A birtokukban lévő x, y és z számokról szeretnék eldönteni, hogy az x+y+z számok összege páros vagy páratlan.
x
y
Az összefonódott kvantumállapotok felhasználásával ezen kérdés két kvantumbit elküldésével megoldható.
z
Klasszikus kommunikáció komplexitása x1x2 xn
y1y2 yn
f (x,y) Egyezőségi vizsgálat: f (x,y) = 1 ha x = y, és 0 ha x y Determinisztikus protokollok kommunikációs igénye: n bit. Valószínűségi protokollok esetén a feladat megoldható O(log(n/)) bit felhasználásával ( hibavalószínűség mellett)
Kvantum kommunikáció bonyolultsága Kvantumkommunikáció, összefonódott állapotok nélkül
Kvantumkommunikáció, összefonódott állapotok megosztásával
x1x2 xn
y1y2 yn
kvantum bitek
f (x,y)
összefonódott állapotok
x1x2 xn
y1y2 yn
klasszikus bitek
f (x,y)
