Simonův algoritmus

Simonův algoritmus je kvantový dotazovací algoritmus pro problém známý jako Simonův problém. Jedná se o problém s příslibem (promise problem), který má podobný charakter jako problémy Deutsch-Jozsa a Bernstein-Vazirani, ale konkrétní detaily se liší.

Simonův algoritmus je významný, protože poskytuje exponenciální výhodu kvantových algoritmů oproti klasickým (včetně probabilistických) algoritmům, a technika, kterou používá, inspirovala Petera Shora k objevu efektivního kvantového algoritmu pro faktorizaci celých čísel.

Simonův problém

Vstupní funkce Simonova problému má tvar

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

pro kladná celá čísla $n$ a $m.$ Mohli bychom se omezit na případ $m = n$ v zájmu jednoduchosti, ale toto zjednodušení by nám mnoho nepřineslo — Simonův algoritmus a jeho analýza jsou v obou případech v podstatě stejné.

Simonův problém

Vstup: funkce $f:\Sigma^n \rightarrow \Sigma^m$
Příslib: existuje řetězec $s\in\Sigma^n$ takový, že $[f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)]$ pro všechna $x,y\in\Sigma^n$
Výstup: řetězec $s$

Za chvíli příslib podrobněji rozebereme, abychom lépe porozuměli tomu, co říká, ale nejprve si ujasněme, že vyžaduje, aby $f$ měla velmi speciální strukturu — většina funkcí tedy tento příslib nesplňuje. Je také na místě připustit, že tento problém nemá praktický význam. Jedná se spíše o poněkud umělý problém, který je vytvořený na míru tak, aby byl snadný pro kvantové počítače a obtížný pro klasické počítače.

Existují dva hlavní případy: první případ je, že $s$ je nulový řetězec $0^n,$ a druhý případ je, že $s$ není nulový řetězec.

• Případ 1: $s=0^n.$ Pokud je $s$ nulový řetězec, pak můžeme zjednodušit výrok „právě tehdy, když" v příslibu tak, aby zněl $[f(x) = f(y)] \Leftrightarrow [x = y].$ To je ekvivalentní tomu, že $f$ je prostá funkce (injekce).

• Případ 2: $s\neq 0^n.$ Pokud $s$ není nulový řetězec, pak splnění příslibu pro tento řetězec implikuje, že $f$ je dva-na-jeden (two-to-one), což znamená, že pro každý možný výstupní řetězec $f$ existují právě dva vstupní řetězce, které způsobí, že $f$ tento řetězec vypíše. Tyto dva vstupní řetězce navíc musí mít tvar $w$ a $w \oplus s$ pro nějaký řetězec $w.$

Je důležité si uvědomit, že pokud je příslib splněn, může existovat pouze jeden řetězec $s,$ který vyhovuje, takže pro funkce splňující příslib existuje vždy jediná správná odpověď.

Zde je příklad funkce tvaru $f:\Sigma^3 \rightarrow \Sigma^5,$ která splňuje příslib pro řetězec $s = 011.$

$$\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}$$

Existuje $8$ různých vstupních řetězců a $4$ různých výstupních řetězců, z nichž každý se vyskytuje dvakrát — jedná se tedy o funkci dva-na-jeden. Navíc pro libovolné dva různé vstupní řetězce, které produkují stejný výstupní řetězec, vidíme, že bitový XOR těchto dvou vstupních řetězců se rovná $011,$ což je ekvivalentní tvrzení, že jeden z nich se rovná druhému XORovanému s $s.$

Všimni si, že jediné, na čem u skutečných výstupních řetězců záleží, je to, zda jsou pro různé volby vstupních řetězců stejné nebo různé. Například ve výše uvedeném příkladu jsou čtyři řetězce $(10011,$ $00101,$ $00001,$ a $11010),$ které se objevují jako výstupy $f.$ Tyto čtyři řetězce bychom mohli nahradit jinými řetězci, pokud by byly navzájem různé, a správné řešení $s = 011$ by se nezměnilo.

