13.2. Kommunikációs és kriptográfiai kvantumalgoritmusok

Az ebben az alfejezetben tárgyalt algoritmusok a kommunikáció/kvantumkommunikáció és kriptográfia/kvantumkriptográfia szempontjából is fontos szerepet játszanak.

Az első algoritmus, amiről röviden szólunk a Simon algoritmus továbbfejlesztése, ami már nem fekete doboz modellű, de arra épül. A Shor algoritmus a hagyományos kriptográfia szempontjából kiemelten fontos.

13.2.1. Shor algoritmusa – prímfaktorizáció

Szokásos megoldási módja egyes (matematikai, fizikai, illetve számítási) feladatoknak, amik valamilyen függvény segítségével adottak, hogy az eredeti függvényt transzformáljuk , a transzformált függvényt használjuk, a problémát így oldjuk meg, majd az eredményt visszatranszformáljuk, ezzel előállítva az eredeti probléma megoldását (az eredeti függvény eredetileg vizsgálandó tulajdonságait). Az alkalmazott transzformáció rengeteg gyakorlatban is előforduló probléma esetén a Fourier transzformáció (idő és frekvencia domének közti átalakítás), mely linearitása miatt a kvantumszámítások esetén is jól használható. E transzformáció kvantumos megfelelője a kvantum Fourier transzformáció:

a 0-tól -ig tartó egész számokat tartalmazó intervallumra. A kvantum Fourier transzformáció hatékonyan implementálható. A Shor algoritmus pedig a kvantum Fourier transzformáción alapul és klasszikus elő- és utószámítást is tartalmaz.

A prímfaktorizáció problémájának a következő megfogalmazását használhatjuk: adott egy természetes szám , ha összetett, akkor adjuk meg egy valódi osztóját. A probléma matematikai érdekessége mellett gyakorlati szempontból is fontos, hiszen a kriptográfiában napjainkban használt algoritmusok nagyrésze számelméleti sejtéseken alapul. Ilyenek az ún. egyirányú függvények, ahol az egyik irány gyorsan kiszámítható, a másik irány viszont sokkal bonyolultabb, számításigényesebb. Erre egy gyakran használt példa a prímfaktorizáció. Prímszámok összeszorzása egyszerű, de az eredmény prímtényezőkre bontásához nem ismert klasszikus hatékony (gyors) algoritmus.

A Shor algoritmus a korábban ismertetett Deutsch, Deutsch-Jozsa és Simon algoritmusokkal együtt a rejtett részcsoport probléma osztályba tartozik. Ennek megfelelően az algoritmus maga is nagyon hasonlít ezekre a korábban részletezett algoritmusokra.

Ahogy korábban írtuk a Simon algoritmus az alakú függvények, mint bináris vektorfüggvények periodikusságát vizsgálja. Ennek ellenére, csak egy kis változtatás kell az algoritmusban, hogy tesztelje az típusú függvények periodikusságát (ahol a bitsorozatok természetes számként vannak interpretálva). Ez egy kiemelten fontos problémája a hagyományos, ma is elterjedten használt kriptográfiának. Röviden, ha polinomiális időben meg tudjuk találni az függvény periódusát, akkor a természetes számok prímfaktorizációját, illetve a diszkrét logaritmus problémát is megoldhatjuk determinisztikus polinomiális időben, így az ezekre épülő nyíltkulcsú titkosítási algoritmusokat, pl. az RSA-t is polinomiális időben tudjuk feltörni. Ez az eredmény Shor nevéhez fűződik, aki kicserélte a Hadamard szűrőt a Simon algoritmusban, kvantum Fourier-transzformáció szűrőre, hogy megmutassa, hogyan is kell ezt csinálni. A fenti okfejtés alapján az algoritmus hatalmas gyakorlati jelentőséggel bír: Amíg hagyományos számítógépen a faktorizációra nem ismert polinomiális idejű determinisztikus algoritmus (bár az sem bizonyított ezidáig, hogy a probléma nincs a P problémaosztályban), kvantumszámítógépen négyzetes időben történik a faktorizáció. A hagyományos modern kriptográfiai titkosítások biztonsága azon alapul, hogy pl. a faktorizáció csak exponenciálisan lassan oldható meg. A nagyobb teljesítményű kvantumszámítógépek megjelenése tehát elveszi e rendszerek biztonságát.

