13. fejezet - Kvantumalgoritmusok

Nézzük tehát, hogyan aknázhatjuk ki a kvantummechanika egyes jelenségeit, hogyan foghatjuk számításra, feladatmegoldásra a kvantumbiteket.

Ebben a fejezetben tehát a kvantumalgoritmusokról ejtünk néhány szót. Általában egy kvantumalgoritmus, vagy kvantum-program a következőképpen néz ki: alkalmazunk egy unitér operátort (megfelelő számú kvantumbitre), majd (általában egy!) mérést végzünk. Ez alapján adjuk meg a választ a megoldandó kérdésre.

Az unitér operátort általában, mint logikai kapcsolást adjuk meg, melyben a korábban ismertetett alapvető kvantumkapukat használjuk. Egy kvantumhálózat tehát kapukból áll, illetve hogy mely kapu mely kubite(ke)n alkalmazandó, és a kapuk milyen sorrendben alkalmazandóak. A számításnak az unitér operátor része reverzibilis, a mérés viszont általában irreverzibilis lépés a számítás végén, melynek során a rendszer beáll egy sajátállapotba.

Az algoritmusok tervezésében fontos szerepet játszik az, mint már említettük, hogy a kvantumszámítások esetén is van(nak) olyan kapu(halmazo)k, amelyek segítségével minden, a számításokhoz szükséges unitér transzformáció elvégezhető. Itt jegyezzük meg, hogy a kvantumalgoritmusok bonyolultságelmélete leginkább a hagyományos Boole-áramköri kapcsolások (logikai hálózatok) bonyolultságához áll közel, hiszen akkor gondolunk egy kvantumalgoritmust gyorsnak, vagy hatékonynak, ha az algoritmus által leírt unitér operátor polinomiálisan sok Hadamard, 45˚-os fáziseltolás és kapuval elvégezhető (az input méretének függvényében).

Ábráinkon, továbbra is, a szokásos balról jobbra történő számítási folyamatot mutatjuk be. Ahogy láttuk, több-bites kapukból elegendő a vezérelt kapuk használata, amik csak egyetlen kubitet változtathatnak meg, azt is csak a vezérlő bit „engedélyével”. Az ilyen többkubites kapukat a célbit vonalára rajzoljuk, ahogy eddig is, a vezérlő bit(ek) vonalát/ait pedig függőlegesen vezetjük el a kapukhoz. Az ilyen vezérlőszálak a kvantum-összefonódást is jelképezik az adott kubitek között.

13.1. Az első kvantumalgoritmusok

A kezdeti kvantumalgoritmusok a következő alakúak voltak: az input bit (általában a 2 valamelyik hatványa). Számítsunk ki egy igen-nem függvényt erre a bemenetre, vagyis a kimeneti függvény minden megengedett bemenetre a 0 vagy az 1 értéket adja. Ezeket az algoritmusokat a kvantumszámítások fekete-doboz modelljének is hívják. A számítás, mintegy fekete dobozban történik és végül egyetlen méréssel kell választ adnunk a feltett kérdésre. Az algoritmus számítási erejét a klasszikus paradigmához képest azzal demonstráljuk, hogy az bitből hányat kellett „elolvasni” ahhoz, hogy a helyes választ megadjuk.

13.1.1. A Deutsch algoritmus

Deutsch problémája a következő: legyen adott egy egyváltozós Boole függvény. Tegyük fel, hogy adott egy fekete doboz arra, hogy kiszámítsuk, vagyis az eredmény megvan, de nem látjuk. Amit szeretnénk tudni az az, hogy az függvény konstans (vagyis ) vagy kiegyensúlyozott (azaz ugyanannyi 0 van az multihalmazban, mint 1). Ez utóbbi feltétel egybites függvény esetén éppen megfelel az feltételnek. Egy klasszikus számítógépen mind az és kiszámítására szükség van, és egy összehasonlítással, vagyis két méréssel (hiszen az összehasonlításhoz mindkét értéket „ki kell olvasnunk”) tudjuk megválaszolni a feltett kérdést.