Popis algoritmu

Zde je diagram kvantového Circuit představující Simonův algoritmus.

Pro upřesnění, nahoře je $n$ Qubitů, na které působí Hadamardovy Gate, a dole je $m$ Qubitů, které jdou přímo do dotazovací Gate. Vypadá to velmi podobně jako algoritmy, které jsme již v této lekci probírali, ale tentokrát nedochází k fázovému zpětnému rázu (phase kickback); spodních $m$ Qubitů vstupuje do dotazovací Gate ve stavu $\vert 0\rangle.$

K vyřešení Simonova problému pomocí tohoto Circuit bude ve skutečnosti zapotřebí několik nezávislých běhů, po nichž následuje klasický krok dodatečného zpracování, který bude popsán později po analýze chování Circuit.

Analýza

Analýza Simonova algoritmu začíná podobně jako u algoritmu Deutsch-Jozsa. Po provedení první vrstvy Hadamardových Gate na horních $n$ Qubitech se stav změní na

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.$$

Když se provede $U_f,$ výstup funkce $f$ se XORuje na nulový stav spodních $m$ Qubitů, takže stav se změní na

$$\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.$$

Když se provede druhá vrstva Hadamardových Gate, získáme následující stav pomocí stejného vzorce pro působení vrstvy Hadamardových Gate jako dříve.

$$\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle$$

V tomto bodě se analýza odchyluje od analýz předchozích algoritmů v této lekci.

Zajímá nás pravděpodobnost, že měření dá jako výsledek každý možný řetězec $y\in\Sigma^n.$ Pomocí pravidel pro analýzu měření popsaných v lekci Více systémů kurzu Základy kvantové informace zjistíme, že pravděpodobnost $p(y)$ získání řetězce $y$ je rovna

$$p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.$$

Abychom tyto pravděpodobnosti lépe uchopili, budeme potřebovat trochu více notace a terminologie. Za prvé, obor hodnot funkce $f$ je množina obsahující všechny její výstupní řetězce.

$$\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}$$

Za druhé, pro každý řetězec $z\in\operatorname{range}(f)$ můžeme množinu všech vstupních řetězců, pro které se funkce vyhodnotí na tento výstupní řetězec $z,$ zapsat jako $f^{-1}(\{z\}).$

$$f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}$$

Množina $f^{-1}(\{z\})$ se nazývá vzor (preimage) množiny $\{z\}$ při zobrazení $f.$ Vzor při zobrazení $f$ můžeme definovat analogicky pro libovolnou množinu namísto $\{z\}$ — je to množina všech prvků, které $f$ zobrazí do dané množiny. (Tuto notaci bychom neměli zaměňovat s inverzní funkcí k $f,$ která nemusí existovat. Nápovědou, která nám pomáhá vyhnout se této záměně, je skutečnost, že argumentem na levé straně je množina $\{z\},$ nikoli prvek $z.$)

Pomocí této notace můžeme rozdělit součet v našem výrazu pro pravděpodobnosti výše a získat

$$p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.$$

Každý řetězec $x\in\Sigma^n$ je zastoupen právě jednou ve dvou součtech — v podstatě jen třídíme tyto řetězce do samostatných skupin podle toho, jaký výstupní řetězec $z = f(x)$ produkují při vyhodnocení funkce $f,$ a pak sčítáme zvlášť přes všechny skupiny.

Nyní můžeme vyhodnotit druhou mocninu euklidovské normy a získat

$$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.$$

Pro další zjednodušení těchto pravděpodobností se podívejme na hodnotu

$$\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}$$

pro libovolnou volbu $z\in\operatorname{range}(f).$

Pokud se stane, že $s = 0^n,$ pak je $f$ prostá funkce a pro každé $z\in\operatorname{range}(f)$ vždy existuje pouze jediný prvek $x\in f^{-1}(\{z\}).$ Hodnota výrazu $(1)$ je v tomto případě $1.$