Az algoritmus a Simon algoritmushoz hasonlóan valószínűségi, tehát nem feltétlenül minden futása ad helyes eredményt. Habár elvileg az algoritmus segítségével nagy számok is faktorizálhatóak, a kísérleti megvalósítások csak lassan indultak be. 2001-ben egy 7-kubites NMR (nukleáris mágneses rezonancián alapuló) kvantumszámítógépen a 15 számot sikerült faktorizálni, megmutatva, hogy az algoritmus a gyakorlatban is működik. 2011-ben volt előrelépés, amikor optikai kvantumgépen a 21-et faktorizálták a Shor algoritmus alapján, és még ebben az évben egy folyadék kristályos NMR gépen a 143 számot faktorizálták, igaz ezt nem az eredeti Shor-féle algoritmussal, hanem egy adiabatikus kvantumalgoritmussal. Egyelőre azonban még messze tartunk attól, hogy akkora számokat faktorizáljunk, amiket a jelenlegi titkosítási rendszerekben használnak (de valószínű ez csak idő kérdése)...

13.2.2. Kvantumkommunikáció

Mivel egy kvantumbit mérésével egy bitnyi információhoz jutunk, hiába használunk kubiteket egy kommunikációban, ha klasszikus bitnyi információt szeretnénk továbbítani, azt nem tehetjük meg ennél kevesebb kubittel sem.

Ennek ellenére a kvantumos technológiának rengeteg alkalmazása lehet a kommunikációban. Az egyik legkézenfekvőbb alkalmazás az üzenet tartalmának hibamentesség-ellenőrzése. Legyen adott Alíz és Bálint, Alíz egy bit hosszúságú klasszikus bitsorozatot küld el Bálintnak. Most mindketten rendelkeznek egy-egy bites adattal, de különböző kommunikációs hibák (pl. zajos kommunikációs csatorna) miatt nem lehetünk biztosak abban, hogy e két bites adat megegyezik egymással. Klasszikusan egy bites üzenet ellenőrzéséhez bitre van szükség és ez elegendő is (hogy bizonyosak lehessünk az azonosságukban). (Egyébként, ha hiba van az üzenetben, akkor az pl. egy külső „mindent látó” szemlélő segítségével sokkal kisebb extra kommunikációs költséggel kimutatható, hiszen a szemlélően elég rámutatnia a nem egyező bit helyére..., viszont ha a két bitsorozat egyezik, azt ez a szemlélő sem tudja röviden bebizonyítani Alíz és Bálint számára.) Kvantumszámítógép segítségével viszont a kommunikációs költség csökkenthető: Az egyenlőség függvény tesztelése két bit hosszú sorozatra kubit mennyiséggel megtehető a Deutsch-Jozsa algoritmusra visszavezetve, a két bitsorozat Hamming távolságát tekintve (ami pontosan ott tartalmaz 1-et, ahol eltérés van a két bitsorozat közt).

A következő részben a kommunikáció titkossága lesz a fő szempont.

13.2.3. Kvantumkriptográfia

Amint részletesen tárgyaltuk a Shor algoritmusnál, a klasszikus (jelenleg is általánosan használt) kriptográfia nagyon sebezhetővé válik a kvantumszámítógépek számítási kapacitásának növekedésével. Ezzel szemben a kvantuminformatika nemcsak gondot jelent azoknak, akik titokban szeretnék tartani kommunikációjuk tárgyát. Ebben a részben magát a kvantuminformatikát használjuk az adatok titkos (biztonságos) továbbítására.

Tegyük fel, hogy Alíz és Bálint szeretnének kommunikálni egymással. Ehhez első lépésben Alíz odaadja egy személyes találkozó keretében Bálintnak a kulcsot (egy bitsorozatot), amihez így más nem férhet hozzá.

A kommunikáció maga kubitekkel történik, amiket pl. fotonokkal valósítanak meg. Legyen adva két ortonormált bázis:

(pl. a polarizált foton rezgési irányainak megfelelően), ahol

