Měření výpočetní náročnosti

Dále se budeme zabývat matematickým rámcem, pomocí kterého lze měřit výpočetní náklady, úzce zaměřeným na potřeby tohoto kurzu. Analýza algoritmů a výpočetní složitost jsou samostatné obory, které mají k těmto pojmům mnohem více co říct.

Jako výchozí bod si vezmi následující obrázek z předchozí lekce, který představuje velmi vysokou úroveň abstrakce výpočtu.

Samotný výpočet může být modelován nebo popsán různými způsoby, například počítačovým programem napsaným v Pythonu, Turingovým strojem, booleovským obvodem nebo kvantovým Circuit. Naše pozornost bude zaměřena na obvody (jak booleovské, tak kvantové).

Kódování a délka vstupu

Začněme vstupem a výstupem výpočetního problému, o kterých budeme předpokládat, že jsou binární řetězce. Mohli bychom použít různé symboly, ale pro účely této diskuse si věci zjednodušíme tím, že se omezíme na binární řetězcové vstupy a výstupy. Pomocí binárních řetězců můžeme zakódovat celou řadu zajímavých objektů, kterých se mohou týkat problémy, jež chceme řešit, jako jsou čísla, vektory, matice a grafy, stejně jako seznamy těchto a dalších objektů.

Například pro kódování nezáporných celých čísel můžeme použít binární zápis. Následující tabulka uvádí binární kódování prvních devíti nezáporných celých čísel spolu s délkou (tj. celkovým počtem bitů) každého kódování.

Číslo	Binární kódování	Délka
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

Toto kódování můžeme snadno rozšířit tak, aby zvládlo jak kladná, tak záporná celá čísla, přidáním znaménkového bitu k reprezentacím. Někdy je také vhodné umožnit binárním reprezentacím nezáporných celých čísel mít úvodní nuly, které nemění zakódovanou hodnotu, ale mohou umožnit reprezentacím vyplnit řetězec nebo slovo pevné velikosti.

Použití binárního zápisu pro reprezentaci nezáporných celých čísel je běžné i efektivní, ale kdybychom chtěli, mohli bychom zvolit jiný způsob reprezentace nezáporných celých čísel pomocí binárních řetězců, jako jsou ty naznačené v následující tabulce. Konkrétní detaily těchto alternativ nejsou pro tuto diskusi důležité — jde pouze o upřesnění, že pro kódování máme na výběr.

Číslo	Unární kódování	Lexikografické kódování
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(V této tabulce symbol $\varepsilon$ představuje prázdný řetězec, který neobsahuje žádné symboly a má délku rovnou nule. Abychom se vyhnuli zjevnému zdroji zmatku, používáme pro reprezentaci prázdného řetězce speciální symbol jako $\varepsilon$, místo abychom doslova nepsali nic.)

Další typy vstupů, jako vektory a matice, nebo složitější objekty jako popisy molekul, lze také zakódovat jako binární řetězce. Stejně jako u nezáporných celých čísel lze zvolit nebo vymyslet celou řadu různých kódovacích schémat. Ať už přijdeme s jakýmkoli schématem pro kódování vstupů daného problému, délku vstupního řetězce interpretujeme jako velikost řešené instance problému.

Například počet bitů potřebných k vyjádření nezáporného celého čísla $N$ v binárním zápisu, který se někdy označuje $\operatorname{lg}(N),$ je dán následujícím vzorcem.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

Za předpokladu, že používáme binární zápis pro kódování vstupu problému faktorizace celých čísel, je délka vstupu pro číslo $N$ tedy $\operatorname{lg}(N).$ Všimni si zejména, že délka (nebo velikost) vstupu $N$ není samotné $N$; když je $N$ velké, nepotřebujeme zdaleka tolik bitů k vyjádření $N$ v binárním zápisu.

Ze striktně formálního hlediska, kdykoli uvažujeme výpočetní problém nebo úlohu, mělo by být zřejmé, že bylo zvoleno konkrétní schéma pro kódování jakýchkoli objektů zadaných jako vstup nebo produkovaných jako výstup. To umožňuje nahlížet na výpočty řešící zajímavé problémy abstraktně jako na transformace z binárních řetězcových vstupů na binární řetězcové výstupy.