Pokud naopak $s\neq 0^n,$ pak v množině $f^{-1}(\{z\})$ existují právě dva řetězce. Přesněji řečeno, pokud zvolíme $w\in f^{-1}(\{z\})$ jako kterýkoli z těchto dvou řetězců, pak druhý řetězec musí být $w \oplus s$ podle předpokladu v Simonově problému. Pomocí tohoto pozorování můžeme zjednodušit $(1)$ následovně.

$$\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}$$

Ukazuje se tedy, že hodnota $(1)$ je v obou případech nezávislá na konkrétní volbě $z\in\operatorname{range}(f).$

Nyní můžeme dokončit analýzu tím, že se podíváme na stejné dva případy jako předtím zvlášť.

• Případ 1: $s = 0^n.$ V tomto případě je funkce $f$ prostá, takže existuje $2^n$ řetězců $z\in\operatorname{range}(f),$ a dostaneme

  $$p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.$$

  Slovně řečeno, měření dává řetězec $y\in\Sigma^n$ vybraný rovnoměrně náhodně.

• Případ 2: $s \neq 0^n.$ V tomto případě je $f$ funkce dva-na-jednu, takže v $\operatorname{range}(f)$ je $2^{n-1}$ prvků. Pomocí výše uvedeného vzorce dospějeme k závěru, že pravděpodobnost změření každého $y\in\Sigma^n$ je

  $$p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}$$

  Slovně řečeno, dostaneme řetězec vybraný rovnoměrně náhodně z množiny $\{y\in\Sigma^n : y \cdot s = 0\},$ která obsahuje $2^{n-1}$ řetězců. (Protože $s\neq 0^n,$ přesně polovina binárních řetězců délky $n$ má binární skalární součin $1$ s $s$ a druhá polovina má binární skalární součin $0$ s $s,$ jak jsme již pozorovali při analýze Deutsch-Jozsova algoritmu pro Bernstein-Vaziraniho problém.)

Klasické post-zpracování

Nyní víme, jaké jsou pravděpodobnosti pro možné výsledky měření, když spustíme kvantový Circuit pro Simonův algoritmus. Stačí nám tato informace k určení $s$?

Odpověď je ano, za předpokladu, že jsme ochotni celý proces několikrát zopakovat a přijmout, že může selhat s určitou pravděpodobností, kterou můžeme udělat velmi malou tím, že Circuit spustíme dostatečně mnohokrát. Základní myšlenka je, že každé spuštění Circuit nám poskytuje statistické důkazy o $s,$ a tyto důkazy můžeme použít k nalezení $s$ s velmi vysokou pravděpodobností, pokud Circuit spustíme dostatečně mnohokrát.

Předpokládejme, že Circuit spustíme nezávisle $k$-krát, pro $k = n + 10.$ Na tomto konkrétním počtu iterací není nic zvláštního — mohli bychom zvolit $k$ větší (nebo menší) v závislosti na pravděpodobnosti selhání, kterou jsme ochotni tolerovat, jak uvidíme. Volba $k = n + 10$ zajistí, že máme více než $99{,}9$% šanci na obnovení $s.$

Spuštěním Circuit $k$-krát získáme řetězce $y^1,...,y^{k} \in \Sigma^n.$ Pro upřesnění, horní indexy zde jsou součástí názvů těchto řetězců, nikoli exponenty nebo indexy jejich bitů, takže máme

$$\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}$$

Nyní vytvoříme matici $M$ s $k$ řádky a $n$ sloupci tak, že jako binární položky vezmeme bity těchto řetězců.

$$M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}$$

V tuto chvíli nevíme, co je $s$ — naším cílem je tento řetězec najít. Ale představ si na chvíli, že řetězec $s$ známe, a vytvoříme sloupcový vektor $v$ z bitů řetězce $s = s_{n-1} \cdots s_0$ následovně.

$$v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}$$

