LOGO
Kvantum-hibajavítás I. Gyöngyösi László BME Villamosmérnöki és Informatikai Kar
Ismétléses kódolás
Klasszikus hibajavítás Klasszikus modell: BSC (binary symmetric channel) • Hibavalószínűség: p • p ≤ 0.5 Kódszavak használata Blokk-kódolás • Kx: x az üzenet kódolásához felhasznált bitek száma • Eredeti üzenet: k bit, felhasznált bitek száma: n • R(K)=k/n
Klasszikus védelem csatornazaj ellen Ismétléses-kód Példa • Hiba: 2 bit sérülése esetén • R(K3)=1/3 • 1 hiba tolerálható • Gyenge hatékonyság, idő+erőforrásigény
K3 : 0
000, 1
111.
000 → 0
111 → 1
001 → 0
110 → 1
010 → 0
101 → 1
100 → 0
011 → 1
Kvantumcsatorna A kvantumállapotok tökéletes meghatározása a gyakorlatban nehezen kivitelezhető Zajos kvantumcsatorna Kvantumkapuk zaja Detektorok, mérőberendezések
Megoldás: kvantum-hibajavító algoritmusok Jelentős elméleti eredmények születtek, de… …továbbra is sok a megoldatlan probléma • Kvantumállapotok és a külvilág kapcsolata • Dekoherencia • Mérések okozta irreverziblis zavarok Számos olyan probléma, amelyekkel klasszikus hibajavító algoritmusok esetén nem találkozhattunk
Kvantum-hibajavítás Eltérések a klasszikus hibajavító algoritmusokhoz képest 1. Kvantumállapotok klónozhatatlansága • Egy adott kvantumállapot pontos lemásolása nem lehetséges.
2. Több hibalehetőség • • • •
Bithiba Fázishiba Bit és fázishiba Dekoherencia
3. A kvantumállapoton végrehajtott mérés hatására a kvantumállapot megsemmisül 4. Diszkrét helyett folytonos hibák
Hibalehetőségek Dekoherencia
(α
0 + β 1 ) ⊗ környezet
α 0 ⊗ környezet A + β 1 ⊗ környezetB .
Kvantumállapotok torzulása U helyett V unitér transzformáció U helyett ρ nem-unitér transzformáció: ρ
† A ρ A ∑ k k. k
Mérési zaj, téves kimeneti eredmények Kvantumrendszerek instabilitása
Kapcsolat a környezettel Problémák rendszer
A külső környezettel kapcsolatba lépve a zárt kvantumrendszer koherens tulajdonságai megsemmisülnek A rendszer további időfejlődése nem adható meg unitér műveletekkel
környezet
A kvantumrendszer és a külső környezet teljes Hilbert-tere:
H = Hrendszer ⊗ Hkörnyezet . A rendszer időfejlődését leíró U unitér operátor: U = e − iHr +k t , ahol H r + k = H r ⊗ Ik + Ir ⊗ H k + Hdekoh . A zárt kvantumrendszeren belüli tiszta kvantumállapot kapcsolatba kerül a külvilággal, a kvantumrendszer kevert állapotba kerül.
ψ0 = ψ
rendszer
⊗ψ
környezet
→ ∑ cn n ⊗ n n
ρ0 = ψ 0
rendszer rendszer
ψ0 .
Hibajelenségek A kvantumállapot lehetséges sérülései Relatív fázisszög hibája:
a 0 +b 1
a 0 −b 1 .
Valószínűségi amplitúdók negálódása:
a 0 +b 1
b 0 +a 1 .
Valószínűségi amplitúdók és relatív fázis hibája:
a 0 +b 1
b 0 −a 1 .
A hibák, az ismeretlen kvantumállapot kódolása után, a hibajavítás szakasz előtt lépnek fel!
Hibajelenségek A hibákat leírhatjuk unitér kvantum transzformációkkal Bithiba (bit-flip): X-transzformáció ⎛ a ⎞ ⎛ b ⎞ ⎛ 0 1 ⎞⎛ a ⎞ ⎛ b ⎞ σx ⎜ ⎟ = ⎜ ⎟ ≡ ⎜ ⎟⎜ b ⎟ = ⎜ a ⎟ . b a 1 0 ⎝ ⎠ ⎝ ⎠ ⎝ ⎠⎝ ⎠ ⎝ ⎠ Fázishiba (phase-flip): Z-transzformáció ⎛a⎞ ⎛ a ⎞ ⎛ 1 0 ⎞⎛a⎞ ⎛ a ⎞ σZ ⎜ ⎟ = ⎜ ⎟ ≡ ⎜ = ⎜ ⎟. ⎟ ⎜ ⎟ ⎝ b ⎠ ⎝ −b ⎠ ⎝ 0 −1⎠ ⎝ b ⎠ ⎝ −b ⎠ Bit és fázishiba: Y-transzformáció (Y=XZ)
⎛a⎞ ⎛ b ⎞ ⎛ −b ⎞ ⎛ 0 −i ⎞⎛ a ⎞ ⎛ −b ⎞ σ Y ⎜ ⎟ = −i ⎜ ⎟ = ⎜ ⎟ ≡ ⎜ = i ⎜ ⎟. ⎟⎜ ⎟ ⎝b⎠ ⎝ a ⎠ ⎝ a ⎠ ⎝ i 0 ⎠⎝ b ⎠ ⎝ a ⎠
A 4 lehetséges leképezés β 0 +α1
α 0 −β1
“Bit hiba”
“Fázis hiba” α 0 +β1
“Identitás”
β 0 −α1
“Bit ÉS fázis hiba” A kvantum-hibajavító kódolás során összesen 3 eltérő tulajdonságú hibajelenséggel kell számolnunk Klasszikus rendszerek esetében csak a bithibák javítása volt a feladatunk
Kvantum ismétléses-kódolás A klasszikus ismétléses-kódolás egyszerűen megfeleltethető klasszikus, nem szuperponált kvantumállapotokkal:
0
000 ,
1
111 .
Szuperpozícióban lévő kvantumállapotok esetén azonban a kvantumállapotok többszörözése nem lehetséges (no-cloning).
Ψ
Ψ Ψ Ψ .
Az ismeretlen kvantumállapotok által realizált leképezés a következő:
(α
0 + β 1 ) ⊗ (α 0 + β 1 ) ⊗ (α 0 + β 1 )
Az ismeretlen kvantumállapotot így egy összefonódott kvantumállapotba transzformáljuk:
Ψ = (α 0 + β 1 )
α 000 + β 111 = Ψ '
= α 000 + 0 001 + 0 010 + 0 011 + 0 100 + 0 101 + 0 011 + β 111 .
Hibajavító kódok tulajdonságai Ha egy kvantum-hibajavító kód képes javítani az A és B hibákat, akkor ezen kóddal az αA + βB jellegű hibák is javíthatóak. Bármilyen 2x2-es mátrix leírható az αI + βX + γY + δZ alakban. A kvantumbit meghibásodása általánosan a ρ → Σ Ak ρ Ak† formában adható meg A hiba a ⎟ψ〉 kvantumállapotot a kevert ψ〉 → Ak⎟ψ〉 állapotba transzformálja, ahol Ak egy a 2x2-es mátrix. A kvantumbiten fellépő X, Y, és Z típusú hibákat javító kvantumkóddal az összes lehetséges egy-kvantumbites hiba javítható. A t darab kvantumbiten fellépő X,Y,Z hibákat javító kvantumkóddal az összes lehetséges t kvantumbites hiba korrigálható. Az I, X, Y, Z Pauli-operátorok tetszőleges M,N párosítása kommutatív, ha MN=NM, illetve anti-kommutatív, ha MN=-NM.
Az elemi CNOT kapu CNOT kapu működése leírható a klasszikus XOR művelet segítségével:
CNOT A, B = A, B ⊕ A A CNOT kapu működési elve: vezérlő kvantumbit
A
A
B
B⊕ A cél kvantumbit
Az elemi CNOT kapu A két bementi kvantumbit: vezérlő és cél kvantumbit
A
A
B
B⊕ A
Ha a vezérlő kvantumbit 0, akkor a célbit változatlan marad : 00 → 00 vagy 01 → 01 . Egyébként a célbit értéke negálódik : 10 → 11 vagy 11 → 10 .
A kimenet : A, B → A, B ⊕ A
Készíthető kvantumbit-másoló kapu? Klasszikus rendszerek esetén egy tetszőleges bit másolása az XOR művelettel megvalósítható:
másolandó bit
0 bemenet
eredeti bit
x
x
x
x
0
y
x⊕ y
x másolt bit
Készíthető kvantumbit-másoló kapu?
másolandó kvantumbit
ψ = a 0 +b 1 Kimenet
a 0 +b 1 a 00 + b 11
a 00 + b 10
0 0 bemenet
Készíthető kvantumbit-másoló kapu?
ψ ψ = a 00 + b 11 = ??? Egy kvantumállapot nem másolható, hiszen
ψ ψ = (a 0 + b 1
)( a 0
ab ≠ 0.
+ b 1 ) = a 2 00 + ab 01 + ab 10 + b 2 11
a 2 00 + ab 01 + ab 10 + b 2 11 ≠ a 00 + b 11 . Vagyis, egy ismeretlen kvantumállapot lemásolása NEM LEHETSÉGES!
- NO CLONING TÉTEL -
Redundáns kódolás Az ismétléses kódolás sem sértheti a klónozhatatlansági-tételt
α⎟0〉 + β⎟1〉 → α⎟000〉 + β⎟111〉 ≠ (α⎟0〉 + β⎟1〉)⊗3 A redundáns kódolás során az ismeretlen kvantumállapot egyes bázisállapotait sokszorosítjuk. A szuperpozíciós állapot kiterjesztésével, redundanciával kódoljuk az állapotot No-cloning tételt nem sértjük
Kvantum ismétléses-kódolás Hogyan valósítható meg a Ψ = (α 0 + β 1 ) α 000 + β 111 = Ψ ' leképezés? A kvantumáramkör bemenetére az ismeretlen Ψ = α 0 + β 1 állapotot adjuk
(
A kvantumhálózat egyes állapotai így a következők lesznek:
)
ψ 1 = α 000 + β 100 . ψ 2 = α 000 + β 101 . ψ 3 = α 000 + β 111 .
Egyszeres bithiba és fázishiba javítás
Kvantum-hibajavítás Valószínűségi amplitúdó felcserélődése (logikai érték negálódása) Megfeleltethető az Ψ ismeretlen kvantumállapoton végrehajtott Xtranszformációnak Tegyük fel, hogy a Ψ = α 000 + β 111 állapot harmadik kvantumbitjének valószínűségi amplitúdói negálódnak. A hibás állapot:
I ⊗ I ⊗ X = α 001 + β 110 . Hogyan detektálható a hiba? A hibás α 001 + β 110 állapot egyes kvantumbitjeihez kiegészítő
kvantumbiteket rendelünk A kiegészítő kvantumbitek segítségével meghatározzuk a bemeneti állapothoz tartozó szindrómavektorok értékét Az eredeti kvantumállapoton nem hajtunk végre mérést
Kvantum-hibajavítás Valószínűségi amplitúdó felcserélődése (bit-hiba javítása) Az áramkör állapotai:
ψ 1 = α 001 + β 110 , ψ 2 = α 00100 + β 11000 , ψ 3 = α 00101 + β 11001 , ψ 4 = α 001 + β 110 ⊗ 0 1 .
Kvantum-hibajavítás Valószínűségi amplitúdó felcserélődése (bit-hiba javítása) Szindróma számítás, hibajavítás: A szindrómát az M1 és M2 mérések segítségével határozzuk meg. A hibajavítást az R hibajavító áramkör végzi. A hibajavításhoz szükséges az M1 és M2 mérések eredményeként előállt szindróma.
Szindróma meghatározása
Kódolt állapot Kiegészítő kvantumbitek
⎟0〉 ⎟0〉
Szindróma
A szindróma első bitje: Az első két kvantumbit azonos vagy eltérő-e?
A szindróma második bitje: a második és harmadik kvantumbit azonos vagy eltérő-e?
Szindróma meghatározása A szindróma segítségével: detektálható a hiba jelenléte pontosan meghatározható a hiba helye.
• Pl.: Az α⎟010〉 + β⎟101〉 állapot szindrómája 11, így a második bit a hibás. Javítás: X-transzformációval, amelyet a 2. kvantumbitre alkalmazunk A kapott szindróma értéke nem függ az α és β valószínűségi amplitúdóktól
A hibát így az eredeti kvantumállapot megsemmisítése nélkül sikerült meghatároznunk és javítanunk!
Bithiba javítása A kapott szindróma és a hibajavítási művelet kapcsolata:
Bithiba javítása A szindróma alapján az áramkör negálja a harmadik kvantumbit értékét:
α 001 + β 110
α 000 + β 111 .
Az áramkör egyetlen kvantumbit helyreállítására képes. A javítás után a Ψ kvantumállapot egyértelműen visszaállítható.
Bithiba javítása kódolás
α 0 +β 1
hiba
dekódolás
javítás
?
0 0 U ⎯⎯ →
hiba
1. Kódolás: (no-cloning kikerülve!)
dekódolás
2. Ortogonális hibák
javítás
3. szindróma
Összefoglalás: Bit-flip javítása (
)
Példa: BSC R(K3)=1/3: Pr [ helyes ] = (1 − p ) + 3 (1 − p ) p = 1 − 3 p 2 − 2 p 3 . A bit-flip hiba megfelel az X unitér kvantum-transzformációnak 3
⎛ 0 1⎞
σX = ⎜ ⎟. 1 0 ⎝ ⎠
2
X⎟0〉 = ⎟1〉, X⎟1〉 = ⎟0〉
A kvantumcsatorna átviteli modellje:
Φ ( ρ ) = (1 − p ) ρ + pσ X ρσ X† .
A teljes bit-flip hibajavító kódolási és javítási folyamat
Relatív fázishiba javítása A kvantumbit fázishibája: a
( −1)
a
a , ahol a ∈ {0,1}.
A hibajelenség a Z unitér kvantum-transzformációval írható le ⎛1
0⎞
. σZ = ⎜ ⎟ ⎝ 0 −1⎠
A bit-flip hiba elleni kódolás nem segít
α 000 + β 111
α 000 − β 111 .
Az előzőekben alkalmazott kódolással tovább növeltük a hiba bekövetkezésének valószínűségét. Megoldás???
Relatív fázishiba javítása A kvantumállapotban bekövetkező sérülés legyen: α 000 + β 111 α 000 − β 111 . Amely állapot dekódolás után: α 0 +β 1 α 0 −β 1 ≡ + − . A hiba javításához változtatunk a kódolást végző kvantumhálózaton: A Hadamard-kapuk implementálásával áttértünk a +/- bázis elemeire:
ψ1 = α + + + + β − − − , ahol + =
1 1 0 + 1 ), − = 0 − 1 ). ( ( 2 2
Relatív fázishiba javítása Tegyük fel, hogy a fázishiba a harmadik kvantumállapoton lép fel:
α +++ +β −−−
α ++− +β −−+ .
A Hadamard-kapuk utáni szindróma számítás eredménye:
ψ 2 = (α 001 + β 110 ) ⊗ 0 0 .
A kapott állapot azonos a valószínűségi amplitúdó sérülése esetén előállt eredménnyel. A bázisok cseréjével a bitnegálódást javító áramkört fázisjavításra, illetve a fázisjavító áramkört bit-negálódás javításra használhatjuk!
Fázishibából bithiba Bázist váltunk:
A fázishibát bithibává konvertáltuk az új bázisban
H
H
H
H
H
H
fázishiba
bithiba
Fázishibából bithiba A Hadamard transzformációval ”válthatunk” bithiba és fázishiba között
H (α 0 + β 1 ) = α + + β − .
Az új bázisban: a fázisfordítást az X-transzformációval,
X + = + , X − =− − .
a bit negálást a Z-transzformációval modellezzük:
Z + = − ,Z − = + .
Relatív fázishiba javítása kódolás
α 0 +β 1
hiba
dekódolás
H
H
0
H
H
0
H
H
javítás
?
U ⎯⎯ →
hiba 1.
Kódolás:
(no-cloning kikerülve!)
dekódolás 2. Ortogonális hibák
javítás 3. szindróma
Szindróma meghatározása
Helyesen kódolt 000 vagy 111 állapotokra: • a csoport első két bitjének paritása páros • a második és harmadik bitből képzett paritás szintén páros.
Ha az első 2 bit közül 1 hibás: • Az első két bitre meghatározott paritás páratlan
Szindróma meghatározása Páros paritás Bithiba javításnál: • A Z⊗Z⊗I sajátértéke +1, az első két bit helyes Fázishiba javításnál: • Az X⊗X⊗I sajátértéke +1, az első két bit helyes
Páratlan paritás: Bithiba javításnál: • A Z⊗Z⊗I sajátértéke -1, a bithiba az első vagy a második kvantumbiten keletkezett Fázishiba javításnál: • Az X⊗X⊗I sajátértéke -1, a fázishiba az első vagy a második kvantumbiten keletkezett
Szindróma meghatározása A Z⊗Z mérésével a bithibák (X) detektálhatóak Az X⊗X mérésével a fázishibák (Z) detektálhatóak. Példa: 1 kvantumbites fázishiba detektálása
Szindróma meghatározása A kiegészítő kvantumbit bemérése után: A kapott eredmény illetve
valószínűséggel
valószínűséggel
A kiegészítő kvantumállapot bemérésével, az eredeti kvantumállapot megsemmisítése nélkül detektálható a hiba A kiegészítő kvantumbit mérési eredménye helyes bitre: +1, hibás bitre: -1.
Szindróma meghatározása Példa: Három kvantumbites ismétléses kód A 3 kvantumbit között van-e hibás, ha igen melyik az? Bithibavizsgálat (X-hiba) paritásellenőrzéssel • első 2 kvantumbitre: Z⊗Z⊗I • 2. és 3. kvantumbitre: I⊗Z⊗Z • A kapott eredmény alapján meghatározható a hiba helye A kiegészítő kvantumbiten (szindrómavektor bitjén) hajtjuk végre a mérést A Z⊗Z mérésével a bithibák (X) detektálhatóak Az X⊗X mérésével a fázishibák (Z) detektálhatóak.
Szindróma meghatározása Az első 3 kvantumbitre végrehajtott Z⊗Z⊗I paritásvizsgálat jellemzői: A kiegészítő kvantumbit kezdeti állapota A kiegészítő kvantumbit egy irányított-Z transzformáció cél kvantumbitje • A vezérlő kvantumbit az első Z transzformáció esetén az 1. kvantumbit • A második Z transzformáció esetén a 2. kvantumbit • A kapu 1 logikai értékű vezérlő-kvantumbitre aktiválódik
Szindróma meghatározása A kapott Z⊗Z⊗I leképezés utáni
rendszerállapoton elvégezzük a szindróma bemérését. A beméréshez a kiegészítő kvantumállapot bázisának megfelelő bázist használjuk. A mérés eredménye a Z⊗Z⊗I transzformáció sajátértéke: +1 vagy 1, a
tag aktuális értékétől függően. Ha a és b bitek értéke különböző, a kimenet értéke -1.
Eredmények felhasználása A hibák által generált alterek ortogonálisak, dimenziójuk azonos.
Az alterek egymástól egyértelműen megkülönböztethetőek A hibák azonosíthatóak a kvantumállapotok bemérése nélkül is
Eredmények felhasználása A Z⊗Z mérésével a bithibák (X) detektálhatóak: A szindrómavektor bitjeit irányított-Z kapuk felhasználásával állítjuk elő
javítás
hiba
Összefoglalás: fázishiba javítása Az új konstrukció megvéd az egyszeres fázisfordulási hibától Azonban a bit-flip hiba ellen nem nyújt védelmet A fázisfordítás unitér transzformációja:
⎛1
0⎞
σZ = ⎜ ⎟. 0 1 − ⎝ ⎠
Z⎟0〉 = ⎟0〉, Z⎟1〉 = -⎟1〉
A teljes fázishiba-javítás kódolási és javítási folyamata:
Kvantum-hibajavítás Bithiba és relatív fázishiba Valószínűségi amplitúdó hiba (bithiba): X-transzformáció Relatív fázishiba: HZH transzformáció
Probléma: Mi történik akkor, ha a két típusú hiba EGYIDEJŰLEG lép fel? Az előzőekben ismertetett hibajavító áramkörök csak egyetlen típusú hiba egyidejű javítására alkalmazhatóak Új konstrukcióra lesz szükségünk
• Shor-féle hibajavító kódolás
LOGO
Köszönöm a figyelmet! Gyöngyösi László BME Villamosmérnöki és Informatikai Kar
