náhled|300px|Náčrt obvodu, na kterém je implementován Deutschův-Jozsův algoritmus Deutschův-Jozsův algoritmus je kvantový algoritmus, na kterém bylo poprvé ukázáno urychlení výpočtu oproti klasickému algoritmu. Tento algoritmus se zabývá globálními vlastnostmi logických funkcí. Při praktických použitích je používán jen zřídka. Algoritmus slouží zejména pro ukázání konceptu kvantových počítačů jako výpočetně silnějších strojů.
Jeho speciálním a zjednodušeným případem je Deutschův algoritmus, který popisuje situaci pro funkci, jejíž vstup tvoří jediný bit.
Algoritmus využívá kvantovou Fourierovu transformaci (KFT) pro získání informace o globálním chování zadané klasické funkce . V klasickém algoritmu by bylo třeba vyhodnocovat funkci na mnoha různých hodnotách, ale Deutschův-Jozsův algoritmus je schopný rozhodnout s pouze jediným vyhodnocením . Prvotní algoritmus, který byl představen fyzikem Davidem Deutschem, byl konstruován pro pouze jednobitovou funkci a fungoval jen pravděpodobnostně a ne deterministicky. Následně byl algoritmus zobecněn v článku, který Deutsch sepsal spolu s matematikem Richardem Jozsou. Po těchto objevitelích dnes algoritmus nese své jméno.Nielsen, str. 59
Původní Deutschův-Jozsův algoritmus pracoval s dvojnásobným vyhodnocením neznámé funkce . Následně byl vylepšen do dnešní zkrácené podoby, kde je třeba pouze jediné volání . Právě tato novější verze algoritmu je popsána v tomto článku.
Deutschova úloha Mějme logickou funkci , která má bitů na vstupu a 1 bit na výstupu . Tato funkce může být buď konstantní nebo vyvážená. Konstantní funkce je taková, která dává pro všechny možné vstupy stejnou hodnotu (buď 0 nebo 1). O funkci řekneme, že je vyvážená, pokud pro právě polovinu všech možných vstupů dává výsledek 0 a pro druhou polovinu výsledek 1. O této zadané funkci nemáme žádnou další informaci. Je možno sledovat pouze výsledek funkce pro různé vstupy. Úloha, kterou Deutschův–Jozsův algoritmus řeší, je následující: rozhodnout, zda je zadaná neznámá funkce konstantní nebo vyvážená. Tento problém se nazývá Deutschova úloha.
Konstrukce algoritmu Pro rozhodnutí, zda je neznámá n-bitová funkce konstantní nebo vyvážená se zde použije celkem n+1 qbitů. Mějme připravené 2 registry (řady qbitů). První registr má celkem n qbitů a druhý má jeden qbit. V prvním registru jsou na začátku všechny qbity ve stavu a v druhém registru je stav . Popsaný stav se značí následovně :.
Smíšení stavů Celková stavba logiky v algoritmu je následující: všechny qbity převedeme do smíšených stavů pomocí Hadamardových hradel, aplikujeme funkci na přidaný qbit a podruhé aplikujeme Hadamardova hradla. Interference mezi stavy pak zajistí, že při změření registru je možno získat jednoznačnou informaci o .
Za prvé se na všechny připravené qbity se zapůsobí Hadamardovým hradlem, čímž stav se přemění na , kde sumace probíhá přes všechny možné kombinace jedniček a nul v uspořádané n-tici nazvané (v součtu tak figuruje celkem členů). Následně se na stav aplikuje hodnota neznámé funkce . To provedeme pomocí unitární transformace . Operace tu značí sčítání modulo 2. Získaný stav tak je . Způsob, jakým tohoto stavu dosáhneme není důležitý, hlavní je, že se jedná o změnu hodnoty pouze v jednom qbitu bez ohledu na počet n-argumentů funkce . Tento krok tak probíhá se stejnou složitostí pro libovolnou . Stav lze zjednodušit do tvaru .
Nadále bude třeba uvažovat pouze prvních n qbitů a poslední qbit tak nebude uváděn. Na n qbitů jsou v posledním kroku opět aplikována Hadamardova hradla, což stav přemění na .
Měření výsledku Následně se všech n-qbitů v libovolném pořadí změří. Pravděpodobnost , že měřením získáme výsledek je rovna . Pravděpodobnost vychází 1, pokud je neznámá funkce konstantní, nebo 0, pokud je funkce vyvážená. Na základě měření tak je možno s určitostí rozhodnout o tom, zda je konstantní nebo vyvážená.
Náročnost Časová složitost na vyřešení problému na klasickém počítači je , protože aby bylo možno definitivně rozhodnout o vyváženosti funkce , je třeba její hodnotu zjistit na alespoň polovině všech možných hodnot vstupu. Pro n bitů to dělá různých hodnot vstupu. Pokud jsou všechny spočtené výsledky stejné, pak je konstantní, jinak musí být vyvážená.
Deutschův–Jozsův algoritmus je schopný úlohu vyřešit v konstantním čase . Délka jeho běhu tak nezávisí na počtu qbitů, které tvoří vstup funkce . Je to tak díky tomu, že aplikace Hadamardových hradel může probíhat pro všechny zúčastněné qbity naráz a tedy v konstantním čase bez ohledu na počet qbitů. Co se týče náročnosti na celkový počet logických operací, chová se lineárně .
Jedná se tedy jak pro čas, tak i pro počet operací o exponenciální urychlení proti jakémukoliv klasickému algoritmu. Toto exponenciální urychlení je ale platné, pouze pokud uvažujeme klasické deterministické algoritmy. Pro pravděpodobnostní klasické algoritmy je náročnost na počet operací opět konstantní , protože stačí zkontrolovat prvních hodnot (pro konstantní hodnotu ), pak je pravděpodobnost mylného určení funkce rovna , což může být podle volby libovolně malé číslo.
Využití Tento kvantový algoritmus řeší poměrně abstraktní problém, který v praxi nalézá jen minimální uplatnění. Zároveň však využívá velmi rozšířených technik v kvantové informatice, jako je interference, provázání stavů i KFT. Díky tomu slouží zejména didaktickým účelům v úvodních kurzech do kvantových počítačů. Ve své době sloužil zejména jako argument pro samotné studium kvantových počítačů, protože se jednalo o první příklad výrazné výkonnostní výhody kvantového počítače nad klasickým.
Odkazy
Poznámky
Reference
Literatura
Související články Kvantová Fourierova transformace
Kategorie:Kvantové algoritmy