Talán a legegyszerűbb és legrégebbi kvantumalgoritmus, ami ugyanakkor már jól mutatja a kvantumszámítások erejét, az Deutsch problémájának a megoldása kvantumalgoritmussal.

Tulajdonképpen azt szeretnénk megtudni, hogy két bit értéke megegyezik-e, vagy különböző. Ez a probléma paritás problémaként is ismert, hiszen éppen a két bit összegének a paritása (vagyis kizáró vagyuknak: az értéke) a kérdés, amire választ szeretnénk kapni. A kvantum számítástechnikában szokásos módon egyetlen mérés eredményéből határozzuk meg az eredményt.

Feltehetjük, hogy a fekete doboz egy (megfordítható) unitér operátort, az -et valósítja meg, amely az és bemenetekhez az és kimeneti kubiteket rendeli. Ez a kapu az első kubiten nem változtat. A második kubitet átfordítja, ha az értéke az első kubiten 1, ellenkező esetben (ha az értéke az első kubiten 0) viszont nem változtat a második kubiten sem. Ne feledjük, hogy az kaput kvantumkapuként definiáltuk, ezt ki is fogjuk használni. A Deutsch algoritmusát megvalósító kvantumhálózat a 13.1. ábrán látható.

13.1. ábra - A Deutsch algoritmus.

A Deutsch algoritmus.

A megvalósításban szerepel három Hadamard kapu és az előbb leírt kétbites kapu. A kezdeti Hadamard kapuk elforgatják a két bemenő sajátállapotban levő kubitet félig az igaz és hamis közé:

Az tehát egy által vezérelt kapunak tekinthető, aminek formális definíciója, ahogy korábban tárgyaltuk:

Az függvény a -ből képez a -be, és ez lehet konstans, vagy kiegyensúlyozott. (Egy -re képező és diszkrét halmazon értelmezett függvényről akkor mondjuk, hogy kiegyensúlyozott, ha mind a 0, mind az 1 értéket ugyanannyiszor veszi fel. Ez a jelen esetben egyszer-egyszer, tehát a függvények vagy konstansok vagy kiegyensúlyozottak. Ennek a látszólag bonyolult megfogalmazásnak majd a probléma általánosításánál lesz jelentősége.) Mivel a felső szálon lévő első Hadamard operátor a -át az -be viszi át, ezért egyidőben betölthetjük -be a -át és -et, vagyis valódi kvantumkapuként használhatjuk az -et. Ennek megfelelően számoljuk ki, hogy a fekete dobozunk alkalmazása után a rendszer milyen állapotban lesz. A számolást megkönnyítendő, először a második kubit értékét helyettesítjük be, az első helyére egyelőre még -t írunk:

ami (függetlenül attól, hogy vagy ) a

alakba írható. Most helyettesítsük be az első kubit értékét:

Ezek után, az első kubitre alkalmazva a harmadik Hadamard operátort az eredményül kapott állapot

alakú lesz. Mivel tudjuk, hogy az és csak 0 vagy 1 értéket vehetnek fel, könnyen ellenőrizhető, hogy az eredmény a

alakba írható át. Nézzük mi is ez az érték konkrétan. Ha az konstans, azaz , akkor értéke 0 lesz, az első kubit értéke pedig

Ezzel szemben, ha a vizsgált függvényünk kiegyensúlyozott, akkor , és ennek megfelelően az első kubit értéke

Ezek után tehát ahhoz, hogy megtudjuk, hogy konstans, vagy kiegyensúlyozott, nem kell mást tennünk, mint megmérni a felső szál állapotát, vagyis az eredmény állapot első kubitjét. Ha ez , akkor biztosan konstans, ha , akkor pedig biztosan kiegyensúlyozott.

Felmerülhet a kérdés, hogy valójában léteznek e az kvantumkapuk minden lehetséges függvényre. Ehhez először gondoljuk át, hogy hányféle függvény létezik. Klasszikus egyargumentumú Boole függvényről van szó, amiből négy darab van. Az első esetben . Ekkor a szokásos Hilbert térbeli reprezentációval élve (ahogy eddig is, pl. a 0-nak a felel meg) az kapu az bemenethez az

