Kvantové algoritmy

Problémem je univerzálnost V průběhu loňského roku vyšla na stránkách CW řada testů týkajících se problematiky ...


Problémem je univerzálnost
V průběhu loňského roku vyšla na stránkách CW řada testů týkajících se
problematiky kvantových počítačů. Následující materiál si klade za cíl shrnout
pokrok dosažený na tomto poli a to formou pokud možno populární.
Původní inspirací k napsání tohoto textu byla četba knihy George Johnsona
"Zkratka napříč časem cesta ke kvantovému počítači" (pod jménem "A Shortcut
Through Time: The Path to the Quantum Computer" lze dohledat např. na
Amazon.com). Johnson se pokusil vyložit srozumitelně téma, které se takové
snaze na první pohled naprosto vzpírá. Co tedy můžeme říci o kvantových
počítačích bez toho, abychom se museli ponořit do podivného světa kvantové
fyziky?
První a snad užitečné zjednodušení ukazuje už nadpis tohoto článku řeč bude o
kvantových algoritmech, nikoliv o vlastních kvantových počítačích. Hardwarovou
realizaci si pro naše potřeby můžeme představit třeba jako černou skřínku máme
prostě systém částic, s nimiž provádíme určité operace (třeba různé atomy
systému ozařujeme v určitém pořadí laserovým paprskem), systém se nějak mění a
tyto změny reprezentují postup výpočtu.

Nejen hardware
Jako hlavní námitka proti prakticky použitelným kvantovým počítačům se většinou
uvádí problém s jejich hardwarovou realizací do příslušného systému dokážeme
propojit jenom málo částic, před dokončením výpočtu se náš "počítač" navíc
nejspíš rozsype. Není ale pravda, že tyto řekněme fyzikální problémy
představují jedinou překážku. Ani fungující černá skřínka, dostatečně velká a s
dostatečně dlouhou životností, totiž není všelékem.
K čemu v tuto chvíli můžeme a k čemu nemůžeme využít kvantové algoritmy?
Obvykle se jako příklad jejich síly uvádí lámání šifer problém je však v tom,
že dalších příkladů už zase tolik není.
Současné kvantové algoritmy se nevyznačují žádnou univerzálností a je jich ve
skutečnosti známo velmi málo (tedy alespoň takových algoritmů, které oproti
algoritmům klasickým přinášejí snížení výpočetní složitosti). Do skupiny
rychlých kvantových algoritmů patří:
Modelování kvantového chaosu, respektive obecněji kvantových systémů. Je vcelku
pochopitelné, že kvantové algoritmy vycházející z podivné struktury mikrosvěta
se budou moci zpětně uplatnit právě při popisu této struktury. Tyto algoritmy
jsou však zajímavé nejspíš pouze pro kvantové fyziky.
Faktorizace. Příslušná operace (rozklad složeného čísla na dvě prvočísla,
postup, který hraje klíčovou úlohu v asymetrické kryptografii) se na kvantovém
počítači provádí pomocí tzv. Shorova algoritmu. Postup byl objeven v roce 1994
a právě na něm se možnosti kvantových počítačů nejčastěji demonstrují.
Vyhledávání v neseřazených databázích tento postup je znám jako tzv. algoritmus
Groverův. Úlohou je zde míněn např. problém nalézt v abecedně setříděném
telefonním seznamu určité číslo. Protože tato čísla jsou distribuována náhodně
(nezávisle na abecedním pořadí jména), klasický algoritmus bude muset v průměru
prověřit polovinu položek seznamu. Groverův algoritmus potřebuje provést počet
kroků odpovídající pouze odmocnině z počtu položek.
Problém rozeznávání obrazů (podrobněji viz CW 39/2003).
Samozřejmě existují i další informatické aplikace využívající zákonů kvantové
fyziky třeba systémy pro kvantovou kryptografii nebo pro generování skutečně
náhodných čísel. To snad ale kvantové počítače/algoritmy ani v pravém slova
smyslu nejsou.

