Shorův algoritmus

Nyní obrátíme pozornost k problému faktorizace celých čísel a uvidíme, jak jej lze efektivně vyřešit na kvantovém počítači pomocí odhadu fáze. Algoritmus, který získáme, je Shorův algoritmus pro faktorizaci celých čísel. Shor svůj algoritmus nepopsal přímo v termínech odhadu fáze, ale je to přirozený a intuitivní způsob, jak vysvětlit jeho fungování.

Začneme diskusí o mezilehlém problému známém jako problém nalezení řádu a uvidíme, jak odhad fáze poskytuje řešení tohoto problému. Poté uvidíme, jak efektivní řešení problému nalezení řádu dává efektivní řešení problému faktorizace celých čísel. (Když řešení jednoho problému poskytuje řešení jiného problému tímto způsobem, říkáme, že se druhý problém redukuje na první — takže v tomto případě redukujeme faktorizaci celých čísel na nalezení řádu.) Tato druhá část Shorova algoritmu vůbec nevyužívá kvantové výpočty; je zcela klasická. Kvantové výpočty jsou potřeba pouze k vyřešení nalezení řádu.

Problém nalezení řádu

Základy teorie čísel

Pro vysvětlení problému nalezení řádu a jak jej lze vyřešit pomocí odhadu fáze, bude užitečné začít několika základními koncepty teorie čísel a zavést přitom praktickou notaci.

Pro začátek, pro libovolné kladné celé číslo $N$ definujeme množinu $\mathbb{Z}_N$ takto.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

Například $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ a tak dále.

Jsou to množiny čísel, ale můžeme je chápat jako víc než jen množiny. Konkrétně můžeme uvažovat o aritmetických operacích na $\mathbb{Z}_N$, jako je sčítání a násobení — a pokud se dohodneme, že výsledky vždy bereme modulo $N$ (to znamená, vydělíme číslem $N$ a jako výsledek vezmeme zbytek), při provádění těchto operací vždy zůstaneme v rámci této množiny. Dvě konkrétní operace sčítání a násobení, obě modulo $N,$ dělají z $\mathbb{Z}_N$ okruh, což je fundamentálně důležitý typ objektu v algebře.

Například $3$ a $5$ jsou prvky $\mathbb{Z}_7$ a pokud je spolu vynásobíme, dostaneme $3\cdot 5 = 15,$ což při dělení číslem $7$ dává zbytek $1.$ Někdy to vyjadřujeme následovně.

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

Můžeme ale také jednoduše napsat $3 \cdot 5 = 1,$ za předpokladu, že bylo jasně řečeno, že pracujeme v $\mathbb{Z}_7,$ jen abychom notaci co nejvíce zjednodušili.

Jako příklad zde jsou tabulky sčítání a násobení pro $\mathbb{Z}_6.$

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

Mezi $N$ prvky $\mathbb{Z}_N$ jsou speciální ty prvky $a\in\mathbb{Z}_N,$ které splňují $\gcd(a,N) = 1.$ Množina obsahující tyto prvky se často označuje hvězdičkou, takto.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

Pokud zaměříme pozornost na operaci násobení, množina $\mathbb{Z}_N^{\ast}$ tvoří grupu — konkrétně abelovskou grupu — což je další důležitý typ objektu v algebře. Je to základní fakt o těchto množinách (a konečných grupách obecně), že pokud si zvolíme libovolný prvek $a\in\mathbb{Z}_N^{\ast}$ a opakovaně násobíme $a$ samo sebou, vždy nakonec dostaneme číslo $1.$

Jako první příklad vezměme $N=6.$ Platí, že $5\in\mathbb{Z}_6^{\ast},$ protože $\gcd(5,6) = 1,$ a pokud vynásobíme $5$ samo sebou, dostaneme $1,$ jak potvrzuje tabulka výše.

$$5^2 = 1 \quad \text{(pracujeme v $\mathbb{Z}_6$)}$$