Detaily toho, jak jsou objekty kódovány jako binární řetězce, musí být pro tyto výpočty na určité úrovni nutně důležité. Obvykle se ale při analýze výpočetních nákladů těmito detaily příliš nezabýváme, abychom se vyhnuli zacházení do podrobností druhořadého významu. Základní úvaha je, že očekáváme, že výpočetní náklady na převod mezi „rozumnými" kódovacími schématy budou ve srovnání s náklady na řešení samotného problému zanedbatelné. V situacích, kdy tomu tak není, mohou (a měly by) být detaily upřesněny.

Například velmi jednoduchý výpočet převádí mezi binární reprezentací nezáporného celého čísla a jeho lexikografickým kódováním (které jsme podrobně nevysvětlili, ale lze ho odvodit z tabulky výše). Z tohoto důvodu by se výpočetní náklady faktorizace celých čísel výrazně nelišily, kdybychom se rozhodli přejít z jednoho z těchto kódování na druhé pro vstup $N.$ Na druhou stranu kódování nezáporných celých čísel v unárním zápisu způsobuje exponenciální nárůst celkového počtu potřebných symbolů a z tohoto důvodu bychom ho nepovažovali za „rozumné" kódovací schéma.

Elementární operace

Nyní se podívejme na samotný výpočet, který je na obrázku výše znázorněn modrým obdélníkem. Způsob, jakým budeme měřit výpočetní náklady, je počítání elementárních operací, které každý výpočet vyžaduje. Intuitivně řečeno, elementární operace je taková, která zahrnuje malý, pevný počet bitů nebo Qubitů a lze ji provést rychle a snadno — jako je výpočet AND dvou bitů. Naproti tomu spuštění funkce factorint nelze rozumně považovat za elementární operaci.

Formálně řečeno, existují různé volby toho, co představuje elementární operaci, v závislosti na použitém výpočetním modelu. Naše pozornost bude zaměřena na modely obvodů, konkrétně kvantové a booleovské Circuit.

Univerzální sady Gate

Pro modely výpočtů založené na obvodech je typické, že každá Gate je považována za elementární operaci. To vede k otázce, které Gate přesně v našich obvodech povolíme. Zaměříme-li se prozatím na kvantové Circuit, dosud jsme v této sérii viděli několik Gate, včetně $X,$ $Y,$ $Z,$ $H,$ $S,$ a $T$ Gate, swap Gate, kontrolovaných verzí Gate (včetně controlled-NOT, Toffoli a Fredkin Gate), a také Gate reprezentujících měření ve standardní bázi. V kontextu hry CHSH jsme také viděli několik dalších rotačních Gate.

Také jsme diskutovali o query Gate v kontextu modelu dotazů a viděli jsme, že jakoukoli unitární operaci $U,$ působící na libovolný počet Qubitů, lze považovat za Gate, pokud se tak rozhodneme — ale obě tyto možnosti pro účely této diskuse pomineme. Nebudeme pracovat v modelu dotazů (ačkoli implementace query Gate pomocí elementárních operací je diskutována později v lekci) a považování libovolných unitárních Gate, potenciálně působících na miliony Qubitů, za elementární operace nevede ke smysluplným ani realistickým pojmům výpočetních nákladů.

Zůstaneme-li u kvantových Gate operujících na malém počtu Qubitů, jedním přístupem k rozhodnutí, které z nich považovat za elementární, je vymezit přesné kritérium — ale to není standardní přístup ani ten, který zvolíme. Místo toho prostě učiníme volbu.

Zde je jedna standardní volba, kterou přijmeme jako výchozí sadu Gate pro kvantové Circuit:

• Jednoqubitové unitární Gate z tohoto seznamu: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T,$ a $T^{\dagger}$
• Controlled-NOT Gate
• Jednoqubitová měření ve standardní bázi

Běžnou alternativou je považovat Toffoli, Hadamard a $S$ Gate za elementární, společně s měřeními ve standardní bázi. Někdy jsou za elementární považovány všechny jednoqubitové Gate, což ale vede k nerealisticky silnému modelu, pokud není řádně zohledněna přesnost, s jakou jsou Gate prováděny.

