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 obvodem 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 obvodů, 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$-qubitová 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ý obvod, 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 obvod 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 obvod o velikosti $O(n^2).$

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

3. Podobně jako v prvním kroku sestav obvod 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 obvody pro odhad fáze. Celkové náklady získaného obvodu 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 obvod pro $M_a^k$ nikoli opakováním obvodu 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 obvod 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 obvodem 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 obvodu 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.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

Například předpokládejme, že $r = 6$ a provedeme odhad fáze na $M_a$ s vlastním vektorem $\vert\psi_1\rangle$ s použitím $m = 5$ řídicích bitů. Nejlepší $5$-bitová aproximace $1/r = 1/6$ je $5/32$ a máme poměrně dobrou šanci (v tomto případě asi $68\%$) získat z odhadu fáze výsledek $y=5.$ Máme

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

a zaokrouhlení na nejbližší celé číslo dá $6,$ což je správná odpověď.

Na druhou stranu, pokud nepoužijeme dostatečnou přesnost, nemusíme dostat správnou odpověď. Například pokud vezmeme $m = 4$ řídicí qubity v odhadu fáze, můžeme získat nejlepší $4$-bitovou aproximaci $1/r = 1/6,$ což je $3/16.$ Výpočet převrácené hodnoty dá

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

a zaokrouhlení na nejbližší celé číslo dá nesprávnou odpověď $5.$

Takže kolik přesnosti potřebujeme, abychom dostali správnou odpověď? Víme, že řád $r$ je celé číslo, a intuitivně řečeno potřebujeme dostatečnou přesnost, abychom rozlišili $1/r$ od blízkých možností, včetně $1/(r+1)$ a $1/(r-1).$ Nejbližší číslo k $1/r,$ kterým se musíme zabývat, je $1/(r+1),$ a vzdálenost mezi těmito dvěma čísly je

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

Takže pokud se chceme ujistit, že nezaměníme $1/r$ za $1/(r+1),$ stačí použít dostatečnou přesnost, aby nejlepší aproximace $y/2^m$ k $1/r$ byla blíže k $1/r$ než k $1/(r+1).$ Pokud použijeme dostatečnou přesnost tak, aby

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

tedy aby chyba byla menší než polovina vzdálenosti mezi $1/r$ a $1/(r+1),$ pak $y/2^m$ bude blíže k $1/r$ než k jakékoli jiné možnosti, včetně $1/(r+1)$ a $1/(r-1).$

Můžeme si to ověřit následovně. Předpokládejme, že

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

pro $\varepsilon$ splňující

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

Když vezmeme převrácenou hodnotu, dostaneme

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

Maximalizací v čitateli a minimalizací ve jmenovateli můžeme ohraničit, jak daleko jsme od $r,$ následovně.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

Jsme méně než $1/2$ od $r,$ takže jak se očekávalo, dostaneme $r$ při zaokrouhlení.

Bohužel, protože zatím nevíme, jaké $r$ je, nemůžeme ho použít k tomu, abychom zjistili, kolik přesnosti potřebujeme. Co můžeme udělat místo toho, je využít skutečnost, že $r$ musí být menší než $N,$ abychom zajistili dostatečnou přesnost. Konkrétně, pokud použijeme dostatečnou přesnost, aby nejlepší aproximace $y/2^m$ k $1/r$ splňovala

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

pak budeme mít dostatečnou přesnost k správnému určení $r$ při výpočtu převrácené hodnoty. Volba $m = 2\operatorname{lg}(N)+1$ zajistí, že máme vysokou šanci získat odhad s touto přesností pomocí dříve popsané metody. (Volba $m = 2\operatorname{lg}(N)$ je dostatečná, pokud nám vyhovuje dolní mez $40\%$ na pravděpodobnost úspěchu.)

Obecné řešení

Jak jsme právě viděli, pokud máme vlastní vektor $\vert \psi_1 \rangle$ operace $M_a,$ můžeme zjistit $r$ pomocí odhadu fáze, pokud použijeme dostatek řídicích qubitů k dosažení dostatečné přesnosti. Bohužel není snadné získat vlastní vektor $\vert\psi_1\rangle,$ takže musíme přijít na to, jak postupovat.

