Dotazový model výpočtu

Když modelujeme výpočty v matematických termínech, typicky máme na mysli takový druh procesu, jaký představuje následující obrázek, kde jsou informace poskytnuty jako vstup, proběhne výpočet a je vyprodukován výstup.

I když je pravda, že počítače, které dnes používáme, nepřetržitě přijímají vstup a produkují výstup, v podstatě interagují jak s námi, tak s jinými počítači způsobem, který tento obrázek nezachycuje, záměrem není reprezentovat průběžný provoz počítačů. Spíše je cílem vytvořit jednoduchou abstrakci výpočtu, zaměřenou na izolované výpočetní úlohy. Například vstup může kódovat číslo, vektor, matici, graf, popis molekuly nebo něco složitějšího, zatímco výstup kóduje řešení výpočetní úlohy, kterou máme na mysli.

Klíčová myšlenka je, že vstup je výpočtu poskytnut, obvykle ve formě binárního řetězce, přičemž žádná jeho část není skryta.

Popis modelu

V dotazovacím modelu výpočtu není celý vstup poskytnut výpočtu jako ve standardnějším modelu naznačeném výše. Místo toho je vstup zpřístupněn ve formě funkce, ke které výpočet přistupuje prostřednictvím dotazů. Alternativně můžeme nahlížet na výpočty v dotazovacím modelu jako na výpočty s náhodným přístupem k bitům (nebo segmentům bitů) vstupu.

V kontextu dotazovacího modelu často říkáme, že vstup je poskytován orákulem nebo černou skříňkou. Oba termíny naznačují, že úplný popis vstupu je před výpočtem skryt a jediný způsob, jak k němu přistupovat, je klást otázky. Je to, jako bychom se dotazovali Orákula v Delfách ohledně vstupu: neřekne nám vše, co ví, odpovídá pouze na konkrétní otázky. Termín černá skříňka dává smysl zejména tehdy, když si vstup představujeme jako funkci; nemůžeme nahlédnout dovnitř funkce a porozumět tomu, jak funguje, můžeme ji pouze vyhodnotit na argumentech, které si vybereme.

V této lekci budeme pracovat výhradně s binárními řetězci, na rozdíl od řetězců obsahujících jiné symboly, takže pro pohodlí budeme dále psát $\Sigma = \{0,1\}$ pro binární abecedu. Budeme uvažovat o různých výpočetních problémech, přičemž několik jednoduchých příkladů bude popsáno zanedlouho, ale u všech bude vstup reprezentován funkcí tvaru

$$f:\Sigma^n \rightarrow \Sigma^m$$

pro dvě kladná celá čísla $n$ a $m.$ Přirozeně bychom mohli zvolit jiný název místo $f,$ ale v celé lekci zůstaneme u $f.$

Říci, že výpočet provádí dotaz, znamená, že je vybrán nějaký řetězec $x \in \Sigma^n$ a poté je řetězec $f(x)\in\Sigma^m$ zpřístupněn výpočtu orákulem. Přesný způsob, jak to funguje pro kvantové algoritmy, bude probrán zanedlouho — musíme se ujistit, že to lze provést unitární kvantovou operací umožňující dotazy v superpozici — ale prozatím o tom můžeme přemýšlet intuitivně na vysoké úrovni.

Nakonec, způsob, jakým budeme měřit efektivitu dotazovacích algoritmů, je jednoduchý: budeme počítat počet dotazů, které vyžadují. To souvisí s časem potřebným k provedení výpočtu, ale není to přesně totéž, protože ignorujeme čas pro operace jiné než dotazy a také zacházíme s dotazy, jako by každý měl jednotkovou cenu. Můžeme vzít v úvahu i operace kromě dotazů, pokud chceme (a to se občas dělá), ale omezení pozornosti pouze na počet dotazů pomáhá udržet věci jednoduché.

Příklady dotazovacích problémů

Zde je několik jednoduchých příkladů dotazovacích problémů.

• OR. Vstupní funkce má tvar $f:\Sigma^n \rightarrow \Sigma$ (takže $m=1$ pro tento problém). Úkolem je vypsat $1,$ pokud existuje řetězec $x\in\Sigma^n,$ pro který $f(x) = 1,$ a vypsat $0,$ pokud takový řetězec neexistuje. Pokud si funkci $f$ představíme jako posloupnost $2^n$ bitů, ke kterým máme náhodný přístup, problém spočívá ve výpočtu OR těchto bitů.

• Parita. Vstupní funkce má opět tvar $f:\Sigma^n \rightarrow \Sigma.$ Úkolem je určit, zda je počet řetězců $x\in\Sigma^n,$ pro které $f(x) = 1,$ sudý nebo lichý. Přesněji řečeno, požadovaný výstup je $0,$ pokud má množina $\{x\in\Sigma^n : f(x) = 1\}$ sudý počet prvků, a $1,$ pokud má lichý počet prvků. Pokud si funkci $f$ představíme jako posloupnost $2^n$ bitů, ke kterým máme náhodný přístup, problém spočívá ve výpočtu parity (neboli exkluzivního OR) těchto bitů.

• Minimum. Vstupní funkce má tvar $f:\Sigma^n \rightarrow \Sigma^m$ pro libovolnou volbu kladných celých čísel $n$ a $m.$ Požadovaným výstupem je řetězec $y \in \{f(x) : x\in\Sigma^n\},$ který je první v lexikografickém (tj. slovníkovém) uspořádání $\Sigma^m.$ Pokud si funkci $f$ představíme jako posloupnost $2^n$ celých čísel zakódovaných jako řetězce délky $m$ v binárním zápisu, ke kterým máme náhodný přístup, problém spočívá ve výpočtu minima těchto celých čísel.