Unitární Gate v naší výchozí kolekci tvoří takzvanou univerzální sadu Gate. To znamená, že můžeme aproximovat jakoukoli unitární operaci na libovolném počtu Qubitů s libovolnou přesností, jakou si přejeme, pomocí Circuit složených pouze z těchto Gate. Pro upřesnění, definice univerzality neklade žádné požadavky na náklady takových aproximací, tedy na počet Gate z naší sady, které potřebujeme. Poměrně jednoduchý argument založený na matematickém pojmu míry skutečně odhaluje, že většina unitárních operací musí mít extrémně vysoké náklady. Důkaz univerzality kvantových sad Gate není jednoduchá záležitost a nebude v tomto kurzu pokryt.

Pro booleovské Circuit budeme za Gate reprezentující elementární operace považovat AND, OR, NOT a FANOUT Gate. Ve skutečnosti nepotřebujeme jak AND Gate, tak OR Gate — můžeme použít De Morganovy zákony k převodu z jedné na druhou umístěním NOT Gate na všechny tři vstupní/výstupní vodiče — přesto je běžné a pohodlné povolovat jak AND, tak OR Gate. AND, OR, NOT a FANOUT Gate tvoří univerzální sadu pro deterministické výpočty, což znamená, že jakoukoli funkci z libovolného pevného počtu vstupních bitů na libovolný pevný počet výstupních bitů lze implementovat pomocí těchto Gate.

Princip odloženého měření

Gate pro měření ve standardní bázi se mohou objevit uvnitř kvantových Circuit, ale někdy je vhodné je odložit až na konec. To nám umožňuje nahlížet na kvantové výpočty jako na unitární část (reprezentující samotný výpočet), po které následuje jednoduchá fáze čtení, kde jsou Qubity měřeny a výsledky jsou výstupem. To lze vždy provést za předpokladu, že jsme ochotni přidat další Qubit pro každé měření ve standardní bázi. Na následujícím obrázku Circuit vpravo ukazuje, jak to lze provést pro Gate vlevo.

Konkrétně, klasický bit v Circuit vlevo je nahrazen Qubitem vpravo (inicializovaným do stavu $\vert 0\rangle$) a měření ve standardní bázi je nahrazeno controlled-NOT Gate, po které následuje měření ve standardní bázi na spodním Qubitu. Pointa je, že měření ve standardní bázi v pravém obvodu lze posunout až na úplný konec obvodu. Pokud se klasický bit v levém obvodu později použije jako řídicí bit, můžeš místo něj v pravém obvodu použít spodní Qubit jako řídicí a celkový efekt bude stejný. (Předpokládáme, že klasický bit v levém obvodu nebude po měření přepsán jiným měřením — ale pokud by byl, mohli bychom vždy jednoduše použít nový klasický bit místo přepisování toho, který byl použit pro předchozí měření.)

Velikost a hloubka Circuit

Velikost Circuit

Celkový počet Gate v Circuit se označuje jako jeho velikost. Za předpokladu, že Gate v našich Circuit představují elementární operace, velikost Circuit tedy reprezentuje počet elementárních operací, které vyžaduje — jinými slovy, jeho výpočetní náklady. Zapisujeme $\operatorname{size}(C)$ pro velikost daného Circuit $C.$

Například uvažuj následující booleovský Circuit pro výpočet XOR dvou bitů.

Velikost tohoto Circuit je 7, protože obsahuje celkem 7 Gate. (Operace FANOUT se ne vždy počítají jako Gate, ale pro účely této lekce je budeme počítat jako Gate.)

Čas, náklady a hloubka Circuit

Čas je kriticky důležitý zdroj, nebo omezující podmínka, pro výpočty. Výše uvedené příklady, jako je úloha faktorizace RSA1024, tento pohled potvrzují. Funkce factorint neselže při faktorizaci RSA1024 jako takové, jen nemáme dost času, abychom ji nechali doběhnout.

Pojem výpočetních nákladů, jakožto počtu elementárních operací potřebných k provedení výpočtu, je zamýšlen jako abstraktní zástupce pro čas potřebný k implementaci výpočtu. Každá elementární operace vyžaduje určitý čas na provedení, a čím více jich výpočet potřebuje, tím déle bude trvat, alespoň obecně. V zájmu jednoduchosti budeme nadále udržovat toto spojení mezi výpočetními náklady a časem potřebným ke spuštění algoritmů.