kimenetet adja, vagyis a -es identitás operátor által leírt unitér operátor az ebben az esetben. Lássuk, most a második esetet, amikor . Ekkor a lehetséges input-output párok:

Könnyen belátható, hogy , vagyis éppen a vezérelt negáció kapu valósítja meg ezt az esetet. A többi esetben is hasonlóan megoldható az operátor felírása.

Láthattuk, hogy, amint a vezérelt kapuktól elvárható, az összekapcsolta a két kubit kvantumállapotát egy összefonódott kvantumállapotba. Ha egy ilyen pár egyik kubitjén mérés vagy dekoherencia jelenség következik be, akkor nemcsak ennek az állapota omlik össze, de a pár másik tagjának állapota is.

Deutsch algoritmusa szépen mutatta be a kvantumalgoritmusok két nagyon fontos jellemzőjét, a kvantumpárhuzamosságot és az összefonódott kubitek kihasználását. Az előző feladat egy kézenfekvő általánosítását mutatjuk be a következő alfejezetben.

13.1.2. A Deutsch-Jozsa algoritmus

Az Deutsch probléma egybites Boole függvényekkel dolgozott, tekintsünk most általánosan egy olyan Boole függvényt, ami -bites inputtal (vagyis -féle lehetséges inputtal) rendelkezik, amelyről tudjuk, hogy a függvény vagy konstans, vagy kiegyensúlyozott, tehát vagy minden inputra az -et, vagy minden inputra a -t adja (ebben a két esetben konstans), vagy pontosan az esetek felében ad és (a másik) felében kimenetet.

Ezen feladat klasszikus megoldásához a legrosszabb esetben (pl. konstans kimenet esetén) a függvény értékét különböző inputra meg kell határozni (mérni).

Ezzel szemben kvantumosan sokkal ügyesebben számolhatunk, egyetlen mérést alkalmazva: A Deutsch-Jozsa algoritmus nagyon hasonlít az előzőekben tárgyalt Deutsch algoritmushoz, tulajdonképpen annak általánosítása több bitnyi információ együttes tartalmának mérésére. Az algoritmust megvalósító áramkört a 13.2. ábrán mutatjuk be esetre, de valójában több input bit esetén is hasonlóan néz ki.

13.2. ábra - A Deutsch-Jozsa algoritmus kapcsolási rajza.

A Deutsch-Jozsa algoritmus kapcsolási rajza.

A Hadamard kapuk ebben az áramkörben ugyanúgy működnek, mint a Deutsch algoritmus esetén, az kaput viszont most nem egy, hanem darab szál vezérli. Az függvény tehát -ből képez a -be, és feltételezzük, hogy az vagy konstans lehet, vagy kiegyensúlyozott. (Itt jegyezzük meg, hogy ellenben a Deutsch algoritmusnál tárgyaltakkal, ezesetben kettőnél több bit együttese esetén természetesen nem csak konstans, illetve kiegyensúlyozott függvények értelmezhetőek. A Deutsch-Jozsa algoritmusnál viszont feltétel, hogy az függvény e két kategória egyikébe essen.) A feladatunk tehát az, hogy mindössze egyetlen méréssel megállapítsuk, hogy a két lehetséges kategória közül melyik teljesül az -re.

Alkalmazzuk először a Hadamard kapukat az darab kiinduláskor értékű kubitre. Ennek eredménye, ahogy a (11.) egyenletben már korábban is szerepelt,

A legutolsó bemenetre alkalmazva a kaput

kubitet kapjuk, így a teljes rendszer állapota:

Alkalmazzuk most az -szeresen vezérelt kaput, ekkor a rendszer kvantumállapota

lesz, felhasználva az előző algoritmusnál tárgyalt részeredményeket.

A Hadamard kapukat felírhatjuk a következőképpen a bázisvektorokra (sajátállapotokra):

vagyis

Ezt a formulát kell kubit tenzorszorzatára alkalmazni, ahhoz hogy alkalmazhassuk majd a kapukat az első kubitre. Ekkor,

ahol bevezettük az és vektorjelölést, valamint