Jako druhý příklad vezměme $N = 21.$ Pokud projdeme čísla od $0$ do $20,$ ta, která mají GCD rovný $1$ s číslem $21,$ jsou následující.

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

Pro každý z těchto prvků je možné umocnit toto číslo na kladné celé číslo a dostat $1.$ Zde jsou nejmenší mocniny, pro které to funguje:

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

Přirozeně pracujeme v $\mathbb{Z}_{21}$ ve všech těchto rovnicích, což jsme se neobtěžovali psát — považujeme to za implicitní, abychom věci zbytečně nekomplikovali. V tom budeme pokračovat po zbytek této lekce.

Formulace problému a spojení s odhadem fáze

Nyní můžeme formulovat problém nalezení řádu.

Nalezení řádu

Vstup: kladná celá čísla $N$ a $a$ splňující $\gcd(N,a) = 1$
Výstup: nejmenší kladné celé číslo $r$ takové, že $a^r \equiv 1$ $(\textrm{mod } N)$

Alternativně, v notaci, kterou jsme právě zavedli výše, je nám dáno $a \in \mathbb{Z}_N^{\ast}$ a hledáme nejmenší kladné celé číslo $r$ takové, že $a^r = 1.$ Toto číslo $r$ se nazývá řád prvku $a$ modulo $N.$

Pro spojení problému nalezení řádu s odhadem fáze se zamysleme nad operací definovanou na systému, jehož klasické stavy odpovídají $\mathbb{Z}_N,$ kde násobíme pevným prvkem $a\in\mathbb{Z}_N^{\ast}.$

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(pro každé $x\in\mathbb{Z}_N$)}$$

Pro upřesnění, násobení provádíme v $\mathbb{Z}_N,$ takže je implicitní, že uvnitř ketu na pravé straně rovnice bereme součin modulo $N.$

Například pokud vezmeme $N = 15$ a $a=2,$ pak působení $M_2$ na standardní bázi $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ je následující.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

Toto je unitární operace za předpokladu, že $\gcd(a,N)=1;$ přeuspořádává prvky standardní báze $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ takže jako matice je to permutační matice. Z její definice je zřejmé, že tato operace je deterministická, a jednoduchý způsob, jak vidět, že je invertibilní, je zamyslet se nad řádem $r$ prvku $a$ modulo $N$ a uvědomit si, že inverze $M_a$ je $M_a^{r-1}.$

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

Existuje i jiný způsob, jak přemýšlet o inverzi, který nevyžaduje žádnou znalost $r$ (které koneckonců teprve chceme vypočítat). Pro každý prvek $a\in\mathbb{Z}_N^{\ast}$ vždy existuje jedinečný prvek $b\in\mathbb{Z}_N^{\ast},$ který splňuje $ab=1.$ Tento prvek $b$ označujeme $a^{-1}$ a lze ho efektivně spočítat; rozšíření Euklidova algoritmu pro GCD to provede s náklady kvadratickými v $\operatorname{lg}(N).$ A tedy

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

Operace $M_a$ je tedy jak deterministická, tak invertibilní. To znamená, že je popsána permutační maticí, a je tedy unitární.

Nyní se zamysleme nad vlastními vektory a vlastními hodnotami operace $M_a,$ za předpokladu, že $a\in\mathbb{Z}_N^{\ast}.$ Jak jsme právě ukázali, tento předpoklad nám říká, že $M_a$ je unitární.

Existuje $N$ vlastních hodnot $M_a,$ případně včetně stejné vlastní hodnoty opakované vícekrát, a obecně existuje určitá volnost při výběru odpovídajících vlastních vektorů — ale nemusíme se zabývat všemi možnostmi. Začněme jednoduše a identifikujme jen jeden vlastní vektor $M_a.$

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

Číslo $r$ je řád $a$ modulo $N,$ zde i ve zbytku celé lekce. Vlastní hodnota přiřazená tomuto vlastnímu vektoru je $1,$ protože se nezmění, když násobíme číslem $a.$

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