Ale všimni si, že velikost Circuit nemusí nutně přímo odpovídat tomu, jak dlouho trvá jeho spuštění. V našem booleovském Circuit pro výpočet XOR dvou bitů by se například dvě Gate FANOUT mohly provést současně, stejně jako dvě Gate NOT a také dvě Gate AND. Jiný způsob měření efektivity Circuit, který bere v úvahu tuto možnost paralelizace, je pomocí jejich hloubky. To je minimální počet vrstev Gate potřebných v rámci Circuit, kde Gate v každé vrstvě operují na různých vodičích. Ekvivalentně je hloubka Circuit maximální počet Gate, na které narazíš na jakékoliv cestě od vstupního vodiče k výstupnímu vodiči. Pro výše uvedený Circuit je například hloubka 4.

Hloubka Circuit je jedním ze způsobů, jak formalizovat dobu běhu paralelních výpočtů. Je to pokročilé téma a existují velmi sofistikované konstrukce Circuit, které minimalizují hloubku potřebnou pro určité výpočty. Existují také některé fascinující nezodpovězené otázky týkající se hloubky Circuit. (Například o hloubce Circuit potřebné k výpočtu NSD toho stále mnoho nevíme.) V této sérii toho o hloubce Circuit mnoho dalšího neřekneme, kromě uvedení několika zajímavých faktů o hloubce Circuit průběžně, ale mělo by být jasně uznáno, že paralelizace je potenciálním zdrojem výpočetních výhod.

Přiřazování nákladů různým Gate

Jedna závěrečná poznámka ohledně velikosti Circuit a výpočetních nákladů je, že je možné přiřadit různým Gate různé náklady, namísto toho, aby každý Gate přispíval k celkovým nákladům stejně.

Například, jak již bylo zmíněno, Gate FANOUT se v booleovských Circuit často považují za bezplatné — což znamená, že bychom mohli zvolit, že Gate FANOUT mají nulové náklady. Jako další příklad, když pracujeme v dotazovém modelu a počítáme počet dotazů, které Circuit provede na vstupní funkci (ve formě černé skříňky), efektivně přiřazujeme jednotkové náklady dotazovým Gate a nulové náklady ostatním Gate, jako jsou Hadamardovy Gate. Posledním příkladem je, že někdy přiřazujeme různým Gate různé náklady v závislosti na tom, jak obtížné je je implementovat, což se může lišit podle zvažovaného hardwaru.

I když jsou všechny tyto možnosti v různých kontextech rozumné, pro tuto lekci to zjednodušíme a zůstaneme u velikosti Circuit jako reprezentace výpočetních nákladů.

Náklady jako funkce délky vstupu

Primárně nás zajímá, jak se výpočetní náklady škálují, když se vstupy stávají stále většími. To nás vede k reprezentaci nákladů algoritmů jako funkcí délky vstupu.

Rodiny Circuit

Vstupy daného výpočetního problému se mohou lišit v délce a potenciálně se stávat libovolně velkými. Každý Circuit má na druhou stranu pevný počet Gate a vodičů. Z tohoto důvodu, když přemýšlíme o algoritmech z hlediska Circuit, obecně potřebujeme nekonečně velké rodiny Circuit k reprezentaci algoritmů. Rodinou Circuit rozumíme posloupnost Circuit, které rostou na velikosti a umožňují zpracování stále větších vstupů.

Například si představ, že máme klasický algoritmus pro faktorizaci celých čísel, jako je ten, který používá factorint. Jako všechny klasické algoritmy, i tento algoritmus lze implementovat pomocí booleovských Circuit — ale k tomu budeme potřebovat samostatný Circuit pro každou možnou délku vstupu. Kdybychom se podívali na výsledné Circuit pro různé délky vstupů, viděli bychom, že jejich velikosti přirozeně rostou s rostoucí délkou vstupu — což odráží skutečnost, že faktorizace 4bitových celých čísel je mnohem jednodušší a vyžaduje daleko méně elementárních operací než faktorizace 1024bitových celých čísel.