Předpokládejme na chvíli, že postupujeme stejně jako výše, ale s vlastním vektorem $\vert\psi_k\rangle$ namísto $\vert\psi_1\rangle,$ pro libovolnou volbu $k\in\{0,\ldots,r-1\},$ o které chceme uvažovat. Výsledek, který z procedury odhadu fáze získáme, bude aproximace

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

Za předpokladu, že neznáme ani $k,$ ani $r,$ to nám může, ale nemusí umožnit identifikovat $r.$ Například pokud $k = 0,$ dostaneme aproximaci $y/2^m$ k $0,$ což nám bohužel nic neřekne. To je však neobvyklý případ; pro jiné hodnoty $k$ se budeme schopni o $r$ alespoň něco dozvědět.

Můžeme použít algoritmus známý jako algoritmus řetězových zlomků k převedení naší aproximace $y/2^m$ na blízké zlomky — včetně $k/r,$ pokud je aproximace dostatečně dobrá. Algoritmus řetězových zlomků zde nebudeme vysvětlovat. Místo toho uvádíme tvrzení známého faktu o tomto algoritmu.

Fact

Pro dané celé číslo $N\geq 2$ a reálné číslo $\alpha\in(0,1)$ existuje nejvýše jedna volba celých čísel $u,v\in\{0,\ldots,N-1\}$ s $v\neq 0$ a $\gcd(u,v)=1$ splňující $\vert \alpha - u/v\vert < \frac{1}{2N^2}.$ Pro daná $\alpha$ a $N$ najde algoritmus řetězových zlomků $u$ a $v,$ nebo oznámí, že neexistují. Tento algoritmus lze implementovat jako booleovský obvod o velikosti $O((\operatorname{lg}(N))^3).$

Pokud máme velmi přesnou aproximaci $y/2^m$ k $k/r$ a spustíme algoritmus řetězových zlomků pro $N$ a $\alpha = y/2^m,$ dostaneme $u$ a $v,$ jak jsou popsány ve faktu. Analýza tohoto faktu nám umožňuje usoudit, že

$$\frac{u}{v} = \frac{k}{r}.$$

Všimni si zejména, že se nemusíme nutně dozvědět $k$ a $r,$ dozvíme se pouze $k/r$ v základním tvaru.

Například, jak jsme si již všimli, z $k=0$ se nic nedozvíme. Ale to je jediná hodnota $k,$ kde k tomu dochází. Když $k$ je nenulové, může mít společné dělitele s $r,$ ale číslo $v,$ které získáme z algoritmu řetězových zlomků, musí přinejmenším dělit $r.$Není to zdaleka zřejmé, ale je pravda, že pokud máme schopnost zjistit $u$ a $v$ pro $u/v = k/r$ kde $k\in\{0,\ldots,r-1\}$ je zvoleno rovnoměrně náhodně, pak s velkou pravděpodobností dokážeme obnovit $r$ po pouhých několika vzorcích. Konkrétně, pokud náš odhad pro $r$ bude nejmenší společný násobek všech hodnot jmenovatele $v$, které pozorujeme, budeme mít pravdu s vysokou pravděpodobností. Intuitivně řečeno, některé hodnoty $k$ nejsou dobré, protože sdílejí společné dělitele s $r,$ a tyto společné dělitele jsou před námi skryty, když zjistíme $u$ a $v.$ Ale náhodné volby $k$ pravděpodobně nebudou dlouho skrývat dělitele $r$ a pravděpodobnost, že neuhodneme $r$ správně pomocí nejmenšího společného násobku pozorovaných jmenovatelů, klesá exponenciálně s počtem vzorků.

Zbývá se zabývat otázkou, jak získáme vlastní vektor $\vert\psi_k\rangle$ operátoru $M_a$, na kterém bychom spustili proceduru odhadu fáze. Jak se ukazuje, ve skutečnosti je nepotřebujeme vytvářet!