To se děje proto, že $a^r = 1,$ takže každý stav standardní báze $\vert a^k \rangle$ se posune na $\vert a^{k+1} \rangle$ pro $k\leq r-1$ a $\vert a^{r-1} \rangle$ se posune zpět na $\vert 1\rangle.$ Neformálně řečeno, je to jako bychom pomalu míchali $\vert \psi_0 \rangle,$ ale ten je už úplně promíchaný, takže se nic nezmění.

Zde je další příklad vlastního vektoru $M_a.$ Tento je v kontextu nalezení řádu a odhadu fáze zajímavější.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

Alternativně můžeme tento vektor zapsat pomocí sumy následovně.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

Zde vidíme, jak se přirozeně objevuje komplexní číslo $\omega_r = e^{2\pi i/r}$ díky způsobu, jakým funguje násobení číslem $a$ modulo $N.$ Tentokrát je odpovídající vlastní hodnota $\omega_r.$ Abychom to viděli, můžeme nejprve provést následující výpočet.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

Potom, protože $\omega_r^{-r} = 1 = \omega_r^0$ a $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle,$ vidíme, že

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

takže $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle.$

Stejným postupem můžeme identifikovat další páry vlastní vektor/vlastní hodnota pro $M_a.$ Pro libovolnou volbu $j\in\{0,\ldots,r-1\}$ platí, že

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

je vlastní vektor $M_a,$ jehož odpovídající vlastní hodnota je $\omega_r^j.$

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

Existují i další vlastní vektory $M_a,$ ale nemusíme se jimi zabývat — zaměříme se výhradně na vlastní vektory $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle,$ které jsme právě identifikovali.

Nalezení řádu pomocí odhadu fáze

K vyřešení problému nalezení řádu pro danou volbu $a\in\mathbb{Z}_N^{\ast}$ můžeme aplikovat proceduru odhadu fáze na operaci $M_a.$

K tomu potřebujeme efektivně implementovat kvantovým Circuit nejen $M_a,$ ale také $M_a^2,$ $M_a^4,$ $M_a^8$ a tak dále, tak daleko, jak je potřeba k získání dostatečně přesného odhadu z procedury odhadu fáze. Zde vysvětlíme, jak to lze provést, a později přesně zjistíme, kolik přesnosti je potřeba.

Začněme samotnou operací $M_a.$ Přirozeně, protože pracujeme s modelem kvantových Circuit, budeme k zakódování čísel mezi $0$ a $N-1$ používat binární zápis. Největší číslo, které potřebujeme zakódovat, je $N-1,$ takže počet bitů, které potřebujeme, je

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

Například pokud $N = 21,$ máme $n = \operatorname{lg}(N-1) = 5.$ Takto vypadá zakódování prvků $\mathbb{Z}_{21}$ jako binárních řetězců délky $5.$

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

A nyní přesná definice toho, jak je $M_a$ definováno jako $n$-Qubit operace.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

Jde o to, že ačkoli nás zajímá pouze to, jak $M_a$ funguje pro $\vert 0\rangle,\ldots,\vert N-1\rangle,$ musíme specifikovat, jak funguje pro zbývajících $2^n - N$ stavů standardní báze — a musíme to udělat způsobem, který nám stále dá unitární operaci. Definování $M_a$ tak, aby s těmito zbývajícími stavy standardní báze nic nedělalo, toto splňuje.

Pomocí algoritmů pro násobení a dělení celých čísel diskutovaných v předchozí lekci, spolu s metodologií pro reverzibilní implementace bez odpadu, můžeme sestavit kvantový Circuit, který provádí $M_a$ pro libovolnou volbu $a\in\mathbb{Z}_N^{\ast},$ s náklady $O(n^2).$ Zde je jeden způsob, jak to lze udělat.