Most már alkalmazhatjuk az algoritmusunkban ezeket a kapukat, így

Már csak az eredmény elolvasása van hátra. Ehhez vizsgáljuk meg, hogyan alakul az eredmény, ha konstans. Ekkor az -es tag kiemelhető a szummák elé, így a szummás tag az marad hogy

Ekkor rögzített értékre vizsgáljuk meg mi is lesz a

értéke. Ha az , akkor

nullának kell lennie, mivel az -ban kiegyenlíti egymást a páros és páratlan értékek száma, így a -ek és -ek száma is a -ban. Ezesetben viszont csak a tag marad meg. Így

lesz a végállapot.

Másrészt, ha viszont kiegyensúlyozott, akkor esetén

lesz az eredmény, mert ugyanannyiszor eredményez -et mint -et a tagban. Ekkor tehát a valószínűségi amplitúdója, hogy a rendszert állapotban találjuk 0.

Összefoglalva tehát, ha konstans, akkor a mért vezérlő szálak mindegyikének a kimenete kell, hogy legyen, vagyis a rendszer 1 valószínűséggel a állapotban kell hogy legyen a mérés előtt (és után is). A mérés minden egyéb kimenete esetén az kiegyensúlyozott kell hogy legyen, kiegyensúlyozott rendszer esetén ugyanis 0 valószínűséggel kapjuk a állapotot a mérés során.

A következő probléma még bonyolultabb, ezt az előző fekete doboz algoritmusunk továbbfejlesztésével oldhatjuk meg.

13.1.3. Simon algoritmusa

A Simon algoritmus az függvény periodikusságát teszteli. Az argumentumok és a függvényértékek is bináris vektorként vannak értelmezve, így lehet a periodikusságukról beszélni a következő értelemben.

A tesztelendő függvényének a következő feltételeket kell kielégítenie:

  • az által felvett minden függvényértékére igaz, hogy pontosan két különböző vektor van ( és , ), amelyre az adott értéket veszi fel az : ;

  • periodikus, azaz létezik olyan vektor, hogy minden vektorra .

Felmerülhet a kérdés, hogy ha az periodikus, akkor nem feltétlenül kellene az első feltételnek teljesülnie, sőt általában kettőnél több helyen is fel kellene vennie ugyanazt azt értéket, hiszen

Viszont itt nem hagyományos periodikusságról van szó, nem összeadjuk a vektorokat hanem kizáró vagy műveletet végzünk velük (ami a modulo 2 osztálybeli összeadást jelenti), ennek megfelelően pedig bármilyen vektorra , vagyis .

Tegyük fel tehát, hogy rendelkezik a megkövetelt tulajdonságokkal. A feladat a periódusvektor megtalálása. A klasszikus paradigmában csak olyan algoritmusok ismertek, amelyek az -nel exponenciálisan növő időben oldják meg a feladatot. Lássuk most a kvantumalgoritmust, amely lineáris időben (lineáris számú méréssel) megoldja ezt a problémát.

Egy példa látható a 13.3. ábrán a Simon algoritmusra egy alakú függvényre.

13.3. ábra - A Simon algoritmus kapcsolási rajza.

A Simon algoritmus kapcsolási rajza.

Általánosan bittel tekintve, az algoritmus tartalmaz a tetején kubitet, ugyanúgy, mint a Deutsch-Jozsa algoritmusban; és kubitet alul. Az alsó kubit mindegyike megfelel egy-egy típusú függvénynek melyek együttesen alkotják az eredetileg vizsgálandó függvényt.

Az -val jelölt négyzetek olyan vezérelt negáció kapuk, ahol a vezérlésről gondoskodik.

Összefoglalva tehát, a Simon algoritmus tesztel egy

alakú függvényt, amit ami darab (bináris) skalár értékű függvényre bontottunk:

Röviden tekintsük hogyan működik és miért is hatékony ez az algoritmus.

1. lépés A Hadamard-transzformáció alkalmazása az első darab kubitre létrehozza az összes 0-tól -ig előforduló egész szám egy szuperpozícióját egyetlen regiszterben:

