Introduction
Kvantové algoritmy nabízejí prokazatelné výhody oproti klasickým algoritmům v dotazovacím modelu výpočtu. Ale co standardnější model výpočtu, kde jsou vstupy problému zadány explicitně, nikoliv ve formě orákula nebo černé skříňky? To se ukáže jako mnohem složitější otázka k zodpovězení a abychom ji mohli řešit, musíme nejprve vybudovat pevný základ, na kterém budeme stavět naše zkoumání. To je hlavní účel této lekce.
Začneme diskuzí o výpočetních nákladech, jak pro klasické, tak pro kvantové výpočty, a o tom, jak je lze měřit. Jedná se o obecn ý pojem, který lze aplikovat na širokou škálu výpočetních problémů — ale pro jednoduchost jej budeme zkoumat především optikou výpočetní teorie čísel, která se zabývá výpočetními úlohami, jež budou většině čtenářů pravděpodobně známé, včetně základní aritmetiky, výpočtu největšího společného dělitele a faktorizace celých čísel. I když je výpočetní teorie čísel úzkou aplikační doménou, tyto problémy dobře ilustrují základní otázky (a navíc jsou vysoce relevantní pro lekci následující po této).
Zaměřujeme se na algoritmy, nikoliv na neustále se zlepšující hardware, na kterém běží. V souladu s tím nás bude více zajímat, jak se náklady na běh algoritmu škálují s rostoucí velikostí konkrétních instancí problémů, než kolik sekund, minut nebo hodin vyžaduje nějaký konkrétní výpočet. Na tento aspekt výpočetních nákladů se zaměřujeme s vědomím, že algoritmy mají zásadní důležitost a budou přirozeně nasazovány na stále větší instance problémů pomocí rychlejšího a spolehlivějšího hardwaru, jak se technologie vyvíjí.
Na závěr se obrátíme ke kriticky důležité úloze, kterou je provádění klasických výpočtů na kvantových počítačích. Důvod, proč je tato úloha důležitá, není ten, že bychom doufali v nahrazení klasických počítačů kvantovými — což se zdá být extrémně nepravděpodobné v dohledné době, pokud vůbec — ale spíše proto, že to otevírá mnoho zajímavých možností pro kvantové algoritmy. Konkrétně se klasické výpočty běžící na kvantových počítačích stávají dostupnými jako podprogramy, čímž efektivně využívají desetiletí výzkumu a vývoje klasických algoritmů při hledání kvantových výpočetních výhod.
Video k lekci
V následujícím videu tě John Watrous provede obsahem této lekce o kvantových algoritmických základech. Případně si můžeš otevřít video na YouTube v samostatném okně. Stáhni si slajdy k této lekci.