Kvantuminformatikai alapismeretek összefoglalása Gyöngyösi László BME Villamosmérnöki és Informatikai Kar
Támadás kvantumszámítógéppel z z
z
z
Egy klasszikus algoritmusnak egy U unitér transzformáció feleltethető meg. Minden klasszikus algoritmus megvalósítható unitér transzformációval egy kvantumszámítógépben A szuperponált kezdőállapot segítségével pedig párhuzamosan végrehajtható az előírt művelet az összes lehetséges bemenő adatra A műveletvégrehajtás teljes mértékben párhuzamosan történik
A kvantumhálózat működésének elméleti alapjai z
A kvantumszámítások során kihasználható kvantumjelenségek: z Szuperpozíció z Összefonódott
állapotok z Hullámfüggvények interferenciája z Kvantumalgoritmusok z Kvantum-teleportáció z Kvantum-párhuzamosság z Kvantum
keresés
Vezérelhető kvantumkapu z
Bármilyen U kvantumkapu működése vezérelhető Vezérlő kvantumbit
U
n db cél kvantumbit
Ha a vezérlő kvantumbit „magas” szintű, akkor az U transzformáció végrehajtódik. A CNOT ekvivalens egy kontrollált-X kapuval
Kvantum-transzformációk ⎡u00 U =⎢ ⎣ u10
u01 ⎤ ⎥ u11 ⎦
unitér akkor, és csak akkor, ha
⎡u00 † UU = ⎢ ⎣ u10
u01 ⎤ ⎡u 00 ⎢ ⎥ u11 ⎦ ⎢u * ⎣ 01 *
u10 ⎤ ⎡1 0 ⎤ ⎥=⎢ =I ⎥ * u11 ⎥ ⎣0 1 ⎦ ⎦ *
Unitér transzformációk U −1 = U † UU † = U †U = I ⎛1 0⎞⎛1 0⎞ ⎛1 0⎞ II = I = ⎜ ⎟⎜ ⎟=⎜ ⎟ = I. ⎝0 1⎠⎝0 1⎠ ⎝0 1⎠ ⎛0 1⎞⎛0 1⎞ ⎛1 0⎞ XX † = X 2 = ⎜ ⎟⎜ ⎟=⎜ ⎟ = I. ⎝1 0⎠⎝1 0⎠ ⎝0 1⎠ ⎛ 0 −i ⎞ ⎛ 0 − i ⎞ ⎛ 1 0 ⎞ † 2 YY = Y = ⎜ ⎟⎜ ⎟=⎜ ⎟ = I. 0 0 0 1 i i ⎝ ⎠⎝ ⎠ ⎝ ⎠ †
2
⎛1 0 ⎞⎛1 0 ⎞ ⎛1 0⎞ ZZ = Z = ⎜ ⎟⎜ ⎟=⎜ ⎟ = I. ⎝ 0 − 1 ⎠ ⎝ 0 −1 ⎠ ⎝ 0 1 ⎠ †
2
Kvantum-transzformációk ⎛1⎞ 0 →⎜ ⎟ ⎝0⎠ ⎛0⎞ 1 →⎜ ⎟ ⎝1⎠
⎛1⎞ ⎛ 0 ⎞ ⎛α0 ⎞ α 0 0 + α 1 1 → α 0 ⎜ ⎟ + α1 ⎜ ⎟ = ⎜ ⎟ ⎝0⎠ ⎝ 1 ⎠ ⎝ α1 ⎠
Kvantum-transzformációk H ϕ
mátrix alakban:
mátrix alakban:
⎛ ⎜ ⎜ ⎜ ⎜ ⎝
1 2 1 2
1 ⎞ 2 ⎟⎟ −1 ⎟ ⎟ 2⎠
⎛1 0 ⎞ ⎜ iφ ⎟ 0 e ⎝ ⎠
Motiváció z
Megbízhatunk-e a jelenlegi titkosítási technikákban? z z z
z
A napjainkban alkalmazott titkosítási eljárások ereje a gyakorlati feltörhetetlenség biztosításában rejlik Elméletileg azonban feltörhetőek A feltörés sikere a birtokunkban lévő számítási kapacitástól függ
A modern titkosítás alapköve: RSA (1977: Rivest-Shamir-Adleman)
z
A hatékonyabb feltöréshez vezető lehetséges utak: z
Elméleti jellegű áttörés a matematikában z
z
Kevésbé valószínű
Gyakorlati jellegű, technikai áttörés z
Kvantumszámítógépek megjelenésével
Motiváció z z z z
A szilíciumchipek sebessége másfél évente megkétszereződik A Moore-törvény alapján 2017-re egy bit információt egy atomban fogunk kódolni A hagyományos, napjainkban alkalmazott technológiák pár éven belül elérik a végső fizikai határokat Hogyan tovább?
Fejlődési ütem z
Forradalom a számítástechnikában? z z z
z z
Dinamikusan fejlődő tudományterület Folyamatos kutatás a világ számos országában Már elérhető a működőképes kvantumszámítógép
A tudományos publikációk, cikkek száma az elmúlt néhány évben exponenciális sebességgel növekszik Óriási lehetőségek a kvantumjelenségek kihasználásban: z z z z z
Összefonódott állapotok Teleportáció Szupersűrűségű tömörítés Kvantum hibajavítás Kvantumkriptográfia
A kvantuminformatika megjelenése
Kvantuminformatika „Aki a kvantummechanikát tanulmányozza, és nem szédül bele, az nem is érti.” Niels Bohr
z z
z
A kvantumvilágban tapasztalható jelenségek a klasszikus, hétköznapi felfogásunktól nagymértékben különböznek Egy kvantumrendszerben az elvégzendő feladatok szuperpozíciós állapotba hozhatók, azaz egyidejűleg végrehajthatók. A szuperpozíció felhasználásával N db kvantumbittel 2N művelet hajtható végre egyidejűleg!
Kvantumállapotok jellemzése valószínűségi amplitúdóik alapján 1 1 ψ = 0 − 1 2 2
ψ =α 0 +β 1
1 1
α 0 +β 1
0
0
“Normáltsági feltétel”
| α |2 + | β |2 = 1
1 1 0 − 1 2 2
P (0) = P (1) =
1 2
A kvantumbit z
Egy klasszikus bittel ellentétben, a kvantumbit nem csupán a 0 vagy 1 állapot valamelyikében lehet, hanem a két állapot közötti szuperpozícióban is.
z
Kvantumbit megvalósítása z
Pl. hidrogén atommal
Alapállapot:
z
Gerjesztett állapot:
Feles spinű részecskékkel, pl. elektron, proton
Kvantumállapot mérése z
A mérés kvantum-áramkörös jelölése ψ
M (A kimenet egy klasszikus érékű bit lesz) 2
M = 0: α valószínűséggel Ha ψ = α 0 + β 1 akkor: vagy 2 M = 1: β valószínűséggel
EPR állapotok felhasználása EPR jelenség – (Einstein, Podolsky, Rosen) A pár egyik tagja valamilyen egyértelmű kvantumállapotba kerül, akkor a pár másik tagja, a másik részecske kénytelen ezzel ellentétes állapotot elfoglalni. z A szubatomi részecskék között mesterségesen létrehozható z A kapcsolat megmarad bármekkora távolság esetén is
Összefonódott állapotok felhasználása Teleportáció: nem közvetlenül a részecskét teleportáljuk át, hanem egy létező elemi részecske állapotát, azaz tulajdonságait visszük át egy másik, már létező elemi részecskére. A kvantumállapot átviteléhez nincs szükség a két részecske fizikai kapcsolatára, így összefonódott állapotokat használunk.
RSA feltörése: prímfaktorizáció z
Az NFS algoritmussal egy 530 bites szám faktorizációja, 104 PC-vel 1 hónapig tartott Moore törvénye alapján, 2018-ra 104 PC teljesítménye megfelel 100.000 mai PC teljesítményének (1000-szeres növekedés)
z
Mire lesz elég?
z
Klasszikus rendszerek esetén, a faktorizált számok méretében 18 bites növekedés érhető el egy év alatt.
Az NFS algoritmussal elérhető eredmények, klasszikus rendszerekben - 768 bites RSA kulcsot 2010-re, míg egy 1024 bites RSA kulcsot 2018-ra leszünk képesek feltörni a jelenlegi klasszikus architektúrákkal.
Mennyire kell tartanunk a kvantumszámítógépek támadásától? Peter Shor prímfaktorizációs algoritmusa z
Amíg a prímfaktorizáció klasszikus rendszerekben exponenciális, addig kvantumos rendszerekben négyzetes növekményű végrehajtási időt igényel
z
Az RSA feltörése egy 1600 klasszikus számítógépből álló hálózatnak 8 hónapig tartott. Ugyanezen feladat egyetlen kvantumszámítógéppel néhány másodperc alatt végrehajtható.
z
Az alapprobléma: „Egy nő még mindig kiszámíthatóbb, mint az elektron.”
Peter Shor
Mérő László szló
z
Az első kereskedelmi forgalomban is kapható kvantumszámítógép bemutatása z
D-Wave, 2007. február 13.
Mérő László
Kvantuminformatika Egyéb eredmények: Adatbázis szűrés z
Lov Grover kvantumalgoritmusa
z
Az 56 bites DES feltörése kvantumszámítógéppel 185 lépésből végrehajtható (másodperc töredéke) z Mai klasszikus rendszerű szuperszámítógépnek 1 év
z
Adott egy adatbázis USA lakosságával: 270 000 000 adat z z
Egyetlen elem megtalálásához klasszikus rendszerben átlagosan 270 000 000/2 = 135 millió lépés szükséges A kvantumos változat esetében kb. 16 ezer lépésből megtalálható a keresett elem
Kvantum operátorok Egy kvantumrendszeren belül, minden kvantum-transzformáció reverzibilis z A klasszikus Boole-algebra felett értelmezett operátorok esetén ez nem követelmény z Egy reverzibilis művelet mindig megadható egy unitér mátrix formájában: z
(U )* = U T
−1
Lényegesebb alap kvantum-kapuk z
A klasszikus rendszerkehez hasonlóan, a logikai műveletek végrehajtásához különböző kvantum kapukat definiálhatunk
α 0 +β 1
X
β 0 +α 1
α 0 +β 1
Z
α 0 −β 1
α 0 +β 1
H
α
0 +1 2
+β
1 −1 2
Kvantum CNOT kapu z
Klasszikus rendszerek esetén a NAND kapu az ún. univerzális kapu z
A NAND kapuk segítségével tetszőleges áramkör felépíthető
NOT kapu NAND-ból
z
ÉS kapu NAND-ból
VAGY kapu NAND-ból
Létezik kvantum rendszerekben UNIVERZÁLIS kvantum kapu?? z
z
Vagyis, bármilyen tetszőleges, n kvantumbiten elvégezhető logikai művelet felépíthető véges számú elemi kvantumkapuból ?
Igen, kvantumrendszerek esetében is létezik univerzális kapu, azonban ezen kapu működése klasszikus rendszerkben nem értelmezhető.
Az univerzális kvantum kapu z
Controlled-NOT (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
Az elemi CNOT kapu z
CNOT kapu működése leírható a klasszikus XOR művelet segítségével: CNOT A, B = A, B ⊕ A
z
A CNOT kapu működési elve: vezérlő kvantumbit
A
A
B
B⊕ A cél kvantumbit
Lényegesebb alap kvantum-kapuk z
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
Lényegesebb alap kvantum-kapuk z
Készíthető kvantumbit-másoló kapu? z Hogyan alakul a helyzet egy kvantumrendszeren belül?
másolandó kvantumbit
ψ = a 0 +b 1 Kimenet
a 0 +b 1 a 00 + b 11
a 00 + b 10
0 0 bemenet
Kvantumállapot másolhatatlansága z
Készíthető kvantumbit-másoló kapu? Vajon
?
ψ ψ = a 00 + b 11
ψ ψ = (a 0 + b 1
)( a 0
+ b 1 ) = a 2 00 + ab 01 + ab 10 + b 2 11
Azaz, egy kvantumállapot nem másolható, hiszen
ab ≠ 0.
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 -
Kvantumkriptográfia z
A fotonok polarizációs állapotainak összefoglalása z
Ortogonális bázisvektorok
z
Szuperpozíciós állapot leírása valószínűségi amplitúdókkal
z
Az állapothoz tartozó valószínűségi amplitúdók, valamint a használt bázis orientációja meghatározzák a mérési eredmények kimenetelét.
A kvantumkriptográfia működési elve
Kvantumkriptográfia z
z z
A kvantumkriptográfiában a biteket a fotonok
polarizációs szögével reprezentáljuk
Az egyeseket és nullákat rektilineáris és diagonális bázisokkal kódoljuk A téves bázisú mérések irreverzibilis változást okozhatnak a kvantumrendszerben
Kvantumkriptográfia z
A rektilineáris és diagonális szűrőkkel előállítható fotonok, és azok bináris értékei
Kvantumkriptográfia z
A fotonok értékeinek dekódolására kétféle bázist választhatunk z
A vevő rektilineáris polárszűrővel tökéletesen azonosítja a függőlegesen és vízszintesen polarizált fotonokat, az átlósakat azonban nem, mivel azokat véletlenszerűen függőlegesnek vagy vízszintesnek méri
Kvantumkriptográfia z
Ha a vevő diagonális szűrőt alkalmaz, akkor az átlósan polarizált fotonokat tökéletesen felismeri, de a vízszintesen és függőleges fotonokat helytelenül átlós polarizáltságúaknak azonosítja. A kapott bit értéke így véletlenszerű lesz.
Kvantumkriptográfia alkalmazása zA
kommunikáció résztvevői Alice
Eve
Kvantumcsatorna
Bank
Publikus csatorna
Kvantumkriptográfia alkalmazása
z z z
A kvantumcsatorna egyirányú, Alice-től a Bank felé A kvantumcsatornát, így az ott folyó kommunikációt a kvantummechanika alaptörvényei védik A kvantumcsatornán történik a titkos kulcs kialakítása z
z
Szimmetrikus, OTP kulcs
A publikus csatorna kétirányú z
A detektorok egyeztetésére használjuk
Kvantumkriptográfia alkalmazása z z
A kommunikáció során Alice és a Bank a kvantumcsatornán keresztül hozza létre a titkos kulcsot A használt bázisokat és a kulcs elemeit a publikus csatornán keresztül egyeztetik
Kvantumkriptográfia alkalmazása A protokoll támadása
Kvantumkriptográfia alkalmazása Eve megjelenése a protokollban Mi teszi lehetetlenné a lehallgató dolgát? z z z z z z
Eve egy fotont csak egyszer mérhet be Nincs információja a bemérendő foton bázisáról Az elfogott fotonok felét tudja csak helyesen bemérni A detektoregyeztetés során a felek téves detektorválasztásaihoz tartozó bitek kikerülnek a kulcsból Ez az információ a lehallgatón nem segít, mivel a Bank által helyesen bemért fotonok felét szintén tévesen határozta meg A téves bázisú lehallgatás irreverzibilis változásokat okoz a rendszerben!!
Kvantumkriptográfia z
Animáció: A protokoll működésének bemutatása
Kvantumkriptográfia z
Összefoglalás z z z z z z
Jelenleg nem kínál előnyöket, mert az RSA révén rendelkezésünkre áll a gyakorlatilag feltörhetetlen kód A kvantumszámítógépek megjelenéséig még biztonságban vagyunk A kvantumkriptográfia nem csupán gyakorlatilag feltörhetetlen kód, hanem abszolút értelemben is az. A kvantumelmélet lehetetlenné teszi, hogy Eve helyesen értelmezze az Alice és Bob között kialakult kulcsot A lehallgatási próbálkozásokat pedig Alice és Bob azonnal észreveszi Kijelenthető, hogy ha egy kvantumkriptográfiával titkosított üzenetet valaha is megfejtenének, akkor hibás a kvantumelmélet, ami az egész fizikát alapjaiban döntené össze
Kvantumkriptográfia z
Az első kvantumkriptográfiára épülő banki tranzakció z z
2005: Ausztria, Bécs A megvalósításhoz szükséges eszközök már elérhetőek a piacon z z
z
Quantique, Magiq A technológia jelenleg még drága,a potenciális vásárlói kör is meglehetősen szűkre szabott Elsődleges célcsoport jelenleg: z
Kutatóintézetek, kormányzati hivatalok, bankok, üzleti élet, nemzetbiztonság, katonaság
Valódi véletlenszámgenerátor Kvantum-véletlenszámgenerátor z z z z z
Foton alapú véletlenszám előállítás 3 féle implementáció z PCI, USB, OEM-chip Valódi véletlenszámok előállítása z 4/16 Mbps-es sebességgel Alacsony költségek Széleskörű felhasználási lehetőség z Kvantumkriptográfia z PIN generálás z Statisztikai kutatások z Numerikus módszerek alkalmazása z Szerencsejátékok, stb…
Kvantumbitek ábrázolása
Kvantuminformáció ábrázolása z
A kvantumbit z
A kvantumbit állapotának leírására a Dirac-féle braket szimbólumot használjuk z z
Ket: oszlopvektor Bra: sorvektor, ket adjungáltja z
z
Azaz a sorvektor az oszlopvektor komplex konjugált elemeinek transzponáltja
A szuperpozíciós állapot szemléltetésére pedig a Bloch-gömböt
Kvantuminformáció ábrázolása ψ = α 0 + β 1 = rα e eiθ = cos θ + i sin θ z = a + bi = r (cos θ + i sin θ ) ⇒ z = reiθ .
2
2
α + β =1 ψ ψ =1 A kvantumbiteken végrehajtható U unitér transzformációk megadhatóak elemi forgatási transzformációkkal.
iφα
0 + rβ e
iφβ
1
Kvantuminformáció ábrázolása Az I-transzformáció az ún. identitás transzformáció, amely transzformáció esetén a kimeneti kvantumállapot megegyezik a bementi kvantumállapottal. Az I-transzformáció tehát a következőképpen írható le:
⎛1 0⎞⎟ ⎛a ⎟⎞ ⎛a ⎟⎞ ⎛1 0⎞⎟ ⎜ ⎟⎟ ⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ , így φ = a ⋅ 0 + b ⋅ 1 . ⎟⎟ ekkor ⎜⎜ σI = I = ⎜ ⎜⎝0 1⎠⎟ ⎜⎝b ⎟⎠ ⎜⎝b ⎟⎠ ⎜⎝0 1⎠⎟ Az X-transzformáció egy kvantumbit állapotát negálja. A φ = σ X ⋅ ψ kimeneti állapotot így a következőképpen írhatjuk le:
⎛0 1⎞⎟ ⎛0 1⎞⎟ ⎛a ⎞⎟ ⎛b ⎞⎟ ⎜ ⎟⎟ ekkor ⎜⎜ ⎟⎟ ⎜⎜ ⎟⎟ = ⎜⎜ ⎟⎟ , σX = X = ⎜ ⎜⎝1 0⎠⎟ ⎜⎝1 0⎠⎟ ⎜⎝b ⎠⎟ ⎜⎝a ⎠⎟
φ = a ⋅ 1 +b ⋅ 0 .
Kvantuminformáció ábrázolása Az Y-transzformáció a negáló és komplex-fázisfordító transzformáció, amelyet a következőképpen adhatunk meg:
⎛ 0 − j ⎟⎞ ⎛a ⎞⎟ ⎛ 0 − j ⎞⎟ ⎛−b ⎟⎞ ⎜ ⎜ ⎜ ⎜ ⎟⎟ ⎜ ⎟⎟ = j ⋅ ⎜ ⎟⎟ , ⎟⎟ ekkor ⎜ σY = Y = ⎜ ⎜ ⎜⎝ j ⎜⎝ a ⎠⎟ ⎟ 0⎠ 0⎟⎠ ⎜⎝b ⎠⎟ ⎝j
így φ = j ⋅ a ⋅ 1 − j ⋅ b 0 . A kiindulási állapotot kék színnel, a transzformált φ = j ⋅ a ⋅ 1 − j ⋅ b 0 kimeneti kvantumállapotot pedig zöld színnel jelöltem.
Kvantuminformáció ábrázolása A Z-transzformáció transzformációval előállítható
a fázisfordító kimeneti φ
transzformáció. kvantumállapot
következőképpen határozható meg:
⎛1 ⎛1 0⎞⎟ 0⎞⎟ ⎛⎜a ⎞⎟ ⎛⎜ a ⎟⎞ ⎜ ⎜ ⎟ ekkor ⎜ ⎟ ⎟= ⎟, σZ = Z = ⎜ ⎜⎝0 −1⎟⎟⎠ ⎜⎝0 −1⎠⎟⎟ ⎜⎜⎝b ⎠⎟⎟ ⎜⎜⎝−b ⎟⎟⎠
φ = a ⋅ 0 −b ⋅ 1 . A kék színnel jelölt ψ = a ⋅ 0 + b ⋅ 1 kiindulási kvantumállapoton végrehajtott σZ transzformáció eredményét
A a
Kvantuminformáció ábrázolása A Hadamard-transzformáció képes arra, hogy egy bázisállapotban lévő kvantumbitet szuperponált állapotba vigyen. Ennek értelmében, ha egy n-bites kvantumregiszter minden kvantumbitjére Hadamard-transzformációt alkalmazunk, a kvantumregiszterben 0-tól 2n-1 -ig az összes szám szuperpozíciós állapotát kezelhetjük párhuzamosan.
1⎞⎟ ⎛⎜a ⎞⎟ 1 ⎛⎜a + b ⎞⎟ 1 ⎛⎜1 ⎟⎟ ⎜ ⎟⎟ = ⎟⎟ , σH = H = ⋅⎜ ⎜ ⎜ ⎜ ⎜ 2 ⎝1 −1⎠⎟ ⎝b ⎠⎟ 2 ⎝a − b ⎟⎠ így 1 1 φ = ( 0 + 1 )⋅ a + ( 0 − 1 )⋅ b . 2 2 Amíg tehát egy klasszikus regiszter csak egy konkrét számot kezel egyidejűleg, addig egy kvantumregiszteren elvégzett művelet egyszerre kerül végrehajtásra az összes, 2n értéken.
0 →ψ =
1 (0 +1 2
)
Kvantuminformáció ábrázolása
Több kvantumbites rendszer Két kvantumbites kvantumrendszer leírása:
(α
0
0 + α1 1 ) ⊗ ( β 0 0 + β1 1
)
Lehetséges bázisállapotok:
0 0 = 00
0 1 = 01
1 0 = 10
1 1 = 11
A bázisállapotokhoz tartozó valószínűségi amplitúdókkal:
α 0 β 0 00 + α 0 β1 01 + α1β 0 10 + α1β1 11 vektor alakban:
⎛ α 0β 0 ⎞ ⎜ ⎟ ⎜ α 0β1⎟ ⎛ α 0 ⎞ ⎛ β0 ⎞ ⎜ α β ⎟ = ⎜⎜ α ⎟⎟ ⊗ ⎜⎜ β ⎟⎟ ⎜ 1 0⎟ ⎝ 1⎠ ⎝ 1⎠ ⎜αβ ⎟ ⎝ 1 1⎠
Több kvantumbites rendszer A két kvantumbites
α 00 0 0 + α 01 0 1 + α10 1 0 + α11 1 1 kvantumrendszer bemérésekor a
x y kimenet valószínűsége:
α xy
2
Több kvantumbites rendszer A szuperponált két kvantumbites
α 00 0 0 + α 01 0 1 + α10 1 0 + α11 1 1 kvantumrendszer valószínűségi amplitúdói: 2
2
2
2
α 00 + α 01 + α10 + α11 = 1 Azonban nem minden két kvantumbites rendszer adható meg tenzor-szorzat alakban. A felbonthatatlan kvantumállapotok az összefonódott kvantumállapotok.
EPR állapotok Nem összefonódott két kvantumbites állapot:
ξ =
1 ( 00 + 01 2
)
⎛1⎞ ⎜ ⎟ 1 ⎜1⎟ Vektor formában: ξ = 2 ⎜0⎟ ⎜ ⎟ ⎝0⎠ ⎛1 ⎜ 1 ⎜1 Sűrűségmátrix formájában: ρξ = ξ ξ = 2 ⎜0 ⎜ ⎝0
1 0 0⎞ ⎟ 1 0 0⎟ . 0 0 0⎟ ⎟ 0 0 0⎠
Az állapot felbotható részrendszerek tenzorszorzatára:
1 ⎛ ⎛ 1 0 ⎞ ⎛ 1 1⎞ ⎞ ρξ = ⎜ ⎜ ⎟⊗⎜ ⎟⎟ 2 ⎝ ⎝ 0 0 ⎠ ⎝ 1 1⎠ ⎠
EPR állapotok Összefonódott állapot : 1 ( 00 + 11 ) 2 ⎛1 0 0 1⎞ ⎜ ⎟ 0 0 0 0 1 ⎟, Sűrűségmátrix : ρ Ψ + = Ψ + Ψ + = ⎜ 2 ⎜0 0 0 0⎟ ⎜ ⎟ ⎝1 0 0 1⎠ Az összefonódott állapotok nem bonthatóak fel részrendszerek tenzorszorzatára! Ψ+ =
Összefonódott állapotok létrehozása Az összefonódott állapotok létrehozásához mindösszesen egy Hadamard kapura, illetve egy CNOT kapura lesz szükségünk:
x
y
H
x
y
Kimenet
0
0
1 ( 00 + 11 ) 2
0
1
1 ( 01 + 10 2
0
1 ( 00 − 11 ) 2
1
1 ( 01 − 10 2
1 1
)
)
Az áramkör működése 0 0
H
1 (0 + 1 ) 2
? ⎛ 0 +1 ⎞ ⎛ 00 + 10 ⎞ ⎟ CNOT⎜⎜ ⋅ 0 ⎟⎟ = CNOT⎜⎜ ⎟ 2 2 ⎝ ⎠ ⎝ ⎠ 1 (CNOT 00 + CNOT 10 = 2 1 ( 00 + 11 ) = 2
)
EPR állapotok felhasználása z
z
A kvantumszámítógépek közti adatátvitelhez ne legyen szükség közvetlen fizikai kontaktusra az egyes kvantumbitek között A kvantumbitek fizikai realizációja legyen a lehető legegyszerűbb z z
z
Foton alapú kommunikáció helyett lézernyaláb, vagy mikrohullám Az összefonódott állapotban lévő kvantumbitek egy kvantum-buszon keresztül kommunikálnak egymással A kvantum-busz fizikai megvalósítása lehet: z
lézer vagy mikrohullám
Kvantum-transzformációk Unitér transzformációk A kvantumkapuk és a felépített kvantumáramkörök reverzibilisek (nincs információveszteség) z
Kimeneti szálak száma = Bemeneti szálak száma
z
A kimenet a bemeneti vektorok permutációja
z
Klasszikus logikai szabályrendszerek leírhatók
z
Kvantumjelenségek: kvantumállapotok fázisa, összefonódottság
Kvantum-transzformációk z
Átvitel-bemenet nélküli összeadás megvalósítása Alapprobléma: A klasszikus sum = x1 ⊕ x0 és carry = x1x0 függvények implementálása |x1〉 |x0〉 |y1〉 |y0〉
Uadd
|x1〉 |x0〉 |y1〉 ⊕ carry |y0〉 ⊕ sum
Kvantum-transzformációk z
A félösszeadó unitér mátrixa:
UADD
⎛1 ⎜0 ⎜0 ⎜0 ⎜ 0 ⎜ 0 ⎜ ⎜0 ⎜0 = ⎜0 ⎜0 ⎜0 ⎜0 ⎜ 0 ⎜ 0 ⎜ ⎜0 ⎝0
0 0
0 0 0 0 0 0 0 0 0 0
0 0 0⎞
1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
0 0 0 0
0 0 0⎟ 0 0 0⎟ 0 0 0⎟ 0 0 0⎟ ⎟ 0 0 0 ⎟ 0 0 0 ⎟ 0 0 0⎟ 0 0 0⎟ 0 0 0⎟ 0 0 0⎟ 0 0 0⎟ 0 1 0⎟ ⎟ 0 0 1 ⎟ 0 0 0 ⎟ 0 0 0⎠
0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0
0 0 0 0 0 0 0 0 0 1
Kvantum-transzformációk z
Half Adder: egyszerűsített implementáció |x1〉 |x0〉 |y〉
C2NOT (Toffoli)
CNOT
|x1〉 sum |y〉 ⊕ carry
Kvantum-transzformációk cn–1 a0
s0
b0
Klasszikus összeadó
s1
a1 b1
s2
a2 b2
s3
a3
Sum
b3
cn
Carry
Kvantum-transzformációk Kvantumösszeadó
• σx : Pauli-féle X
transzformáció, NOT művelet
• Irányított-σx: controlled-NOT, CNOT kapu Controlled-controlled σx = Toffoli-kapu
Controlled σx = C-NOT kapu
Elemi kvantumáramkörök
i⎧ ⎨… ⎩
Klasszikus logikai függvény
n bemenet
… f(i) m kimenet
i⎧ ⎨…
⎩ ⎧ ⎨ ⎩
“kiegészítő kvantumbitek”
…
Reverzibilis kvantum függvény
… …
⎧ ⎨ ⎩
z
⎧ ⎨ ⎩
z
Reverzibilis áramkörök: ötlet megszületése a ’80-as években (Feynman), cél: energiaveszteség minimalizálása Bennett, Toffoli: bármilyen klasszikus logikai transzformáció megvalósítható reverzibilis műveletekkel Annyi bemenő bit értékét kell a kimeneten megőrizni, amelyből egyértelműen eldönthető a bemenő bitek értéke.
⎧ ⎨ ⎩
z
“irreleváns állapotok”
f(i)
Elemi kvantumáramkörök z
Hogyan állítható elő a klasszikus f függvény kvantumos változata? z A függvény legyen f :i → f(i), n bemenettel és m kimenettel z Kvantum-kimenet reverzibilis: a klasszikus megvalósításhoz képest n bit extra kimenet + m bit extra bemenet szükséges z A klasszikus f függvény kvantumos változata így: frev: i, j → i, f(i) ⊕ j ahol ⊕ az XOR művelet
z
Valósítsuk meg az ÉS függvény kvantumos változatát: f(a,b) = AND(a,b) a b c a b f
a b c
Reverzibilis ÉS kapu
a b f = ab ⊕ c
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 1 0
Elemi kvantumáramkörök z
A kapott kvantum-transzformációt a Toffoli kapuval realizálhatjuk z z
AND művelet: c = 0, esetén NAND művelet: ha c = 1. a b c a b f
a b c
Reverzibilis ÉS kapu
a b f = ab ⊕ c
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
0 0 0 0 1 1 1 1
0 0 1 1 0 0 1 1
0 1 0 1 0 1 1 0
Elemi kvantumáramkörök z
Reverzibilis kvantum kapuk:
z z
Minden klasszikus logikai függvény leírható univerzális kvantum műveletekkel Nem létezik három bemenetűnél kisebb univerzális reverzibilis kvantumkapu
Elemi kvantumkapuk ismertetése
Elemi kvantumáramkörök NOT z z z z
Bemeneti állapot: c0|0〉 + c1|1〉 NOT Kimeneti állapot: c1|0〉 + c0|1〉 A NOT leképezés: |0〉 → |1〉 és |1〉 → |0〉 A transzformáció mátrixa:
⎛⎜ 0 1⎞ ⎝ 1 0⎠ z
(NOT)(NOT)=Identitás transzformáció
⎜⎛ 0 1⎞ ⎜⎛ 0 1⎞ = ⎜⎛ 1 0⎞ ⎝ 1 0⎠ ⎝ 1 0⎠ ⎝ 0 1⎠
NOT
NOT
Elemi kvantumáramkörök z
“GyökNOT” z z
Imaginárius elemek A transzformáció mátrixa:
⎛ i / 1/ 2 1/ 1/ 2 ⎞ 1 ⎛ i 1⎞ ⎜ ⎟= ⎜ ⎟ ⎜1/ 1/ 2 i / 1/ 2 ⎟ 1 i 2⎝ ⎠ ⎝ ⎠ z Így a kimenetelek valószínűsége: |0〉 → |0〉 : |i/√2|2 = ½ és |0〉 → |1〉 : |1/ √ 2|2 = ½. z
A véletlenszerű viselkedés eliminálható: (NOT lesz) 1 ⎜⎛ i 1⎞ ⎜⎛ i 1⎞ ⎜⎛ 0 i ⎞ = 2 ⎝ 1 i ⎠ ⎝1 i ⎠ ⎝ i 0⎠
NOT
NOT
Elemi kvantumáramkörök z
Komplex elemek helyett csak valós értékekkel számolunk:
⎛ 1 ⎛ i 1⎞ 1 ⎛ 1 −1 ⎞ ⎜ ⎜ ⎟→ ⎜ ⎟=⎜ 2 ⎝1 i ⎠ 2 ⎝1 1 ⎠ ⎜ ⎜ ⎝
z
Funkcionalitása azonos: z Véletlenszerű kimenet z Konkatenációja NOT transzformáció
⎛ ⎜ ⎜ ⎜ ⎜ ⎝
1 2 1 2
1 ⎞⎛ − 2 ⎟⎜ ⎟⎜ 1 ⎟⎜ ⎟⎜ 2 ⎠⎝
1 2 1 2
1 2 1 2
−
1 ⎞ 2 ⎟⎟ . 1 ⎟ ⎟ 2 ⎠
1 ⎞ − 2 ⎟⎟ ⎛ 0 −1⎞ =⎜ ⎟. 1 ⎟ ⎝1 0 ⎠ ⎟ 2 ⎠
Elemi kvantumáramkörök Hadamard 1 2
⎛⎜1 1 ⎞ ⎝1 −1⎠
H
|0〉 → 1/ √ 2 |0〉 + 1/ √ 2 |1〉 és |1〉 → 1/ √ 2 |0〉 – 1/ √ 2 |1〉. z Az 1/ √ 2 normalizálást elhagyva: z
|x〉 → (-1)x |x〉 – |1 – x〉
Fázisfordítás ⎜⎛ 1 0 ⎞ ⎝ 0 e iφ ⎠
φ
Univerzális kvantum-transzformációk z
Követelmény: |0〉
z
z
U
tetszőleges |ψ〉 állapot
A Hadamard és fázisfordító kapukból felépíthető minden 1-kvantumbites, univerzális művelet Példa: Az áramkör kimenete: |ψ〉 = cos θ |0〉 + eiφ sin θ |1〉
H
2θ
H
π 2
+φ
Elemi kvantumáramkörök z
Controlled NOT (CNOT) kapu |x〉 |y〉
CNOT
|x〉 |x ⊕ y〉
⎛1 ⎜0 ⎜0 ⎜ ⎝0
0 0 0⎞ 1 0 0⎟ 0 0 1⎟ ⎟ 0 1 0⎠
|x〉
|x〉
|y〉
|x ⊕ y〉
z
CNOT leképezés: |x〉|0〉 → |x〉||x〉 ⎡σ |x〉|1〉 → |x〉||NOT x〉
z
|x〉|0〉 → |x〉||x〉 NEM KLÓNOZÁS!!! z
Csak és kizárólag ismert, |0〉 és |1〉 bázisállapotokra érvényes!
Az elemi kvantumáramkörök felépítése z
Univerzális, reverzibilis kapu z A végrehajtás során nem veszítünk információt
z
A Toffoli kapu a z értékét akkor módosítja, ha x és y is 1 :
T ( x, y, z ) = z ⊕ xy.
Elemi kvantumáramkörök z
Controlled CNOT (C2NOT vagy Toffoli kapu) ⎛1 ⎜0 ⎜0 ⎜0 ⎜ 0 ⎜ 0 ⎜ ⎜0 ⎝0
0 0 0 0 0 0 0⎞ 1 0 0 0 0 0 0⎟ 0 1 0 0 0 0 0⎟ 0 0 1 0 0 0 0⎟ 0 0 0 1 0 0 0⎟ ⎟ 0 0 0 0 1 0 0 ⎟ 0 0 0 0 0 0 1 ⎟ 0 0 0 0 0 1 0⎠
|a〉
|a〉
|b〉
|b〉
|c〉
|ab ⊕ c〉
Elemi kvantumáramkörök z
Irányított U unitér transzformációk: ⎜⎛ u00 ⎝ u10
u01⎞ u11 ⎠
U
U
U
U
C(U)
C2(U)
Elemi kvantumáramkörök z
Bármilyen C2(U) kapu felépíthető CNOT, illetve C(V) és C(V†) kapukból, ahol V2 = U
= U
1/2
V
V†
V
(1+i) (1-i) (1-i) (1+i)
1/2
(1-i) (1+i) (1+i) (1-i)
Elemi kvantumáramkörök Az áramkör működése 0 kontrollbit esetén |0〉
|0〉
|1〉
|1〉
|x〉
|x〉
U
?
=
|0〉
|0〉
|0〉
|0〉
|0〉
|0〉
|1〉
|1〉
|1〉
|1〉
|1〉
|1〉
|x〉
V|x〉
V
V
†
|x〉
V
|x〉
Az áramkör működése aktív kontroll esetén |1〉
|1〉
|1〉
|1〉
|x〉
U|x〉
U
?
=
|1〉
|1〉
|1〉
|1〉
|1〉
|1〉
|1〉
|1〉
|0〉
|0〉
|1〉
|1〉
|x〉
V|x〉
V
V
†
V|x〉
V
U|x〉
Kvantum párhuzamosság alkalmazása
Kvantum párhuzamosság z
Bármilyen bináris f függvényre, ahol
z
létrehozható olyan Uf unitér kvantumáramkör, amellyel elvégezhető az f függvény által meghatározott művelet Azaz, minden klasszikus rendszerű f művelet egyértelműen megfeleltethető egy kvantumtranszformációnak:
f : {0,1} 6 {0,1} ,
U f : x, y 6 x, y ⊕ f ( x ) bináris összeadás
Kvantum párhuzamosság z
Mire képes a megkonstruált Uf kvantumáramkörünk? A kvantumáramkör kimenete:
0
x
1
y
x
Uf y⊕f(x)
ψ =U f ( 0 ⊗ 1
)
= U f 01 = 0, 1 ⊕ f (0)
Kvantum párhuzamosság z
Mi történik, ha a bemenetre szuperpozíciós állapotot adunk? 1 (0 + 1 ) 2
1
x
x
Uf y
y⊕f(x)
Kvantum párhuzamosság!!! Az f(0) és az f(1) értékét egyetlen bemeneti bittel meghatároztuk.
⎛ 0 +1
⎞ ⋅0 ⎟ 2 ⎝ ⎠ ⎛ 00 + 10 ⎞ =U f ⎜ ⎟ 2 ⎝ ⎠ 0, 0 ⊕ f (0) + 1, 0 ⊕ f (1) = 2 0, f (0) + 1, f (1) = 2
ψ =U f ⎜
Kvantum párhuzamosság z
Egyetlen lépésben meghatározhatjuk a következő művelet értékét:
f (0) ⊕ f (1) z
Egy klasszikus rendszerben ehhez a következő lépéseket kellene végrehajtanunk: 1. Az f(0) értékének kiszámítása 2. Az f(1) értékének kiszámítása 3. A két eredmény bináris összeadása Ahol az f továbbra is: f : {0,1} 6 {0,1}
Kvantum párhuzamosság 0
H
x
1
H
y
ψ 0 = 01
H
x
Uf
ψ1 =
y⊕f(x)
0 +1 2
⋅
0 −1 2
Kvantum párhuzamosság 0
H
x
1
H
y
ψ2
⎧ ⎪ha f (0) = f (1), ⎪ =⎨ ⎪ha f (0) ≠ f (1), ⎪⎩
H
x
Uf
± ±
y⊕f(x)
0 +1 2 0 −1 2
⋅ ⋅
0 −1 2 0 −1 2
Kvantum párhuzamosság 0
H
x
1
H
y
x
Uf
H
y⊕f(x)
A kapott eredmény átírása után:
ψ 3 = ± f (0) ⊕ f (1) ⋅
0 −1 2
Azaz, megkaptuk a keresett műveleti értéket:
f (0) ⊕ f (1)
Az f kiegyensúlyozott vagy konstans? Egyetlen lekérdezéssel megválaszoltuk.
Kvantum keresés implementálása
Kvantum keresés z z
A kvantum-keresési algoritmus szemléltetése: általában az adatbázis-keresésen keresztül Szemléletesebb példa: gráfszínezés
Gráfszínezési probléma megoldása kvantum-kereséssel 1
Feladat: közös éllel rendelkező csomópontok kiszínezése eltérő színnel
1 3
2 5 4
Cél: kiszínezés végrehajtása minimális számú színnel
3
2 5 4 6
6
7
7 A gráf 3-színnel kiszínezhető
1
Gráf színezés kvantum-algoritmussal 3
2
Az összes lehetséges színkombináció
4 1. csomópont lehetséges színei 2. csomópont lehetséges színei 3. csomópont lehetséges színei
4. csomópont lehetséges színei
≠ “1” kimenet: akkor és csak akkor, ha a csp. 1 és csp. 2 színe eltérő
≠ 1≠2
≠ 1≠3
≠ 2≠3
≠
2≠4
3≠4
F(x) ÉS művelet: 1 kimenet csak a keresett színezés esetén
Az összes lehetséges kombináció előállítására a Hadamard transzformációt alkalmazzuk
Az összes lehetséges színkombináció |0> |0> |0>
H H
H H H
≠
≠ 1≠2
≠ 1≠3
≠ 2≠3
2≠4
≠ 3≠4
f(x) A Hadamard transzformációval a kvantumállapotok szuperponált állapotba kerültek Az összes lehetséges bemeneti kombinációt egyidejűleg vizsgálhatjuk!
ÉS művelet: 1 kimenet csak a keresett színezés esetén
Gráf színezés kvantum-kereséssel
|0>
2
−1) ( n
f ( x)
orákulum
1
(x 1)
Az orákulum egy Karnaugh táblának feleltethető meg Minden helyes mintermre (1) -1 kimenettel
|1>
f(x)
Rossz mintermek (0) kódolása: 1
A Hadamard transzformációkkal előállított szuperponált állapotokkal az összes lehetséges helyes mintermet párhuzamosan határozhatjuk meg
Kvantum-keresés: Belső f függvény meghatározása 1 lépésben
A lehetséges belső f függvények
A kvantum kereséssel egyetlen lekérdezésből megállapíthatjuk a belső orákulum függvény típusát.
Az orákulum tulajdonságai Az f : {0,1}2 Æ {0,1} belső függvény kimenete csak egyetlen x ∈ {0,1}2 bementre 1: f (x) = 1 Cél: azon x ∈ {0,1}2 bemenet megtalálása, amelyre
f (x) = 1 A négy lehetséges belső függvénytípust egyetlen lekérdezésből megállapíthatjuk!
Kvantum keresés A belső f függvény leképezése: |x1〉 |x1〉 f |x2〉 |x2〉 |y〉 |y ⊕ f(x1,x2)〉 Előállítjuk az összes lehetséges bemeneti kombinációt az f: függvény teszteléséhez |0〉 |0〉 |1〉
H H H
f
A bemeneti állapot: (|00〉 + |01〉 + |10〉 + |11〉)(|0〉 – |1〉)
Kimeneti állapot: ((–1) f(00)|00〉 + (–1) f(01)|01〉 + (–1) f(10)|10〉 + (–1) f(11)|11〉)(|0〉 – |1〉) A helyes bemenetek a kvantumállapotok fázisában kódolva jelennek meg!
|0〉 |0〉 |1〉 állapot = 0 1 0 0 0 0 0 0
ab c
00 01 11 10
01 1
H H H
f
állapot = 0.353 -0.353 0.353 -0.353 0.353 -0.353 0.353 -0.353
ab c
01
0.3 –0,3
00 01 0.3 –0,3 11 0.3 –0,3 10 0.3 –0,3
X X
H H
állapot = 0.353 -0.353 0.353 -0.353 0.353 -0.353 -0.353 0.353
ab c
állapot = 0.353 -0.353 0.353 -0.353 0.353 -0.353 -0.353 0.353
01
00 0.3 –0,3 01 0.3 –0,3 11 - 0.3 0,3 10 0.3 –0,3
H
állapot = -0.353 0.353 0.353 -0.353 0.353 -0.353 0.353 -0.353
ab c
01
H
állapot = 0 0 -0.5 0.5 0.5 -0.5 0 0
ab c
X X
H H H
M M M
állapot = 0 0 -0.5 0.5 0 0 0.5 -0.5
01
00 0.3 –0,3 00 - 0.3 0,3 01 0.3 –0,3 01 0.3 –0,3 11 - 0.3 0,3 11 0.3 - 0,3 10 0.3 –0,3 10 0.3 – 0,3
ab c
01
ab c
01
00 0 0 00 0 01 - 0.5 0,5 01 - 0.5 11 0 0 11 0.5 10 0.5 – 0,5 10 0
0 0,5 - 0.5 0
|0〉 |0〉 |1〉
H H H
f
X X
H H
áll. = 0.353 -0.353 0.353 -0.353 0.353 -0.353 -0.353 0.353
ab c
01
00 és 11 közötti fáziscsere
ab c
01
00 0.3 –0,3 00 - 0.3 0,3 01 0.3 –0,3 01 0.3 –0,3 11 - 0.3 0,3 11 0.3 - 0,3 10 0.3 –0,3 10 0.3 – 0,3
Hadamard: 00 és 11 megkülönböztetése
ab c
01
H
áll. = -0.353 0.353 0.353 -0.353 0.353 -0.353 0.353 -0.353
H
áll. = 0 0 -0.5 0.5 0.5 -0.5 0 0
Ha az első bit 1 invertáljuk a 2.-at
ab c
01
00 0 0 00 0 01 - 0.5 0,5 01 - 0.5 11 0 0 11 0.5 10 0.5 – 0,5 10 0
0 0,5 - 0.5 0
X X
áll. = -0.353 0.353 0.353 -0.353 0.353 -0.353 -0.353 0.353
áll. = 0 0 -0.5 0.5 0 0 0.5 -0.5
H H H
ab c
01
00 -0.3 01 0.3 11 -0.3 10 0.3
0.3 -0.3 0.3 -0.3
ab c
M áll. = 0 0 0 0 0 0 0 -1
áll. = -0.353 0.353 0.353 -0.353 0.353 -0.353 -0.353 0.353
Invertálás 00 és 11 között
M M
áll. = 0 0 0 0 0 0 0 1
Hadamard
01
00 - 0.3 0.3 01 0.3 - 0.3 11 - 0.3 0.3 10 0.3 - 0.3
ab c
00 01 11 10
01
-1
|0〉 |0〉 |1〉
H H H
f
H H
X X
H
|ψ00〉 = – |00〉 + |01〉 + |10〉 + |11〉 |ψ01〉 = + |00〉 – |01〉 + |10〉 + |11〉 |ψ10〉 = + |00〉 + |01〉 – |10〉 + |11〉 |ψ11〉 = + |00〉 + |01〉 + |10〉 – |11〉
H
X X
H H H
M M M
A Hadamard transzformáció után már ismert a helyes megoldás a -1 fázis alapján. Azonban a megoldás ekkor még a komplex Hilbert-térben értelmezett. A megoldást valahogyan ki kell nyernünk.
A helyes kimenethez tartozó fázis: -1.
Minden helyes színezési lehetőség negatív fázissal jelenik meg
Inicializáló állapot |0>
Hadamard transzformáció
Hadamard transzformáció Orákulum: komparátorok, ÉS kapuk Orákulum kimenete
Bemeneti bitek
Kvantum keresés A node az U I = U sU k iterációt többször alkalmazza a kvantumregiszterre Az iteráció eredményeként a keresett k állapotot kiemeli a ψ 0 − állapotból Az iteráció leírható egy θ szögű forgatási transzformációval is, amelyre
1 sin θ = n . 2 2
Az U I iteráció j − alkalommal történő végrehajtása után az ψ 0 állapotból kiemelhetjük a keresett k állapotot. A k állapot valószínűségi amplitudója ekkor:
a = sin ( ( 2 j + 1) θ ) . j k
Kvantum keresés
A ψ vektor tükrözése L-en
Az ψ vektor elforgatása
Kvantum keresés L1 és L2 közti távolság: θ Tetszőleges ψ állapot elforgatása 2θ -vel: 1. ψ tükrözése L1 mentén 2. Kapott eredmény tükrözése L2 mentén
Egy iterációs lépés: ψ elforgatása 2θ -vel
Kvantum keresés Az U I iterációt j =
π − 2θ alkalommal végrehajtva az ψ 0 kindulási állapoton, 4θ
a keresett k állapot fázisa:
( 2 j + 1)θ ≈
π 2
,
így az állapot előfordulási valószínűsége a node kvantumregiszterén belül:
⎛π ⎞ a = sin ⎜ ⎟ = 1. ⎝2⎠ j k
⎡π ⎤ Hibázási valószínűség: 1 2 N , ha a node az U I iterációt int ⎢ ⎥ − szer hajtja végre. ⎣ 4θ ⎦
Kvantum teleportáció
SWAP – állapotok felcserélése
A B
A
A ⊕ ( A ⊕ B) = B
A⊕ B
A⊕ B
B A
B ⊕ ( A ⊕ B) = A
A csomópontok kommunikációjaKvantumteleportáció ψ
M1
H
M2
Ψ+ XM2
ψ0 = ψ ⋅ Ψ
+
ZM1
1 ( 00 + 11 ) = (α 0 + β 1 )⋅ 2
ψ
A csomópontok kommunikációjaKvantumteleportáció ψ
H
M1
M2
Ψ+ XM2
ZM1
1 (α 0 ⋅ ( 00 + 11 ) + β 1 ⋅ ( 00 + 11 )) ψ1 = 2
ψ
A csomópontok kommunikációjaKvantumteleportáció ψ
H
M1
M2
Ψ+ XM2
ψ2
ZM1
1 ⎡ 00 ⋅ (α 0 + β 1 ) + 01 ⋅ (α 1 + β 0 ) + ⎤ = ⎢ ⎥ 2 ⎢⎣ 10 ⋅ (α 0 − β 1 ) + 11 ⋅ (α 1 − β 0 ) ⎥⎦
ψ
A csomópontok kommunikációjaKvantumteleportáció ψ
H
M1
M2
Ψ+ XM2 00, 01, 10 vagy 11
ZM1
ψ
Kvantumteleportáció Összefoglalás Alice
Bob kvantumbitje
Bob Eredmény transzformációja
00
α 0 +β1
I
01
α 1 +β 0
X
10
α 0 −β1
Z
11
α 1 −β 0
Y = ZX
α 0 +β1
Kvantumteleportáció Összefoglalás z
z z z z
A teleportáció segítségével egy adott kvantumbit újraépíthető egy fizikailag különböző helyen, azonban az eredeti kvantumállapot megsemmisül A teleportációhoz szükséges EPR állapotok elemi kvantumáramkörökkel létrehozhatóak Olcsó megvalósítás, hatékony működés A kvantumteleportáció kombinálható a kvantum-párhuzamosság jelenségével A párhuzamos, elosztott rendszerű kvantumhálózat hatékonysága tovább fokozható