To nás vede k reprezentaci výpočetních nákladů algoritmu funkcí $t,$ definovanou tak, že $t(n)$ je počet Gate v Circuit, který implementuje algoritmus pro $n$-bitové vstupy. Formálněji řečeno, algoritmus v modelu booleovských Circuit je popsán posloupností Circuit $\{C_1, C_2, C_3,\ldots\},$ kde $C_n$ řeší jakýkoliv problém, o kterém mluvíme, pro $n$-bitové vstupy (nebo obecněji pro vstupy, jejichž velikost je nějakým způsobem parametrizována pomocí $n$), a funkce $t$ reprezentující náklady tohoto algoritmu je definována jako

$$t(n) = \operatorname{size}(C_n).$$

Pro kvantové Circuit je situace podobná, kde stále větší Circuit jsou potřeba pro zpracování stále delších vstupních řetězců.

Příklad: sčítání celých čísel

Pro další vysvětlení se na chvíli zaměřme na problém sčítání celých čísel, který je mnohem jednodušší než faktorizace celých čísel nebo dokonce výpočet NSD.

Integer addition

Vstup: celá čísla $N$ a $M$
Výstup: $N+M$

Jak bychom mohli navrhnout booleovské Circuit pro řešení tohoto problému?

Pro zjednodušení omezíme naši pozornost na případ, kdy $N$ a $M$ jsou obě nezáporná celá čísla reprezentovaná $n$-bitovými řetězci v binárním zápisu. Povolíme libovolný počet úvodních nul v těchto kódováních, takže

$$0\leq N,M\leq 2^n - 1.$$

Výstupem bude $(n+1)$-bitový binární řetězec reprezentující součet, což je maximální počet bitů, které potřebujeme k vyjádření výsledku.

Začneme algoritmem — standardním algoritmem pro sčítání binárních reprezentací — což je analogie v soustavě o základu 2 ke způsobu, jakým se sčítání učí na základních školách po celém světě. Tento algoritmus lze implementovat pomocí booleovských Circuit následovně.

Počínaje nejméně významnými bity můžeme vypočítat jejich XOR, abychom určili nejméně významný bit součtu. Poté vypočítáme bit přenosu, což je AND dvou nejméně významných bitů $N$ a $M.$ Někdy se tyto dvě operace dohromady nazývají poloviční sčítačka (half adder).

Pomocí Circuit pro XOR, který jsme už několikrát viděli, spolu s jedním Gate AND a dvěma Gate FANOUT, můžeme sestavit poloviční sčítačku s 10 Gate. Pokud bychom se z nějakého důvodu rozhodli zahrnout Gate XOR do naší sady elementárních operací, potřebovali bychom 1 Gate AND, 1 Gate XOR a 2 Gate FANOUT k sestavení poloviční sčítačky.

Přejdeme-li k významnějším bitům, můžeme použít podobný postup, ale tentokrát zahrneme bit přenosu z každé předchozí pozice do našeho výpočtu. Kaskádovým zapojením dvou polovičních sčítaček a provedením OR jejich bitů přenosu můžeme vytvořit to, co je známé jako úplná sčítačka (full adder).

To vyžaduje celkem 21 Gate: 2 Gate AND, 2 Gate XOR (každý vyžadující 7 Gate k implementaci), jeden Gate OR a 4 Gate FANOUT.

Nakonec kaskádovým zapojením úplných sčítaček získáme booleovský Circuit pro sčítání nezáporných celých čísel. Například následující Circuit počítá součet dvou 4bitových celých čísel.

Obecně to vyžaduje

$$21 (n-1) + 10 = 21 n - 11$$

Gate. Pokud bychom se rozhodli zahrnout Gate XOR do naší sady elementárních operací, potřebovali bychom $2n-1$ Gate AND, $2n-1$ Gate XOR, $n-1$ Gate OR a $4n-2$ Gate FANOUT, celkem $9n-5$ Gate. Pokud navíc rozhodneme nepočítat Gate FANOUT, je to $5n-3$ Gate.

Asymptotická notace

Na jedné straně je dobré přesně vědět, kolik Gate je potřeba k provedení různých výpočtů, jako v příkladu sčítání celých čísel výše. Tyto detaily jsou důležité pro skutečnou stavbu Circuit.