Pokud provedeme násobení matice vektorem $M v$ modulo $2$ — což znamená, že provedeme násobení jako obvykle a poté vezmeme zbytek po dělení položek výsledku číslem $2$ — dostaneme nulový vektor.

$$M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}$$

To znamená, že řetězec $s,$ chápaný jako sloupcový vektor $v$ jak bylo právě popsáno, bude vždy prvkem jádra (null space) matice $M,$ za předpokladu, že aritmetiku provádíme modulo $2.$ To platí jak v případě, že $s = 0^n,$ tak v případě $s\neq 0^n.$ Přesněji řečeno, nulový vektor je vždy v jádře $M$ a v případě $s\neq 0^n$ se k němu přidává vektor, jehož položky jsou bity $s.$

Zbývající otázka je, zda v jádře $M$ budou kromě vektorů odpovídajících $0^n$ a $s$ ještě nějaké další vektory. Odpověď je, že to se stává čím dál méně pravděpodobným s rostoucím $k$ — a pokud zvolíme $k = n + 10,$ jádro $M$ nebude obsahovat žádné další vektory kromě těch odpovídajících $0^n$ a $s$ s pravděpodobností větší než $99{,}9$%. Obecněji, pokud nahradíme $k = n + 10$ hodnotou $k = n + r$ pro libovolnou volbu kladného celého čísla $r,$ pravděpodobnost, že vektory odpovídající $0^n$ a $s$ jsou v jádře $M$ samy, je alespoň $1 - 2^{-r}.$

Pomocí lineární algebry je možné efektivně vypočítat popis jádra $M$ modulo $2.$ Konkrétně to lze provést pomocí Gaussovy eliminace, která funguje při aritmetice modulo $2$ stejně jako s reálnými nebo komplexními čísly. Pokud jsou vektory odpovídající $0^n$ a $s$ v jádře $M$ samy, což nastává s vysokou pravděpodobností, můžeme $s$ odvodit z výsledků tohoto výpočtu.

Klasická obtížnost

Kolik dotazů potřebuje klasický dotazovací algoritmus k vyřešení Simonova problému? Odpověď je: obecně hodně.

Existují různá přesná tvrzení, která lze o klasické obtížnosti tohoto problému učinit, a zde je jedno z nich. Pokud máme jakýkoli pravděpodobnostní dotazovací algoritmus a tento algoritmus provede méně než $2^{n/2 - 1} - 1$ dotazů, což je počet dotazů exponenciální v $n,$ pak tento algoritmus selže při řešení Simonova problému s pravděpodobností alespoň $1/2.$

Někdy může být dokazování výsledků o nemožnosti velmi náročné, ale tento není příliš obtížný a lze ho dokázat elementární pravděpodobnostní analýzou. Zde však pouze stručně prozkoumáme základní intuici, která za ním stojí.

Snažíme se najít skrytý řetězec $s,$ ale dokud nezadáme funkci dotaz na dva řetězce se stejnou výstupní hodnotou, získáme o $s$ velmi omezené informace. Intuitivně řečeno, vše, co se dozvíme, je, že skrytý řetězec $s$ není exkluzivní disjunkcí (XOR) žádných dvou různých řetězců, na které jsme se dotázali. A pokud zadáme dotaz na méně než $2^{n/2 - 1} - 1$ řetězců, stále bude existovat mnoho možností pro $s,$ které jsme nevyloučili, protože nemáme dostatek párů řetězců, abychom to dokázali. Toto není formální důkaz, je to jen základní myšlenka.

Takže, shrnuto, Simonův algoritmus nám poskytuje pozoruhodnou výhodu kvantových algoritmů nad klasickými v rámci dotazovacího modelu. Konkrétně Simonův algoritmus řeší Simonův problém s počtem dotazů, který je lineární v počtu vstupních bitů $n$ naší funkce, zatímco jakýkoli klasický algoritmus, i pravděpodobnostní, potřebuje provést počet dotazů, který je exponenciální v $n,$ aby vyřešil Simonův problém s rozumnou pravděpodobností úspěchu.