Student World

Co jsou to vlastně kvantová počítače? Při pokusu o srozumitelný výklad ihned narazíme na velký kámen úrazu: jakou roli má v našem popisu hrát matematika?
Jen málo popularizátorů "nové" fyziky (teorie relativity a kvantová fyzika) je nadáno takovým talentem, který jim umožní podat výklad bez složitých doprovodných rovnic. Vhodným příkladem je Hawkingova Stručná historie času, mimochodem jedna z celosvětově nejprodávanějších knih posledního desetiletí. Tento článek by měl být pochopitelný i bez matematického doprovodu, několik zde zmíněných základních pojmů slouží spíše k pochopení typů příkladů, v nichž by použití kvantových počítačů představovalo výhodu oproti těm klasickým.
Pokud řešíte nějaký problém, ať už jde o formalizovaný matematický příklad nebo třeba o šachovou úlohu, máte v zásadě dvě možnosti: buď se snažíte postupovat analyticky/logicky, nebo prostřednictvím metody hrubé síly (brute force). Hrubá síla znamená, že z množiny možností vybíráte vlastně náhodným způsobem jednu po druhé, kontrolujete, zda vyhovuje podmínkám řešení, a v případě neúspěchu přejdete k dalšímu řešení. Obě možnosti lze v praxi samozřejmě různě kombinovat.
V případě řady úloh není žádný "inteligentní" algoritmus pro jejich řešení znám (buď jsme ho ještě neobjevili, nebo nemůže existovat principiálně) a musíme tedy postupovat výčtem prvků. Z našeho hlediska je v tuto chvíli klíčová především rychlost řešení, tedy to, aby výpočet vůbec stihl doběhnout ke svému konci v reálném čase.
Pojďme dále. Máte např. najít nejkratší cestu mezi několika body (a musíte navštívit každý z nich právě jednou – jedná se o tzv. Problém obchodního cestujícího, kterým jsme se podrobněji zabývali v článku o DNA počítačích), nebo vyřešit šifru s klíčem o určité bitové délce. Přichází důležitá otázka: Pokud zdvojnásobíte počet bodů v grafu nebo délku šifrovacího klíče, co se stane s časem potřebným k řešení problému? Zdvojnásobí se? Tak jednoduché to samozřejmě není a např. šifrování je založeno právě na skutečnosti, že s růstem složitosti roste čas potřebný k řešení prakticky nade všechny meze.
Jaká je matematická závislost mezi složitostí úlohy a časem potřebným k jejímu řešení? V zásadě rozlišujeme úlohy polynomiální a nepolynomiální. Jestliže čas potřebný k řešení úlohy roste např. jako kubická funkce (y = ax^3 + bx^2 + cx + d), můžeme růst složitost alespoň teoreticky kompenzovat tím, že k řešení použijeme vždy větší počítač (objem, respektive výpočetní výkon poroste tedy řekněme také s mocninou třetího stupně).
Čas potřebný k řešení nepolynomiálních problémů však s růstem složitosti roste exponenciálně (y=a^x) a zde je každá rada drahá. V této souvislosti je dobré si uvědomit, že exponenciální závislost je řádově vyšší než polynomiální. Z úvodu do vysokoškolské matematiky si sice možná vzpomenete na Taylorův rozvoj, kterým se libovolná funkce převáděla na polynom — tam šlo ale o převod závislosti v okolí jednoho bodu, nikoliv po celé délce funkce.
Právě v souvislosti s nepolynomiálními problémy naleznou uplatnění kvantové počítače. Kvantový počítač se v jednom okamžiku může současně nacházet v 2^n stavech, kde n je počet základních stavebních jednotek systému — qbitů. S růstem jednotek roste tedy výkonnost kvantového počítače opět exponenciálně, a tím jaksi "vyrovnává" růst NP problémů. Kvantový počítač tedy "snižuje úroveň složitosti výpočtu".
O kolik? Nutno přiznat, že v tom není zcela jasno. Algoritmus navržený pro luštění v některých případech nepřevede exponenciální závislost na polynomiální, ale "schová" ji pod odmocninu (y = sqr (a^x)). O určitých nejasnostech v tomto ohledu svědčí např. článek ve vědecké sekci Neviditelného psa (http://pes.internet.cz/clanky/9794_0_0_0.html) a zejména následující diskuse.
Jiným příkladem je tzv. Groverův algoritmus, což je způsob, jakým se prohledává netříděná databáze. Postupujeme prostě tak, že každou položku zkoušíme. Pokud můžeme neúspěšné pokusy z databáze vyřadit, pak k řešení dojdeme v průměru po (n+1)/2 otázkách. Díky kvantovému algoritmu, se kterým přišel v roce 1996 L. K. Grover, však k nalezení řešení potřebujeme v průměru pouze sqr(n) pokusů — kvantový algoritmus nám tedy složitost výpočtu opět snížil přidáním odmocniny. Podrobnosti hledejte např. na http://www.kolej.mff.cuni.cz/~lmotm275/RUZE/19/node18.html.

autor Pavel Houser