Na druhé straně, pokud bychom prováděli analýzy na této úrovni detailu pro všechny výpočty, které nás zajímají, včetně těch pro úlohy, které jsou mnohem složitější než sčítání, velmi rychle bychom se utopili v detailech. Abychom to zvládli a záměrně potlačili detaily vedlejšího významu, obvykle při analýze algoritmů používáme notaci Big-O. Pomocí této notace můžeme vyjádřit řád, jakým funkce rostou.

$$g(n) \leq c\cdot h(n)$$

pro všechna $n \geq n_0.$ Typicky se $h(n)$ volí jako co nejjednodušší výraz, aby notace mohla jednoduše vyjádřit limitní chování funkce. Například $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Tuto notaci lze poměrně přímočaře rozšířit na funkce s více argumenty. Například pokud máme dvě funkce $g(n,m)$ a $h(n,m)$ definované na kladných celých číslech $n$ a $m,$ píšeme $g(n,m) = O(h(n,m)),$ pokud existuje kladné reálné číslo $c > 0$ a kladné celé číslo $k_0$ takové, že

$$g(n,m) \leq c\cdot h(n,m)$$

kdykoli $n+m \geq k_0.$

Když tuto notaci propojíme s příkladem sčítání nezáporných celých čísel, dojdeme k závěru, že existuje rodina Booleovských obvodů $\{C_1, C_2,\ldots,\},$ kde $C_n$ sčítá dvě $n$-bitová nezáporná celá čísla, taková že $\operatorname{size}(C_n) = O(n).$ To odhaluje nejpodstatnější vlastnost toho, jak náklady sčítání rostou s velikostí vstupu: rostou lineárně.

Všimni si také, že to nezávisí na konkrétním detailu, zda považujeme XOR Gate za jednotkovou cenu nebo cenu $7.$ Obecně nám použití Big-O notace umožňuje formulovat tvrzení o výpočetních nákladech, která nejsou citlivá na takové nízkoúrovňové detaily.

Další příklady

Zde je několik dalších příkladů problémů z výpočetní teorie čísel, počínaje násobením.

Integer multiplication

Vstup: celá čísla $N$ a $M$
Výstup: $NM$

Vytváření Booleovských obvodů pro tento problém je obtížnější než vytváření obvodů pro sčítání — ale když se zamyslíš nad standardním algoritmem násobení, můžeš přijít s obvody o velikosti $O(n^2)$ pro tento problém (za předpokladu, že $N$ i $M$ jsou reprezentovány $n$-bitovými binárními zápisy). Obecněji, pokud $N$ má $n$ bitů a $M$ má $m$ bitů, existují Booleovské obvody o velikosti $O(nm)$ pro násobení $N$ a $M.$

Existují ve skutečnosti i jiné způsoby násobení, které škálují lépe. Například Schönhage-Strassenův algoritmus násobení lze použít k vytvoření Booleovských obvodů pro násobení dvou $n$-bitových celých čísel s náklady $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ Složitost této metody však způsobuje velkou režii, takže je praktická pouze pro čísla s desítkami tisíc bitů.

Dalším základním problémem je dělení, které interpretujeme jako výpočet podílu i zbytku pro daného celočíselného dělitele a dělence.

Integer division

Vstup: celá čísla $N$ a $M\neq0$
Výstup: celá čísla $q$ a $r$ splňující $0\leq r < |M|$ a $N = q M + r$

Náklady celočíselného dělení jsou podobné násobení: pokud $N$ má $n$ bitů a $M$ má $m$ bitů, existují Booleovské obvody o velikosti $O(nm)$ pro řešení tohoto problému. A stejně jako u násobení jsou známy asymptoticky lepší metody.

Nyní můžeme porovnat známé algoritmy pro výpočet NSD s algoritmy pro sčítání a násobení. Euklidův algoritmus pro výpočet NSD $n$-bitového čísla $N$ a $m$-bitového čísla $M$ vyžaduje Booleovské obvody o velikosti $O(nm),$ podobně jako standardní algoritmy pro násobení a dělení. Stejně jako u násobení a dělení existují asymptoticky rychlejší algoritmy pro NSD — včetně těch vyžadujících $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ elementárních operací pro výpočet NSD dvou $n$-bitových čísel.

Poněkud nákladnějším výpočtem, který se vyskytuje v teorii čísel, je modulární umocňování.

Integer modular exponentiation

Vstup: celá čísla $N,$ $K,$ a $M$ s $K\geq 0$ a $M\geq 1$
Výstup: $N^K \hspace{1mm} (\text{mod }M)$