2. lépés Az kapuk alkalmazásával az alsó kubit értéke a értékről az értékre állítódik át, hiszen ahol értéke 0-t ad ott a kubit értéke marad , ahol pedig értéke 1-et ad, ott átvált -ból -re, amivel éppen értékűvé válik. A rendszer állapota tehát

lesz. Az kapukkal tulajdonképpen a számítógép minden kubitje összefonódik.

3. lépés Az algoritmus következő lépésében az alsó kubiten hagyjuk hogy az összefonódottság megszűnjön (dekoherencia), ennek megfelelően ezen bitek felvesznek valamilyen értéket, ami vagy az -nak vagy az -nak felel meg (valamilyen vektorra). Ennek megfelelően a felső kubit ennek a két vektornak a szuperpozíciójába kerül (EPR jelenség), a rendszer állapota pedig

lesz. Miközben tehát az alsó kubiten a dekoherencia jelenség megy végbe, a velük összefonódott felső kubit, az EPR jelenség alapján valamilyen és a hozzá tartozó állapotok szuperpozíciójába kerül. Tehát a értéke már itt megjelenik bekódolva a felső kubitbe, de egyelőre még egy értékkel összekeveredve. Ennek a „kitisztítása” lesz a következő lépése az algoritmusnak.

4. lépés Alkalmazzuk most a felső kubitre a (jobboldali) Hadamard kapukat. A rendszer állapota a következő lesz:

Soroljuk az vektorokat két osztályba: az elsőben , a másikban . Az első osztályban

minden egyes együttható esetén. Ennek megfelelően csak azok az értékek kellenek a számításhoz, amelyek merőlegesek az vektorra (vagyis ). Ezek alapján a rendszer állapota:

Tehát végül megkapjuk -ra merőleges vektorok egy szuperpozícióját az első kubites regiszterben.

5. lépés Végül a felső kubitet mérve, tehát, mindig egy az -ra merőleges vektort kapunk. Igaz, hogy ez lehet bármelyik vektor a szuperpozícióból, de ha a elég sokszor ismételjük a kísérletet hogy kapjunk különböző vektort, akkor független egyenletet kapunk az vektorra:

Ezek pedig a klasszikus lineáris algebrai módszerrel egyszerűen megoldhatók -ra.

Még egyszer kiemeljük, hogy a Simon algoritmus a problémát exponenciálisan gyorsabban oldja meg, mint bármely ismert hagyományos (determinisztikus) algoritmus, a kvantumpárhuzamosságnak (szuperpozíciónak), az összefonódásnak és az EPR jelenségnek köszönhetően.

A helyhiány miatt a további algoritmusokat csak röviden ismertetjük (kb. az itteni lépéseknek megfelelő utasításoknak megfelelően).

13.1.4. Grover (kereső) algoritmusai

Az előzőekben ismertetett algoritmusoktól jelentősen eltérnek a kvantum kereső algoritmusok, amelyek közül a legismertebbek a Grover algoritmusok.

Rengeteg probléma, a rendezéstől, a gráfszínezésen át adatbázisban keresésig átfogalmazható olyan alakba, hogy találjunk olyan értéket, amelyre a predikátum teljesül. (Például, találjuk meg olyan permutációt egy vektornak, amiben bármely két egymás melletti elemre fennáll, hogy az utóbbi nem kisebb az előbbinél.) Van amikor a keresési tér strukturált, és a megoldást össze lehet rakni részfeladatok megoldásaiból. Néha ilyenkor így hatékony algoritmust is tudunk adni az eredeti probléma megoldására is. Néha viszont a keresési tér nem strukturált. Hogy érezzük a különbséget a strukturált és nem strukturált kereséséi terek közt tekintsük a következő Brassard által ajánlott példát. A feladat első része: keressük meg a városban lakó telefonszámát (a nevet ismerjük) a telefonkönyvből. A feladat másik része: adott egy telefonszám (a városunkból), találjuk meg kié ez a szám (a telefonkönyvből). Míg az első rész triviális, hiszen a telefonkönyvet éppen erre találták ki, benne az nevek szerinti betűrendben gyorsan kereshetünk, a másik része a feladatnak reménytelennek tűnik a nyomtatott telefonkönyv alapján. Hagyományos számítógépeken strukturálatlan adatszerkezet esetén a számítógépnek végig kell néznie az állományt addig, amíg nem talál olyan elemet, ami kielégíti a keresési feltételt. Ez általában átlagosan az adatok felének átnézésig tarthat.