Uvažujeme také dotazovací problémy, kde máme slib ohledně vstupu. To znamená, že dostaneme nějaký druh záruky ohledně vstupu a neneseme odpovědnost za to, co se stane, když tato záruka není splněna. Jiný způsob, jak tento typ problému popsat, je říci, že některé vstupní funkce (ty, pro které slib není splněn) jsou považovány za vstupy typu „nezáleží na tom". Na algoritmy nejsou kladeny vůbec žádné požadavky, pokud dostanou vstupy typu „nezáleží na tom".

Zde je jeden příklad problému se slibem:

• Unique search. Vstupní funkce má tvar $f:\Sigma^n \rightarrow \Sigma$ a je nám slíbeno, že existuje právě jeden řetězec $z\in\Sigma^n,$ pro který $f(z) = 1,$ přičemž $f(x) = 0$ pro všechny řetězce $x\neq z.$ Úkolem je najít tento jedinečný řetězec $z.$

Všechny čtyři právě popsané příklady jsou přirozené v tom smyslu, že se snadno popisují a můžeme si představit různé situace nebo kontexty, ve kterých by se mohly vyskytnout.

Naproti tomu některé dotazovací problémy nejsou vůbec takto „přirozené". Při studiu dotazovacího modelu totiž někdy přicházíme s velmi složitými a vysoce umělými problémy, u kterých si lze jen těžko představit, že by je někdo kdy chtěl v praxi řešit. To ale neznamená, že tyto problémy nejsou zajímavé! Věci, které se na první pohled mohou zdát umělé nebo nepřirozené, mohou poskytnout nečekané vodítka nebo inspirovat nové myšlenky. Shorův kvantový algoritmus pro faktorizaci, který byl inspirován Simonovým algoritmem, je skvělým příkladem. Důležitou součástí studia dotazovacího modelu je také hledání extrémů, které mohou osvětlit jak potenciální výhody, tak omezení kvantového počítání.

Dotazovací Gate

Když popisujeme výpočty pomocí Circuit, dotazy se provádějí speciálními Gate nazývanými dotazovací Gate.

Nejjednodušší způsob, jak definovat dotazovací Gate pro klasické Booleovské Circuit, je jednoduše jim umožnit přímo počítat vstupní funkci $f,$ jak naznačuje následující obrázek.

Když je Booleovský Circuit vytvořen pro dotazovací problém, ke vstupní funkci $f$ se přistupuje prostřednictvím těchto Gate a počet dotazů, které Circuit provádí, je jednoduše počet dotazovacích Gate, které se v Circuit vyskytují. Vstupní vodiče samotného Booleovského Circuit jsou inicializovány na pevné hodnoty, které by měly být považovány za součást algoritmu (na rozdíl od vstupů problému).

Například zde je Booleovský Circuit s klasickými dotazovacími Gate, který řeší výše popsaný problém parity pro funkci tvaru $f:\Sigma\rightarrow\Sigma$:

Tento algoritmus provádí dva dotazy, protože obsahuje dva dotazovací Gate. Funguje tak, že funkce $f$ je dotázána na dvou možných vstupech, $0$ a $1,$ a výsledky jsou zapojeny do Booleovského Circuit, který počítá XOR. (Tento konkrétní Circuit se objevil jako příklad Booleovského obvodu v lekci Kvantové obvody kurzu Základy kvantové informace.)

Pro kvantové Circuit tato definice dotazovacích Gate nefunguje, protože tyto Gate budou pro některé volby funkce $f$ neunitární. Místo toho tedy definujeme unitární dotazovací Gate, které na stavech standardní báze fungují tak, jak naznačuje tento obrázek:

Zde předpokládáme, že $x\in\Sigma^n$ a $y\in\Sigma^m$ jsou libovolné řetězce. Zápis $y\oplus f(x)$ označuje bitový exkluzivní OR dvou řetězců, které mají v tomto případě délku $m.$ Například $001 \oplus 101 = 100.$

Intuitivně řečeno, Gate $U_f$ (pro libovolně zvolenou funkci $f$) zrcadlí horní vstupní řetězec $x$ a XORuje hodnotu funkce $f(x)$ na spodní vstupní řetězec $y,$ což je unitární operace pro každou volbu funkce $f.$ Ve skutečnosti se jedná o deterministickou operaci a je svou vlastní inverzí. To znamená, že jako matice je $U_f$ vždy permutační matice, tedy matice s jedinou $1$ v každém řádku a v každém sloupci, přičemž všechny ostatní prvky jsou $0.$ Aplikace permutační matice na vektor jednoduše přemístí prvky vektoru (odtud termín permutační matice), a proto nemění euklidovskou normu tohoto vektoru — což odhaluje, že permutační matice jsou vždy unitární.

Je třeba zdůraznit, že když analyzujeme dotazovací algoritmy pouhým počítáním dotazů, které dotazovací algoritmus provede, zcela ignorujeme obtížnost fyzické konstrukce dotazovacích Gate — jak pro klasickou, tak pro kvantovou verzi právě popsanou. Intuitivně řečeno, konstrukce dotazovacích Gate je součástí přípravy vstupu, nikoli součástí hledání řešení.

To se může zdát nerozumné, ale musíme mít na paměti, že se nesnažíme popisovat praktické počítání ani plně vyčíslit potřebné zdroje. Spíše definujeme teoretický model, který pomáhá osvětlit potenciální výhody kvantového počítání. K tomuto bodu se vrátíme v lekci následující po této, kdy obrátíme pozornost ke standardnějšímu modelu výpočtu, kde jsou vstupy dány explicitně Circuit jako binární řetězce.