Výrazem $N^K\hspace{1mm} (\text{mod }M)$ myslíme zbytek po dělení $N^K$ číslem $M,$ tedy jedinečné celé číslo $r$ splňující $0\leq r < M$ a $N^K = q M + r$ pro nějaké celé číslo $q.$

Pokud $N$ má $n$ bitů, $M$ má $m$ bitů a $K$ má $k$ bitů, tento problém lze řešit Booleovskými obvody o velikosti $O(k m^2 + nm).$ To vůbec není zřejmé. Řešením není nejprve spočítat $N^K$ a poté vzít zbytek, což by vyžadovalo exponenciálně mnoho bitů jen pro uložení čísla $N^K.$ Místo toho můžeme použít algoritmus umocňování (známý též jako binární metoda a opakované umocňování na druhou), který využívá binární reprezentaci $K$ k provedení celého výpočtu modulo $M.$ Za předpokladu, že $N,$ $M$ a $K$ jsou všechna $n$-bitová čísla, získáme $O(n^3)$ algoritmus — neboli kubický algoritmus. A opět existují známé algoritmy, které jsou složitější, ale asymptoticky rychlejší.

Náklady na faktorizaci celých čísel

Na rozdíl od právě probíraných algoritmů jsou známé algoritmy pro faktorizaci celých čísel mnohem nákladnější — jak bychom mohli očekávat z diskuse dříve v této lekci.

Jedním jednoduchým přístupem k faktorizaci je zkusmé dělení, kdy algoritmus prohledává seznam $2,\ldots,\sqrt{N}$, aby našel prvočíselný dělitel vstupního čísla $N.$ To vyžaduje $O(2^{n/2})$ iterací v nejhorším případě, když $N$ je $n$-bitové číslo. Každá iterace vyžaduje zkusmé dělení, což znamená $O(n^2)$ elementárních operací na každou iteraci (při použití standardního algoritmu pro dělení celých čísel). Výsledkem jsou obvody o velikosti $O(n^2 2^{n/2}),$ což je exponenciální vzhledem ke vstupní velikosti $n.$

Existují algoritmy pro faktorizaci celých čísel s lepším škálováním. Dříve zmíněné síto číselného tělesa, což je algoritmus využívající náhodnost, obecně vyžaduje (jak se věří, ale není to rigorózně dokázáno)

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

elementárních operací k faktorizaci $n$-bitových celých čísel s vysokou pravděpodobností. I když je dosti významné, že $n$ je v exponentu tohoto výrazu umocněno na $1/3$, fakt, že se objevuje v exponentu, je stále problém způsobující špatné škálování — a částečně vysvětluje, proč RSA1024 zůstává mimo oblast jeho použitelnosti.

Polynomiální versus exponenciální náklady

Klasické algoritmy pro sčítání, násobení, dělení celých čísel a výpočet největších společných dělitelů nám umožňují řešit tyto problémy v mžiku oka pro vstupy s tisíci bity. Sčítání má lineární náklady, zatímco ostatní tři problémy mají kvadratické náklady (nebo subkvadratické náklady při použití asymptoticky rychlých algoritmů). Modulární umocňování je nákladnější, ale stále se dá provést poměrně efektivně, s kubickými náklady (nebo sub-kubickými náklady při použití asymptoticky rychlých algoritmů).

To vše jsou příklady algoritmů s polynomiálními náklady, což znamená, že mají náklady $O(n^c)$ pro nějakou zvolenou pevnou konstantu $c > 0.$ Jako hrubou aproximaci prvního řádu jsou algoritmy s polynomiálními náklady abstraktně považovány za efektivní algoritmy.

Naproti tomu známé klasické algoritmy pro faktorizaci celých čísel mají exponenciální náklady. Někdy se náklady síta číselného tělesa popisují jako sub-exponenciální, protože $n$ je v exponentu umocněno na $1/3$, ale v teorii složitosti je typičtější vyhradit tento termín pro algoritmy, jejichž náklady jsou

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