Místo toho spustíme proceduru odhadu fáze na stavu $\vert 1\rangle,$ čímž myslíme $n$-bitové binární kódování čísla $1,$ namísto vlastního vektoru $\vert\psi\rangle$ operátoru $M_a.$ Dosud jsme mluvili pouze o spouštění procedury odhadu fáze na konkrétním vlastním vektoru, ale nic nám nebrání spustit proceduru na vstupním stavu, který není vlastním vektorem $M_a,$ a přesně to zde děláme se stavem $\vert 1\rangle.$ (Toto není vlastní vektor $M_a$, pokud $a=1,$ což není volba, která by nás zajímala.)

Důvod pro volbu stavu $\vert 1\rangle$ namísto vlastního vektoru $M_a$ je ten, že platí následující rovnice.

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

Jeden způsob, jak tuto rovnici ověřit, je porovnat skalární součiny obou stran s každým stavem standardní báze, přičemž k vyhodnocení výsledků pro pravou stranu použijeme vzorce zmíněné dříve v lekci. V důsledku toho získáme přesně stejné výsledky měření, jako kdybychom zvolili $k\in\{0,\ldots,r-1\}$ rovnoměrně náhodně a použili $\vert\psi_k\rangle$ jako vlastní vektor.

Podrobněji si představ, že spustíme proceduru odhadu fáze se stavem $\vert 1\rangle$ namísto jednoho z vlastních vektorů $\vert\psi_k\rangle.$ Po provedení inverzní kvantové Fourierovy transformace nám to zanechá stav

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

kde

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle.$$

Vektor $\vert\gamma_k\rangle$ reprezentuje stav horních $m$ qubitů po provedení inverze kvantové Fourierovy transformace.

Takže díky tomu, že $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ je ortonormální množina, zjistíme, že měření horních $m$ qubitů dává aproximaci $y/2^m$ hodnoty $k/r$, kde $k\in\{0,\ldots,r-1\}$ je zvoleno rovnoměrně náhodně. Jak jsme již diskutovali, to nám umožňuje zjistit $r$ s vysokou mírou jistoty po několika nezávislých bězích, což byl náš cíl.

Celková cena

Cena implementace každé řízené unitární operace $M_a^k$ je $O(n^2).$ Řízených unitárních operací je $m$ a máme $m = O(n),$ takže celková cena řízených unitárních operací je $O(n^3).$ Kromě toho máme $m$ Hadamardových hradel (které přispívají $O(n)$ k ceně) a inverzní kvantová Fourierova transformace přispívá $O(n^2)$ k ceně. Cena řízených unitárních operací tedy dominuje ceně celé procedury — která je tedy $O(n^3).$

Kromě samotného kvantového obvodu je třeba provést několik klasických výpočtů. To zahrnuje výpočet mocnin $a^k$ v $\mathbb{Z}_N$ pro $k = 2, 4, 8, \ldots, 2^{m-1},$ které jsou potřeba k vytvoření řízených unitárních hradel, a také algoritmus řetězových zlomků, který převádí aproximace $\theta$ na zlomky. Tyto výpočty mohou být provedeny booleovskými obvody s celkovou cenou $O(n^3).$

Jako obvykle lze všechny tyto odhady zlepšit pomocí asymptoticky rychlých algoritmů; tyto odhady předpokládají, že používáme standardní algoritmy pro základní aritmetické operace.

Faktorizace pomocí nalezení řádu

Úplně poslední věc, kterou musíme probrat, je to, jak řešení problému nalezení řádu pomáhá při faktorizaci. Tato část je čistě klasická — nemá nic specificky společného s kvantovým počítáním.

Zde je základní myšlenka. Chceme faktorizovat číslo $N$ a můžeme to udělat rekurzivně. Konkrétně se můžeme zaměřit na úlohu rozštěpení $N,$ což znamená nalezení libovolných dvou celých čísel $b,c\geq 2$, pro která $N = bc.$ To není možné, pokud je $N$ prvočíslo, ale můžeme efektivně otestovat, zda je $N$ prvočíslo, pomocí algoritmu pro testování prvočíselnosti, a pokud $N$ není prvočíslo, pokusíme se ho rozštěpit. Jakmile $N$ rozštěpíme, můžeme jednoduše rekurzivně pokračovat s $b$ a $c$, dokud nebudou všechny naše faktory prvočísla a nezískáme rozklad $N$ na prvočísla.

Rozštěpení sudých čísel je snadné: jednoduše vypíšeme $2$ a $N/2.$