Alíz és Bálint megegyeztek, hogy a és kubitek az 1, míg a és kubitek a 0 értéknek felelnek meg majd az elküldött üzenetekben. Ekkor Alíz az üzenetét a Bálintnak adott kulcs szerint a következőképpen kódolja: ha a kulcsban az . helyen a bit található, akkor az első ( ) bázis szerint kódolja az üzenet . bitjét, míg ha bit van a kulcs . helyén, akkor a másik ( ) bázis szerint. Világos, hogy Bálint megkapva az üzenetet, annak minden egyes kubitjét a megkapott kulcs szerinti bázis szerint méri, így helyesen dekódolva az üzenetet. Ezzel szemben, ha egy támadó megkapja az Alíz üzenetét, akkor minden egyes kubiten, amire mérést végez (a kulcs hiányában) 50% esélye van, hogy helyes bázisban méri (és ekkor helyesen dekódolja a kubit megváltoztatása nélkül, hiszen az adott bázisban a kubit sajátállapotban volt, amit a mérés 1 valószínűséggel jól ad meg és nem változtat meg). Viszont minden ilyen elolvasott kubitnél 50% az esélye, hogy nem a helyes bázisban próbálja meg elolvasni, amikor is az eredeti kubit megváltozik, és 50% eséllyel az egyik, 50% eséllyel a másik sajátállapotba áll be a mérésnél használt bázis szerint. Ekkor viszont ezt az elrontott kubitet Bálint 50% eséllyel rosszul fogja dekódolni, ami hibaként jelentkezik. Minél több bitet próbáltak lehallgatni, annál nagyobb lesz a hibás bitek száma, aminek segítségével azonnal kiderül, hogy a csatornát lehallgatják.

A következőkben azt mutatjuk be, hogy a kvantummechanika EPR jelenségét is kihasználhatjuk az üzenettovábbítás biztonságosságára. Tekintsünk a következő áramkört, amely segítségével összefonódott kubitpárt tudunk létrehozni. Legyen a két input kubit mindkettő állapotú, az elsőn végezzünk egy Hadamard-transzformációt, majd ezt az első szálat használjuk arra, hogy vezéreljen egy kaput, ami a másik kubitet összefonja ezzel (lásd a 13.4. ábrát).

13.4. ábra - Összefonódott kubitek előállítása (pl. kriptográfiai alkalmazáshoz).

Összefonódott kubitek előállítása (pl. kriptográfiai alkalmazáshoz).

Ekkor a kezdeti állapotból a rendszer az első kubitre a Hadamard kapu alkalmazásával az állapotba kerül, majd a kapu alkalmazásával ez az állapotba megy át. Alíz elküldi Bálintnak egy ilyen összefonódott kubitpár egyik példányát Bármelyikük is méri meg előbb a nála levő kubitet, 50% valószínűséggel fog -t, illetve -et mérni. Tegyük fel, hogy Alíz megméri a nála levő kubitet, és a mérés eredménye. Ezzel az összefonódott állapot összeomlik, a Bálintnál levő példány állapota is módosul, értéke így ennek is csak lehet. Hasonlóan alakul a jelenség, ha Alíz kubitje -et ad a mérésre. Így a párok segítségével kommunikálhatnak, ahogy pl. a következő részben látni fogjuk.

13.2.4. Kvantumteleportáció

A teleportáció, vagyis objektumok átvitele a térben távoli helyre az objektumok „szokásos mozgási sebességét jelentősen meghaladó módon”, sok tudományos fantasztikus műben megjelenik. Tulajdonképpen egy három fázisból álló műveletről van szó, melynek részei: elkülönítés, információ-átvitel, rekonstrukció. A fax működése is hasonló, de a fax esetén az eredeti megmarad a küldő félnél és csak egy (az eredetihez közel álló) másolat jön létre a célhelyen. Ezzel szemben a teleportáció esetén az eredeti objektum megsemmisül, miután elég információt szereztünk róla, az anyaga nem utazik semmilyen formában a küldő és a célhely között, viszont egy, az eredetivel megegyező példány jön létre a célhelyen a művelet végére.

A kvantumteleportáció segítségével kvantuminformációt tudunk távoli helyre eljuttatni. A cél, hogy egy részecske kvantumállapotát eljuttassunk a célhelyre klasszikus bitek segítségével létrehozva az eredeti kvantumállapotot a célhelyen, vagyis, hogy kubitek küldése nélkül vigyük át a kubit tartalmát (állapotát) egyik helyről a másikra.