pro každé $\varepsilon > 0.$ Takzvané NP-úplné problémy jsou třída problémů, u kterých není známo (a je široce předpokládáno, že nemají) algoritmy s polynomiálními náklady. Obvodová formulace hypotézy exponenciálního času postuluje něco ještě silnějšího, a sice že žádný NP-úplný problém nemůže mít algoritmus se sub-exponenciálními náklady.

Spojení algoritmů s polynomiálními náklady s efektivními algoritmy musíš chápat jako volnou abstrakci. Samozřejmě, pokud náklady algoritmu škálují jako $n^{1000}$ nebo $n^{1000000}$ pro vstupy velikosti $n,$ pak je přehnané popisovat takový algoritmus jako efektivní. Avšak i algoritmus s náklady škálujícími jako $n^{1000000}$ musí dělat něco chytrého, aby se vyhnul exponenciálním nákladům, které obecně očekáváme u algoritmů založených nějakým způsobem na „hrubé síle" nebo „vyčerpávajícím prohledávání". Ani sofistikovaná vylepšení síta číselného tělesa se například nedokážou vyhnout tomuto exponenciálnímu škálování nákladů. Algoritmy s polynomiálními náklady naproti tomu dokážou nějakým způsobem využít strukturu problému a vyhnout se exponenciálnímu škálování.

V praxi je identifikace algoritmu s polynomiálními náklady pro daný problém jen prvním krokem ke skutečné efektivitě. Prostřednictvím algoritmických vylepšení lze algoritmy s polynomiálními náklady a velkými exponenty někdy dramaticky zlepšit a snížit náklady na „rozumnější" polynomiální škálování. Někdy se věci stávají snazšími, když je známo, že jsou možné — takže identifikace algoritmu s polynomiálními náklady pro problém může mít také efekt inspirace k novým, ještě efektivnějším algoritmům.

Když zvažujeme výhody kvantových výpočtů oproti klasickým, naše oči se obecně nejprve obracejí k exponenciálním výhodám, nebo alespoň super-polynomiálním výhodám — ideálně k nalezení algoritmů s polynomiálními náklady na kvantových počítačích pro problémy, o kterých není známo, že by měly klasické algoritmy s polynomiálními náklady. Teoretické výhody tohoto řádu mají největší šance vést ke skutečným praktickým výhodám — ale identifikace takových výhod je mimořádně obtížná výzva. V současnosti je známo jen několik příkladů, ale hledání pokračuje.

Polynomiální (ale ne super-polynomiální) výhody ve výpočetních nákladech kvantových oproti klasickým jsou také zajímavé a neměly by být odmítány — ale vzhledem k současnému rozdílu mezi kvantovou a klasickou výpočetní technologií se v současné době zdají poněkud méně přesvědčivé. Jednoho dne by se však mohly stát významnými. Groverův algoritmus, který je probírán v pozdější lekci, například nabízí kvadratickou výhodu kvantových oproti klasickým výpočtům pro takzvané nestrukturované prohledávání a má potenciál pro široké aplikace.

Skryté náklady obvodových výpočtů

Je tu ještě jedna poslední záležitost, kterou stojí za to zmínit, i když se jí v tomto kurzu dále nebudeme zabývat. Při práci s obvody existují „skryté" výpočetní náklady, a ty se týkají samotných specifikací obvodů. Jak se vstupy stávají delšími a delšími, jsou zapotřebí větší a větší obvody — ale musíme se nějak dostat k popisům těchto obvodů, pokud je chceme implementovat.

Pro všechny příklady, které jsme probírali, nebo budeme probírat v následujících lekcích, existuje základní algoritmus, ze kterého jsou obvody odvozeny. Obvody v rodině obvykle následují nějaký základní vzor, který je snadné extrapolovat na větší a větší vstupy, jako je kaskádování úplných sčítaček pro vytvoření booleovských obvodů pro sčítání nebo provádění vrstev Hadamardových Gate a dalších Gate v nějakém snadno popsatelném vzoru.

Ale co se stane, pokud jsou se vzory v samotných obvodech spojeny neúměrné výpočetní náklady? Například popis každého členu $C_n$ v rodině obvodů by v principu mohl být určen nějakou extrémně obtížně vypočitatelnou funkcí $n.$

Odpověď je, že to skutečně je problém — a proto musíme na rodiny obvodů klást dodatečná omezení nad rámec polynomiálních nákladů, aby skutečně představovaly efektivní algoritmy.