next up previous contents
Next: Stavový vektor a jeho Up: Jak přežít na pustém Previous: Jak přežít na pustém

Kvantový počítač

neexistuje. Jedná se o teoretickou konstrukci, která spatřila světlo světa na počátku 80. let a jejíž praktická realizace naráží na problémy tak obtížné, že se je hned tak překonat nepodaří. Však také dlouho nebudila nijak zvláštní pozornost. Bomba vybuchla až roku 1994. Tehdy se Peteru Shorovi podařilo vymyslet kvantový algoritmus pro faktorizaci prvočísel, který má polynomiální časovou složitost. Tato úloha je na klasických počítačích řešitelná pouze exponenciálně a její praktická neřešitelnost je základem mnohých moderních kryptografických metod - například kódování čísla kreditní karty při bankovních operacích. Shorovým objevem se kvantové počítače ocitly ve středu zájmu. My zde tento algoritmus rozebírat nebudeme (viz např [1, 2, 5]), místo toho se podíváme na o něco jednodušší aplikaci -- tzv. Groverův algoritmus. Lov K. Grover koncem roku 1996 přišel na způsob, jak vyhledávat v nesetříděné databázi se složitostí tex2html_wrap_inline1235 , tedy také rychleji, než libovolným klasickým algoritmem. Než se pustíme do jeho výkladu, uvedeme nejprve základní poznatky kvantové teorie, které budeme potřebovat.


(Poznamka LUMO: Klasicke hledani spociva v ptani se - je tohle ona? Je tohle ona? Je tohle ona? Na to potrebujeme v prumeru (N+1)/2 otazek, pokud neuspesne vyrazujeme, pripadne v prumeru N otazek, pokud pamet nemame a vyzkousene polozky vracime - pravdepodobnost, ze danou polozku nenajdeme, exponencialne klesa.)



Luboš Motl pro redakci OŽR
Sat Mar 21 17:54:51 EST 1998