1. Sestav Circuit pro provedení operace

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

   kde

   $$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

   pomocí metody popsané v předchozí lekci. Tím získáme Circuit o velikosti $O(n^2).$

2. Prohoď dva $n$-Qubit systémy pomocí $n$ swap Gate pro individuální prohození Qubitů.

3. Podobně jako v prvním kroku sestav Circuit pro operaci

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

   kde $a^{-1}$ je inverze $a$ v $\mathbb{Z}_N^{\ast}.$

Inicializací spodních $n$ Qubitů a složením tří kroků získáme tuto transformaci:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

Metoda vyžaduje pracovní Qubity, ale ty jsou na konci vráceny do svého inicializovaného stavu, což nám umožňuje použít tyto Circuit pro odhad fáze. Celkové náklady získaného Circuit jsou $O(n^2).$

Pro provedení $M_a^2,$ $M_a^4,$ $M_a^8$ a tak dále můžeme použít přesně stejnou metodu, jen nahradíme $a$ za $a^2,$ $a^4,$ $a^8$ a tak dále jako prvky $\mathbb{Z}_N^{\ast}.$ To znamená, že pro jakoukoli mocninu $k,$ kterou zvolíme, můžeme vytvořit Circuit pro $M_a^k$ nikoli opakováním Circuit pro $M_a$ celkem $k$-krát, ale místo toho vypočteme $b = a^k \in \mathbb{Z}_N^{\ast}$ a poté použijeme Circuit pro $M_b.$

Výpočet mocnin $a^k \in \mathbb{Z}_N$ je problém modulární exponenciace zmíněný v předchozí lekci. Tento výpočet lze provést klasicky pomocí algoritmu pro modulární exponenciaci zmíněného v předchozí lekci (v teorii výpočetních čísel často nazývaného algoritmus mocnění). Ve skutečnosti potřebujeme pouze mocniny $a$ o základu $2,$ konkrétně $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast},$ a tyto mocniny můžeme získat iterativním umocňováním na druhou $m-1$ krát. Každé umocnění na druhou lze provést booleovským Circuit o velikosti $O(n^2).$

V podstatě zde efektivně přenášíme problém iterování $M_a$ až $2^{m-1}$ krát na efektivní klasický výpočet. A je to šťastná okolnost, že je to možné! Pro libovolnou volbu kvantového Circuit v problému odhadu fáze to pravděpodobně není možné — a v takovém případě výsledné náklady na odhad fáze rostou exponenciálně s počtem řídicích Qubitů $m.$

Řešení s výhodným vlastním vektorem

Abychom pochopili, jak můžeme vyřešit problém nalezení řádu pomocí odhadu fáze, začněme předpokladem, že spustíme proceduru odhadu fáze na operaci $M_a$ s použitím vlastního vektoru $\vert\psi_1\rangle.$ Získat tento vlastní vektor není snadné, jak se ukáže, takže toto nebude konec příběhu — ale je užitečné zde začít.

Vlastní hodnota $M_a$ odpovídající vlastnímu vektoru $\vert \psi_1\rangle$ je

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

To znamená, $\omega_r = e^{2\pi i \theta}$ pro $\theta = 1/r.$ Takže pokud spustíme proceduru odhadu fáze na $M_a$ s použitím vlastního vektoru $\vert\psi_1\rangle,$ získáme aproximaci $1/r.$ Výpočtem převrácené hodnoty budeme schopni zjistit $r$ — za předpokladu, že naše aproximace je dostatečně dobrá.

Podrobněji, když spustíme proceduru odhadu fáze s $m$ řídicími Qubity, získáme číslo $y\in\{0,\ldots,2^m-1\}.$ Poté vezmeme $y/2^m$ jako odhad pro $\theta,$ což je v našem případě $1/r.$ Abychom z této aproximace zjistili, co je $r,$ přirozená věc je vypočítat převrácenou hodnotu naší aproximace a zaokrouhlit na nejbližší celé číslo.

undefined