Introduction

Groverův algoritmus je kvantový algoritmus pro takzvané problémy nestrukturovaného vyhledávání, který nabízí kvadratické zlepšení oproti klasickým algoritmům. To znamená, že Groverův algoritmus vyžaduje počet operací řádově odpovídající odmocnině z počtu operací potřebných k vyřešení nestrukturovaného vyhledávání klasicky — což je ekvivalentní tvrzení, že klasické algoritmy pro nestrukturované vyhledávání musí mít náklady přinejmenším řádově odpovídající druhé mocnině nákladů Groverova algoritmu.

Groverův algoritmus spolu se svými rozšířeními a základní metodologií se ukazují jako široce aplikovatelné, vedoucí ke kvadratické výhodě pro mnoho zajímavých výpočetních úloh, které na první pohled nemusí vypadat jako problémy nestrukturovaného vyhledávání.

I když je široká aplikovatelnost Groverovy vyhledávací techniky přesvědčivá, je třeba zde na začátku lekce přiznat, že kvadratická výhoda, kterou nabízí, pravděpodobně nepovede k praktické výhodě kvantových počítačů oproti klasickým v dohledné době. Hardware klasických počítačů je mnohem pokročilejší než hardware kvantových počítačů — a kvadratická výhoda kvantových počítačů oproti klasickým, kterou nabízí Groverův algoritmus, bude jistě zastíněna ohromujícími taktovacími frekvencemi moderních klasických počítačů pro jakýkoli problém nestrukturovaného vyhledávání, který by bylo možné v dohledné době reálně spustit.

S pokrokem kvantových výpočetních technologií však Groverův algoritmus může mít potenciál. Některé z nejdůležitějších a nejvlivnějších klasických algoritmů, které byly kdy objeveny, včetně rychlé Fourierovy transformace a rychlého řazení (například quicksort a merge sort), nabízejí o něco méně než kvadratickou výhodu oproti naivním přístupům k problémům, které řeší. Klíčový rozdíl zde samozřejmě spočívá v tom, že k běhu Groverova algoritmu je zapotřebí zcela nová technologie (tedy kvantové počítače). I když je tato technologie stále velmi na počátku ve srovnání s klasickými počítači, neměli bychom být tak rychlí v podceňování potenciálu technologických pokroků, které by mohly umožnit, aby kvadratická výhoda kvantových počítačů oproti klasickým jednoho dne přinesla hmatatelné praktické přínosy.

Video k lekci

V následujícím videu tě John Watrous provede obsahem této lekce o Groverově algoritmu. Případně si můžeš otevřít video na YouTube v samostatném okně. Stáhni si slajdy k této lekci.