Převody problémů
V principu není nemožné konstruovat kvantový algoritmus pro řešení libovolné
úlohy, problém však spočívá v tom, zda tím dosáhneme nějakého urychlení oproti
algoritmům klasickým. Tuto obtíž jsme si demonstrovali v CW 31/2003 v článku,
který popisoval, jak kvantový počítač určí procentuální zastoupení lichých/
sudých čísel v zadaném souboru. Výpočetní náročnost kvantového algoritmu je v
tomto případě stejná jako u standardního postupu.
Dosavadní text by snadno mohl vzbudit značnou skepsi k výsledkům kvantového
počítání. I když pomineme hardwarovou realizaci, efektivních algoritmů je dnes
známo jen pár a není jasné, jak vytvářet ty další nedá se to dělat bez
podrobných znalostí chování kvantového mikrosvěta. Platí tedy, že kromě
faktorizace a hledání v seznamech by i dostatečně robustní kvantové počítače
byly k ničemu?
Přece jen existují i důvody k opatrnému optimismu. Jednotlivé problémy
(respektive jejich matematický popis) mezi sebou bývají převoditelné. Kdo
sledoval třeba historii řešení slavné Velké Fermatovy věty, ví, že problém
připomínající na první pohled Pythagorovu větu byl nakonec odhalen pomocí na
první pohled tak vzdálené matematické disciplíny, jakou představovaly eliptické
křivky.
Ani známá Shorova faktorizace ve skutečnosti vůbec nepracuje s hledáním
dělitelů, ale úloha je převedena na řešení ekvivalentního problému v rámci tzv.
hodinové/modulové aritmetiky (kdy se čísla namísto za sebe na osu řadí do
kruhu). To, co ve skutečnosti zkoumá kvantový systém, jsou pak nikoliv
prvočísla, ale frekvence zastoupení jednotlivých čísel v těchto "matematických
strojcích".
Tato skutečnost ukazuje, že nemusíme pouze konstruovat nové kvantové algoritmy,
ale můžeme také převádět zcela klasickým způsobem úlohy na jejich ekvivalenty,
pro které už bude nějaký algoritmus znám.

Faktorizace a NP
Zajímavá situace panuje v případě tzv. NP úplných úloh. U těchto problémů není
známo klasické řešení, jehož složitost by s růstem úlohy stoupala polynomiálně.
Co je klíčové, u NP úplných úloh je dokázána nejen jejich vzájemná ekvivalence,
ale i mechanismus, kterými jsou na sebe převoditelné. Pokud bychom tedy našli
(polynomiálně složitý) kvantový algoritmus pro jediný z této skupiny problémů,
vyřešili bychom je de facto jako celek. K NP úplným úlohám patří např. hledání
pravdivostní hodnoty logické formule, problém obchodního cestujícího, dláždění
konečné roviny či barvení 2D mapy třemi barvami.
Jak to všechno souvisí s faktorizací? Bohužel zatím pouze nepřímo. U
faktorizace se totiž nepodařilo dokázat, že patří mezi NP úplné problémy (byť
se s takovým tvrzením lze v populárních článcích o možnostech kvantových
počítačů lze často setkat není to ale pravda). Je tedy stále možné, že bude
nalezen i naprosto klasický algoritmus pro řešení rozkladu na prvočísla v
polynomiálním čase. Shorova metoda nám pro řešení dalších NP úplných úloh typu
prozatím nijak nepomůže.
Složitá konstrukce kvantových algoritmů nás ale každopádně když nic jiného může
motivovat k hlubšímu pochopení vztahů, které existují mezi algoritmy klasickými.

Kvantový buněčný automat
Klasický Turingův stroj funguje tak, že přečte symbol napsaný na pásce, na
základě jeho hodnoty provede určitou operaci a čtecí/zapisovací hlava se posune
o políčko dále. Kvantové počítače samozřejmě nemohou fungovat podobně
"sekvenčně" jejich podstatou je superpozice a propletenost zúčastněných částic-
políček pásky, které se často opisují jako existence ve více hodnotách
najednou. Při pokusu o čtení by kvantový bit zkolaboval k jedné z možných
hodnot do klasického stavu a celý efekt by se vytratil.
George Johnson v knize "Zkratka napříč časem cesta ke kvantovému počítači" (viz
také hlavní text) proto doporučuje představit si mechanismus kvantového
počítače spíše jako buněčný (celulární) automat. Zatímco v klasickém buněčném
automatu může určité políčko v určitém čase zaujímat pouze jednu hodnotu
(nejčastěji ze 2 možností), políčko kvantového buněčného automatu může
existovat také v superpozici. Operace na kvantovém buněčném automatu složeném
např. z jednotlivých atomů můžeme provádět prostřednictvím laserového paprsku,
který bude převracet hodnoty určité veličiny (např. spinu) "zasaženého" atomu
stejně jako v případě klasického automatu bude ovšem přitom výsledek záviset na
stavu sousedních buněk. Kombinací zásahů laserového paprsku a pravidel
interakce mezi sousedními buňkami bude realizován vlastní algoritmus. Důležité
přitom je, že laserový paprsek na rozdíl od hlavy Turingova stroje v pravém
slova smyslu nic "nečte", a kvantový buněčný automat proto následkem provádění
výpočtu nezkolabuje do klasického stavu.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.