Je také snadné rozštěpit dokonalé mocniny, tedy čísla tvaru $N = s^j$ pro celá čísla $s,j\geq 2,$ jednoduše tak, že aproximujeme odmocniny $N^{1/2},$ $N^{1/3},$ $N^{1/4},$ a tak dále, a zkontrolujeme blízká celá čísla jako kandidáty na $s.$ Nemusíme jít dále než $\log(N)$ kroků v této posloupnosti, protože v tom bodě odmocnina klesne pod $2$ a neodhalí další kandidáty.

Je dobré, že obě tyto věci zvládneme, protože nalezení řádu nám nepomůže faktorizovat sudá čísla ani prvočíselné mocniny, kde číslo $s$ je prvočíslo. Pokud je však $N$ liché a není prvočíselnou mocninou, nalezení řádu nám umožní $N$ rozštěpit.

Probabilistický algoritmus pro rozštěpení lichého, složeného celého čísla N, které není prvočíselnou mocninou

1. Náhodně zvol $a\in\{2,\ldots,N-1\}.$

2. Vypočítej $d=\gcd(a,N).$

3. Pokud $d > 1$, pak vypiš $b = d$ a $c = N/d$ a skonči. Jinak pokračuj dalším krokem s vědomím, že $a\in\mathbb{Z}_N^{\ast}.$

4. Nechť $r$ je řád prvku $a$ modulo $N.$ (Zde potřebujeme nalezení řádu.)

5. Pokud je $r$ sudé:

   5.1 Vypočítej $x = a^{r/2} - 1$ modulo $N$
   5.2 Vypočítej $d = \gcd(x,N).$
   5.3 Pokud $d>1$, pak vypiš $b=d$ a $c = N/d$ a skonči.

6. Pokud bylo dosaženo tohoto bodu, algoritmus nenalezl dělitele $N.$

Běh tohoto algoritmu nemusí nalézt dělitele $N.$ Konkrétně k tomu dochází ve dvou situacích:

• Řád prvku $a$ modulo $N$ je lichý.
• Řád prvku $a$ modulo $N$ je sudý a $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1.$

Pomocí základní teorie čísel lze dokázat, že pro náhodnou volbu $a$ s pravděpodobností alespoň $1/2$ nenastane ani jedna z těchto událostí. Ve skutečnosti je pravděpodobnost, že nastane některá z těchto událostí, nejvýše $2^{-(m-1)}$ pro $m$ rovné počtu různých prvočíselných dělitelů $N,$ a proto je nutný předpoklad, že $N$ není prvočíselná mocnina. (Pro platnost tohoto faktu je rovněž vyžadován předpoklad, že $N$ je liché.)

To znamená, že každý běh má alespoň 50% šanci rozštěpit $N.$ Proto, pokud spustíme algoritmus $t$-krát a pokaždé náhodně zvolíme $a$, podaří se nám rozštěpit $N$ s pravděpodobností alespoň $1 - 2^{-t}.$

Základní myšlenka algoritmu je následující. Pokud máme volbu $a$, pro kterou je řád $r$ prvku $a$ modulo $N$ sudý, pak $r/2$ je celé číslo a můžeme uvažovat čísla

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

Pomocí vzorce $Z^2 - 1 = (Z+1)(Z-1)$ dojdeme k závěru, že

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

Nyní víme, že $a^r \; (\textrm{mod}\; N) = 1$ z definice řádu — což je jiný způsob, jak říci, že $N$ beze zbytku dělí $a^r - 1.$ To znamená, že $N$ beze zbytku dělí součin

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

Aby to platilo, všechny prvočíselné dělitele $N$ musí být také prvočíselnými děliteli $a^{r/2} - 1$ nebo $a^{r/2} + 1$ (nebo obou) — a pro náhodnou volbu $a$ se ukazuje, že je nepravděpodobné, aby všechny prvočíselné dělitele $N$ dělily jeden z členů a žádný nedělil druhý. V opačném případě, pokud některé z prvočíselných dělitelů $N$ dělí první člen a některé dělí druhý člen, budeme schopni nalézt netriviální dělitel $N$ výpočtem GCD s prvním členem.