Kvantový Turingův stroj

Hlavním impulzem pro vznik kvantového Turingova stroje (KTS), bylo v roce 1973 potvrzení Charlese Bennetta, který dokázal jeho reverzibilitu⁵. To nezůstalo bez povšimnutí Paulem Benioffem, kterého napadlo, že by šlo napodobit vývoj reverzibilního kvantového systému na Turingově stroji. Na práce Benioffa a později i Richarda Feynmana navázal prvním popisem opravdového KTS v roce 1985 David Deutsch. Kvantová verze měla tyto hlavní charakteristiky a odlišnosti od klasického stroje:

• čtení, zápis a posun pásky se odehrával pomocí kvantově-mechanických interakcí.
• místo čisté 0, 1 a mezery se nyní setkáváme v každé buňce pásky se superpozicí stavů 0 a 1, což si můžeme představit jako vektor v jednotkové kouli; odklon od svislé osy zde určuje podíl zastoupení 0 a 1.
• superpozice zde umožňuje využít kvantový paralelismus - možnost provádět jednu operaci nad více daty současně.

Nejlépe si lze KTS představit jako kvantové zobecnění PTS. Pokud necháme po určitou dobu takový KTS vyvíjet (nebudeme jej měřit), můžeme stav vyjádřit jako součet pravděpodobností výpočetních cest, kterými může stroj projít. U KTS se v jednom kroku nebere pouze jedna náhodně zvolená cesta (jeden následující stav, jako je tomu u PTS), ale výpočet pokračuje v duchu kvantového paralelismu všemi možnými cestami naráz. Se vznikem KTS bylo možné zaměřit úsilí na otázky vypočitatelnosti, složitosti a univerzálnosti kvantových počítačů. Vypočitatelnost je spojena s otázkou, zda je možné o daném problému rozhodnout (nebo nalézt k němu řešení) v konečném čase. Pokud algoritmus, terý by těmto požadavkům vyhověl, neexistuje, nazývá se problém nevypočitatelný. Hledání algoritmu k řešení problému vede i k tomu, že například pro generování náhodného čísla žádný klasický algoritmus neexistuje (není možné vygenerovat opravdu náhodné číslo, protože všechny klasické generátory musí být založeny na výpočtu vstupů dle daného předpisu), kdežto u kvantových počítačů takový algoritmus existuje. Vychází totiž ze základní vlastnosti přírody - okamžiku náhodného kolapsu vlnové funkce na vlastní stav při měření kvantového systému. Více se měřením kvantového systému a generováním náhodných číslech budeme zabývat v kapitole o kvantových algoritmech. Složitost neboli komplexita je druhou vlastností, která nás u kvantových počítačů zajímá. Souvisí s ní efektivita kvantových algoritmů a následně i výkon kvantových počítačů. Aby se dokázalo, že výzkum kvantových počítačů může mít v budoucnosti i praktický dopad, začala se během 90.let vynořovat řada možných aplikací, které využívají superpozice kvantových systémů k uplatnění kvantového paralelismu a tím i vylepšení složitostí dosavadních algoritmů. Jako příklad uveďme známý problém s faktorizací velkých celých čísel na součin prvočísel. Nejlepší známý klasický algoritmus dosahuje exponenciální složitosti, kterou lze (pro obecnou metodu Number Field Sieve) vyjádřit jako: ${\cal O}(e^{(L^\frac{1}{3}\ \mathrm{ln}^\frac{2}{3}L)})$, kde $L = {\rm ln}\ n$ a $n$ je celé číslo, jehož rozklad hledáme. Vidíme, že časová náročnost roste velmi rychle s velikostí vstupu. Tento problém je ze skupiny NP problémů (nondeterministic polynomial), u nichž existuje efektivní nedeterministický algoritmus, jehož řešení v polynomiálním čase ověřit lze. Řešení takového problému deterministickým algoritmem není kvůli počtu výpočetních kroků schůdné (tractable). Nicméně u faktorizačního problému se zatím nepodařilo dokázat, že nemá efektivní algoritmus běžící v třídě složitosti P, tj. v polynomiálním čase, a proto je možné (i když se mnozí domnívají, že nepravděpodobné), že bude takový algoritmus ještě objeven. V roce 1994 se Peteru Shorovi z AT&T Bell Labs podařilo vymyslet kvantový faktorizační algoritmus, jehož složitost je na kvantovém počítači polynomiální. Takové řádové vylepšení znamenalo průlom ve vývoji kvantových algoritmů. Podobně jako se dají roztřídit algoritmy u klasické a pravděpodobnostní verze Turingových strojů, lze definovat i kvantové složitostní třídy. Pro přehlednost byly všechny třídy seřazeny do následující tabulky:

Třída	Popis
P	schůdné algoritmy běžící nejhůře v polynomiálním čase (dále jen PT), příklad: násobení
NP	neschůdné algoritmy; pouze správnost řešení lze ověřit v PT, příklad: faktorizace
NP-úplný	NP problémy vzájemně mapovatelné v PT, příklady: SAT, obchodní cestující, plánování
ZPP	problémy řešitelné s jistotou v průměrně PT na PTS
BPP	problémy řešitelné s $p > 2/3$ v nejhůře PT na PTS
QP	problémy řešitelné s jistotou v nejhůře PT
ZQP	problémy řešitelné s jistotou v průměrném PT
BQP	problémy řešitelné s $p > 2/3$ v nejhůře PT

Tabulka: Třídy složitosti: první tři klasické, druhé dvě pravděpodobnostní, poslední tři kvantové. SAT je problém splnitelnosti (satisfiability) logické funkce boolovských proměnných.

Univerzálnost je schopnost efektivně simulovat jeden Turingův stroj druhým. Turinga napadlo, že když vytvoří transformační pravidla jednoho Turingova stroje jako program (posloupnost bitů) pro jiný stroj, bude tento stroj schopný simulovat první stroj. Tak vznikla myšlenka, že je možné vytvořit programovatelný počítač - Turingův stroj, jehož programem je nějaký algoritmus. Až v roce 1996 potvrdili Seth Lloyd a Christof Zalka, že univerzálnost platí také u kvantových počítačů. To znamená, že jeden kvantový systém dokáže simulovat jiný.