Grover bizonyította, hogy strukturálatlan keresési térben kvantumszámítógéppel négyzet-gyökösen kevesebb „találgatással” is megoldható a feladat.

Tehát legyen adott egy elemből álló adathalmaz (strukturálatlan adatbázis). Legyen a legkisebb egész, hogy teljesüljön. Tegyük fel, hogy a predikátum egy olyan kapuval van implementálva amely minden párra az kimenetet adja. Ekkor Grover algoritmusa következőképpen néz ki:

  1. lépés Készítsünk el egy regisztert ami az halmaz összes elemének szuperpozícióját tartalmazza.

  2. lépés Számítsuk ki a értéket erre a regiszterre.

  3. lépés Minden olyan -re, amire változtassuk meg az amplitúdót -re.

  4. lépés Alkalmazzunk az átlag-transzformáció inverzét, hogy azon -k amplitúdóját megnöveljük, amikre .

  5. lépés Ismételjük a 2.-4. lépések közti részt -ször.

  6. lépés Olvassuk le az eredményt.

Amint látjuk a Grover algoritmus is arra támaszkodik, hogy az összes szám szuperpozícióját bekódoljuk a probléma karakterisztikus függvényébe, majd speciális módon megszűrve a regisztert megkapjuk a választ a feltett kérdésre. Az algoritmus 2. és 4. lépése közti részét szokás „Grover iterációnak” hívni. Az első két lépés a megszokott kvantumos lépeseknek tekinthető. A gond az, hogy mivel az eredmény szuperpozícióban van, elég kicsi az esély annak, hogy egy méréssel kinyerjünk egy megfelelő -t. Ezért a megfelelő vektorok amplitúdóját növeljük, amikre viszont a predikátum értéke 0, azokét csökkentjük. Ezt az algoritmus harmadik lépésében tesszük az átlagot megadó transzformáció inverzével (ez nagyságrendileg kvantumkapuval megtehető). Ily módon erősítjük az átlag feletti amplitúdó(ka)t és elnyomjuk az átlag alattiakat. Itt jegyezzük meg, hogy az iteráció további ismétléseivel az eredmény már romlik (a mérés eredménye nem biztos, hogy jó eredményt ad). Egyébként ez szokásos jellemzője a hasonló jellegű kvantumalgoritmusoknak, hogy az ismétlések számával először nő a jó eredmény esélye, de egy idő után az újabb ismétlések már rontanak a helyzeten. Ennek megfelelően a kísérletnek van egy olyan pontja, amikor célszerű megállítani a használható eredmény eléréséhez.

Láthatjuk, hogy itt a hatékonyságbeli különbség a kvantumos és klasszikus algoritmus között nem exponenciális, hanem gyökös (a klasszikus nagyságrendű időbonyolultság helyett nagyságrendileg kvantumalgoritmus lépés szükséges). Ha adatbázis algoritmusként gondolunk a Grover algoritmusra, ami rendezetlen adathalmazban keres (egy olyan értékű függvény alapján, ami pl. csak egy helyen veszi fel az értéket, mindenhol máshol 0 értékű, vagyis tulajdonképpen egy olyan egyargumentumú predikátum, ami az adatbázisnak pontosan egy elemére teljesül), akkor minél nagyobb az adatbázis annál kézenfekvőbb az előnye a hagyományos algoritmusokkal szemben. Például, ha van egy adatbázisunk 315 000 000 (315 millió, vagyis majdnem egyharmad milliárd) adattal – ez a szám nagyjából megegyezik az USA 2012-beli népességszámával –, akkor a Grover algoritmussal a teljes adatbázisban, bármely lekérdezésre nem több, mint 18 000 kereséssel kapunk választ.

Az algoritmusnak 1999-ben elkészült egy olyan implementációja, ami optikai kapukat használ.