Emlékezzünk, hogy a csere kapuval, a kapuval éppen két kubit értékének cseréjét valósítottuk meg. Célunk most is hasonló, csak két egymástól távol elhelyezkedő kubitre, amelyek egyike Alíznél, a másik pedig Bálintnál van...

Tehát, Alíz szeretne Bálinthoz eljuttatni egy kubitet (illetve a benne tárolt információt), aminek állapota . Tehát klasszikus kommunikációs csatorna áll rendelkezésre, amin klasszikus biteket tudunk küldeni. A küldendő kubit tetszőleges, Alíz által ismeretlen állapotú lehet, így Alíz nem mérheti meg, hiszen ezzel a kubit értéke megváltozhatna; amint tudjuk, a kubit nem is klónozható. Úgy tűnhet, hogy az egyetlen mód a kubit elküldésére annak fizikai eljuttatása lehet Bálinthoz, vagy egy másik kvantumrendszerbe bekódolva annak tartalmát, e másik rendszer fizikai eljuttatása...

Alíz és Bálint egy összefonódott értékű kubitpár segítségével fog kommunikálni, aminek első tagja Alíznél, másik tagja Bálintnál van. A teleportáció megvalósítását a 13.5. ábra szemlélteti.

13.5. ábra - A kvantumteleportáció elve.

A kvantumteleportáció elve.

Legyen tehát az input állapota a rendszernek a

ami a műveleteket elvégezve, a

alakba írható. Az első két kubit Alíznél van, míg a harmadik Bálintnál. Most Alíz a transzformációt alkalmazza (vagyis a vezérelt nem transzformációt az első két kubitre), így előáll az

állapot. Ekkor Alíz alkalmazza erre a transzformációt (vagyis Hadamard-transzformációt az első kubitre):

Átcsoportosítással ez a következő formába írható:

Ekkor Alíz 25% valószínűséggel mérheti a négy lehetséges kvantumállapot ( , illetve ) mindegyikét. A mérés eredményétől függően a Bálintnál levő kubit értéke az , illetve az eredményt veszi fel. Ekkor Alíz a mérésének eredményét két klasszikus bitként elküldi Bálintnak. Ezek alapján Bálint visszaállíthatja a nála levő kubit értékét egy dekódoló transzformációval. Ez a dekódoló operátor pl. a bitpár esetén az identikus transzformáció. Ha Alíz az biteket küldi el Bálintnak, akkor a dekódolás a ún. Pauli-mátrixú operátorral történik; ha az üzenet a , akkor pedig a Pauli-mátrixú operátort kell Bálintnak alkalmaznia a nála levő biten. Ha pedig az üzenet , akkor a adja az alkalmazandó dekódoló transzformációt.

Itt jegyezzük meg, hogy az esetben alkalmazott operátor mátrixát első Pauli mátrixnak, a esetben alkalmazottat harmadik Pauli mátrixnak hívjuk. Az eset mátrixa a második Pauli mátrix szerese, ami előáll a harmadik és első mátrixok szorzatának -szereseként is. A Pauli mátrixokat tehát, mint kvantumkapukat is alkalmazhatjuk, bit- és fázis-eltolásra.

A kvantumteleportációval tehát nem objektumot, hanem annak kvantumállapotát teleportálhatjuk (juttathatjuk el távoli helyre, annak elküldése nélkül): egy kubitnyi információ elküldéséhez két klasszikus bit elküldése és egy EPR párra van szükség. Ez a jelenség a gyakorlatban is működik, először Bennett és csoportja teleportált egy kubitet 1993-ban. 2012-ben viszont már makroszkopikus objektumot (kb. darab Rubídium atom alkotta kvantum-memóriaegység kvantuminformációját) is sikerült, fotonokat felhasználva, optikai kábelen 150 m távolságra teleportálni.

Habár elvileg a kvantumtechnika segítségével lehetséges teljesen biztonságos kommunikáció megvalósítása, ezt a gyakorlatban nem feltétlenül egyszerűen megoldható, hiszen több eszköz összekötésekor bármelyik „klasszikus” berendezés, vagy az emberi butaság lehet a gyenge láncszem, amin keresztül a rendszer feltörhető.