Algoritmo ni Shor

Ngayon ay itutuon natin ang ating pansin sa problema ng integer factorization, at makikita kung paano ito malulutas nang mahusay sa isang quantum computer gamit ang phase estimation. Ang algorithm na makukuha natin ay ang algoritmo ni Shor para sa integer factorization. Hindi inilalarawan ni Shor ang kanyang algorithm sa pamamagitan ng phase estimation, ngunit ito ay isang natural at madaling maintindihang paraan upang ipaliwanag kung paano ito gumagana.

Magsisimula tayo sa pamamagitan ng pagtalakay sa isang intermediate na problema na kilala bilang order-finding problem at makikita kung paano nagbibigay ng solusyon dito ang phase estimation. Makikita rin natin kung paano ang isang mahusay na solusyon sa order-finding problem ay nagbibigay sa atin ng mahusay na solusyon sa integer factorization problem. (Kapag ang solusyon sa isang problema ay nagbibigay ng solusyon sa isa pang problema tulad nito, sinasabi natin na ang pangalawang problema ay nire-reduce sa una — kaya sa kasong ito ay nire-reduce natin ang integer factorization sa order finding.) Ang pangalawang bahagi ng algoritmo ni Shor ay hindi gumagamit ng quantum computing; ito ay ganap na klasikal. Kailangan lamang ang quantum computing para malutas ang order finding.

Ang order-finding problem

Ilang pangunahing number theory

Upang maipaliwanag ang order-finding problem at kung paano ito malulutas gamit ang phase estimation, magiging kapaki-pakinabang ang magsimula sa ilang pangunahing konsepto ng number theory, at magpakilala ng ilang maginhawang notasyon habang nagpapatuloy.

Una, para sa anumang positibong integer na $N,$ tukuyin ang set na $\mathbb{Z}_N$ tulad nito.

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

Halimbawa, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ at iba pa.

Ito ay mga set ng mga numero, ngunit maaari nating isipin ang mga ito nang higit pa sa mga set. Sa partikular, maaari tayong mag-isip tungkol sa mga operasyong aritmetika sa $\mathbb{Z}_N$ tulad ng pagdaragdag at pagpaparami — at kung sumasang-ayon tayong palaging kumuha ng ating mga sagot modulo $N$ (iyon ay, hatiin sa $N$ at kunin ang natitirang bilang ang resulta), palagi tayong mananatili sa loob ng set na ito habang ginagawa ang mga operasyong ito. Ang dalawang partikular na operasyon ng pagdaragdag at pagpaparami, na parehong kinukuha modulo $N,$ ay ginagawang ring ang $\mathbb{Z}_N$, na isang pundamental na mahalagang uri ng bagay sa algebra.

Halimbawa, ang $3$ at $5$ ay mga elemento ng $\mathbb{Z}_7,$ at kung pararamihin natin ang mga ito nang magkasama makukuha natin ang $3\cdot 5 = 15,$ na nag-iiwan ng natitirang $1$ kapag hinati sa $7.$ Minsan ipinapahayag natin ito tulad ng sumusunod.

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

Ngunit maaari rin tayong simpleng isulat ang $3 \cdot 5 = 1,$ kung malinaw na ang ating pinagtatarabahong $\mathbb{Z}_7,$ upang panatilihing simple ang ating notasyon hangga't maaari.

Bilang halimbawa, narito ang mga talahanayan ng pagdaragdag at pagpaparami para sa $\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}$$

Sa mga $N$ elemento ng $\mathbb{Z}_N,$ ang mga elemento na $a\in\mathbb{Z}_N$ na sumasaklaw sa $\gcd(a,N) = 1$ ay espesyal. Madalas ang set na naglalaman ng mga elementong ito ay tinutukoy ng bituin tulad nito.

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

Kung itutuon natin ang ating pansin sa operasyon ng pagpaparami, ang set na $\mathbb{Z}_N^{\ast}$ ay bumubuo ng isang grupo — partikular na isang abelian group — na isa pang mahalagang uri ng bagay sa algebra. Isa itong pangunahing katotohanan tungkol sa mga set na ito (at sa mga finite group sa pangkalahatan), na kung pumili tayo ng anumang elemento $a\in\mathbb{Z}_N^{\ast}$ at paulit-ulit na pararamihin ang $a$ sa sarili nito, palagi tayong makakakuha ng bilang na $1$ sa kalaunan.

Para sa isang unang halimbawa, kunin natin ang $N=6.$ Mayroon tayong $5\in\mathbb{Z}_6^{\ast}$ dahil $\gcd(5,6) = 1,$ at kung pararamihin natin ang $5$ sa sarili nito makukuha natin ang $1,$ tulad ng kinukumpirma ng talahanayan sa itaas.

$$5^2 = 1 \quad \text{(nagtatrabaho sa loob ng $\mathbb{Z}_6$)}$$

Bilang ikalawang halimbawa, kunin natin ang $N = 21.$ Kung dadaanan natin ang mga numero mula $0$ hanggang $20,$ ang mga may GCD na katumbas ng $1$ kasama ang $21$ ay ang mga sumusunod.

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

Para sa bawat isa sa mga elementong ito, posibleng itaas ang bilang na iyon sa isang positibong integer na kapangyarihan upang makuha ang $1.$ Narito ang pinakamaliit na kapangyarihan kung saan gumagana ito:

$$\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}$$

Natural na nagtatrabaho tayo sa loob ng $\mathbb{Z}_{21}$ para sa lahat ng mga ekwasyong ito, na hindi na natin isinusulat — itinuturing natin itong implicit upang maiwasan ang kumplikasyon. Patuloy nating gagawin iyon sa buong natitirang bahagi ng aralin.

Pahayag ng problema at koneksyon sa phase estimation

Ngayon ay maaari na nating sabihin ang order-finding problem.

Order finding

Input: positibong mga integer $N$ at $a$ na sumasaklaw sa $\gcd(N,a) = 1$
Output: ang pinakamaliit na positibong integer $r$ na $a^r \equiv 1$ $(\textrm{mod } N)$

Bilang kahalili, sa mga tuntunin ng notasyong ipinakilala natin sa itaas, binibigyan tayo ng $a \in \mathbb{Z}_N^{\ast},$ at naghahanap tayo ng pinakamaliit na positibong integer $r$ na $a^r = 1.$ Ang bilang na $r$ na ito ay tinatawag na order ng $a$ modulo $N.$

Upang maikonekta ang order-finding problem sa phase estimation, pag-isipan natin ang operasyon na tinukoy sa isang sistema na ang mga klasikal na estado ay katumbas ng $\mathbb{Z}_N,$ kung saan pinaraparami natin ng isang nakapirming elemento na $a\in\mathbb{Z}_N^{\ast}.$

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(para sa bawat $x\in\mathbb{Z}_N$)}$$

Upang maging malinaw, ginagawa natin ang pagpaparami sa $\mathbb{Z}_N,$ kaya implicit na kinukuha natin ang produkto modulo $N$ sa loob ng ket sa kanan ng ekwasyon.

Halimbawa, kung kunin natin ang $N = 15$ at $a=2,$ ang aksyon ng $M_2$ sa standard basis na $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ ay ang sumusunod.

$$\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}$$

Ito ay isang unitary operation kung $\gcd(a,N)=1;$ ini-shuffle nito ang mga elemento ng standard basis na $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ kaya bilang isang matrix ito ay isang permutation matrix. Malinaw mula sa kahulugan nito na ang operasyong ito ay deterministic, at isang simpleng paraan upang makita na ito ay invertible ay ang pag-isip sa order $r$ ng $a$ modulo $N,$ at kilalanin na ang inverse ng $M_a$ ay $M_a^{r-1}.$

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

May isa pang paraan upang pag-isipan ang inverse na hindi nangangailangan ng anumang kaalaman sa $r$ (na, pagkatapos ng lahat, ay ang ating sinusubukang kalkulahin). Para sa bawat elemento $a\in\mathbb{Z}_N^{\ast}$ palaging may natatanging elemento $b\in\mathbb{Z}_N^{\ast}$ na sumasaklaw sa $ab=1.$ Tinutukoy natin ang elementong $b$ na ito bilang $a^{-1},$ at maaari itong kalkulahin nang mahusay; ang isang extension ng GCD algorithm ni Euclid ay ginagawa ito na may gastos na quadratic sa $\operatorname{lg}(N).$ At kaya

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

Kaya, ang operasyon na $M_a$ ay parehong deterministic at invertible. Iyon ay nagpapahiwatig na inilarawan ito ng isang permutation matrix, at samakatuwid ay unitary.

Ngayon ay pag-isipan natin ang mga eigenvector at eigenvalue ng operasyon na $M_a,$ sa pag-aakala na $a\in\mathbb{Z}_N^{\ast}.$ Tulad ng pinagtatalunan lamang, sinasabi sa atin ng pagpapalagay na ito na ang $M_a$ ay unitary.

Mayroong $N$ eigenvalue ng $M_a,$ posibleng kasama ang parehong eigenvalue na paulit-ulit nang maraming beses, at sa pangkalahatan ay may ilang kalayaan sa pagpili ng mga katumbas na eigenvector — ngunit hindi natin kailangang mag-alala sa lahat ng mga posibilidad. Magsimula tayo nang simple at tukuyin lamang ang isang eigenvector ng $M_a.$

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

Ang bilang na $r$ ay ang order ng $a$ modulo $N,$ dito at sa buong natitirang bahagi ng aralin. Ang eigenvalue na nauugnay sa eigenvector na ito ay $1$ dahil hindi ito nagbabago kapag pinarami ng $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$$

Nangyayari ito dahil $a^r = 1,$ kaya ang bawat standard basis state na $\vert a^k \rangle$ ay inililipat sa $\vert a^{k+1} \rangle$ para sa $k\leq r-1,$ at ang $\vert a^{r-1} \rangle$ ay inilipat pabalik sa $\vert 1\rangle.$ Sa impormal na pagsasalita, parang dahan-dahan nating hinahalo ang $\vert \psi_0 \rangle,$ ngunit ito ay ganap nang nahalo kaya walang nagbabago.

Narito ang isa pang halimbawa ng eigenvector ng $M_a.$ Ito ay mas kawili-wili sa konteksto ng order finding at phase estimation.

$$\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}}$$

Bilang kahalili, maaari nating isulat ang vector na ito gamit ang isang summation tulad ng sumusunod.

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

Dito nakikita natin ang complex number na $\omega_r = e^{2\pi i/r}$ na lumilitaw nang natural, dahil sa paraan ng pagpaparami ng $a$ modulo $N.$ Sa pagkakataong ito ang katumbas na eigenvalue ay $\omega_r.$ Upang makita ito, maaari tayong unang kalkulahin tulad ng sumusunod.

$$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$$

Pagkatapos, dahil $\omega_r^{-r} = 1 = \omega_r^0$ at $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle,$ makikita natin na

$$\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,$$

kaya $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle.$

Gamit ang parehong pangangatwiran, maaari tayong tumukoy ng mga karagdagang pares ng eigenvector/eigenvalue para sa $M_a.$ Para sa anumang pagpili ng $j\in\{0,\ldots,r-1\}$ mayroon tayong

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

na isang eigenvector ng $M_a$ na ang katumbas na eigenvalue ay $\omega_r^j.$

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

Mayroong iba pang mga eigenvector ng $M_a,$ ngunit hindi na natin kailangang pag-abalahan ang mga ito — magtutuon lamang tayo sa mga eigenvector na $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ na ating natukoy.

Order finding sa pamamagitan ng phase estimation

Upang malutas ang order-finding problem para sa isang partikular na pagpili ng $a\in\mathbb{Z}_N^{\ast},$ maaari nating ilapat ang pamamaraan ng phase estimation sa operasyon na $M_a.$

Upang magawa ito, kailangan nating ipatupad nang mahusay hindi lamang ang $M_a$ sa isang quantum circuit, kundi pati na rin ang $M_a^2,$ $M_a^4,$ $M_a^8,$ at iba pa, na pumupunta hanggang saan kinakailangan upang makakuha ng sapat na tumpak na pagtatantya mula sa pamamaraan ng phase estimation. Dito ay ipapaliwanag natin kung paano ito maaaring gawin, at malalaman natin kung gaano kalawak ang katumpakan na kailangan sa ibang pagkakataon.

Magsimula tayo sa operasyon na $M_a$ mismo. Natural, dahil nagtatrabaho tayo sa quantum circuit model, gagamit tayo ng binary notation upang i-encode ang mga numero sa pagitan ng $0$ at $N-1.$ Ang pinakamalaking numero na kailangan nating i-encode ay $N-1,$ kaya ang bilang ng mga bit na kailangan natin ay

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

Halimbawa, kung $N = 21$ mayroon tayong $n = \operatorname{lg}(N-1) = 5.$ Narito ang hitsura ng pag-encode ng mga elemento ng $\mathbb{Z}_{21}$ bilang mga binary string na may haba na $5.$

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

At ngayon, narito ang isang tumpak na kahulugan ng kung paano tinukoy ang $M_a$ bilang isang $n$-qubit na operasyon.

$$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}$$

Ang punto ay kahit na nagmamalasakit lamang tayo sa kung paano gumagana ang $M_a$ para sa $\vert 0\rangle,\ldots,\vert N-1\rangle,$ kailangan nating tukuyin kung paano ito gumagana para sa natitirang $2^n - N$ standard basis state — at kailangan nating gawin ito sa paraang nagbibigay pa rin sa atin ng unitary operation. Ang pagtukoy sa $M_a$ upang hindi ito gumawa ng anuman sa mga natitirang standard basis state ay nagagawa ito.

Gamit ang mga algorithm para sa integer multiplication at division na tinalakay sa nakaraang aralin, kasama ang pamamaraan para sa mga reversible, garbage-free na implementasyon ng mga ito, maaari tayong bumuo ng quantum circuit na gumaganap ng $M_a,$ para sa anumang pagpili ng $a\in\mathbb{Z}_N^{\ast},$ na may gastos na $O(n^2).$ Narito ang isang paraan na maaaring gawin ito.

1. Bumuo ng circuit para sa pagsasagawa ng operasyon

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

   kung saan

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

   gamit ang pamamaraang inilarawan sa nakaraang aralin. Nagbibigay ito sa atin ng circuit na may laki na $O(n^2).$

2. I-swap ang dalawang $n$-qubit na sistema gamit ang $n$ swap gate upang i-swap ang mga qubit nang isa-isa.

3. Katulad ng unang hakbang, bumuo ng circuit para sa operasyon

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

   kung saan $a^{-1}$ ang inverse ng $a$ sa $\mathbb{Z}_N^{\ast}.$

Sa pamamagitan ng pag-initialize ng ibabang $n$ qubit at pagsasama ng tatlong hakbang, nakukuha natin ang transformasyong ito:

$$\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$$

Ang pamamaraan ay nangangailangan ng mga workspace qubit, ngunit ibinabalik ang mga ito sa kanilang initialized na estado sa katapusan, na nagbibigay-daan sa atin na gamitin ang mga circuit na ito para sa phase estimation. Ang kabuuang gastos ng circuit na ating makukuha ay $O(n^2).$

Upang maisagawa ang $M_a^2,$ $M_a^4,$ $M_a^8,$ at iba pa, maaari tayong gumamit ng eksaktong parehong pamamaraan, maliban na pinapalitan natin ang $a$ ng $a^2,$ $a^4,$ $a^8,$ at iba pa, bilang mga elemento ng $\mathbb{Z}_N^{\ast}.$ Iyon ay, para sa anumang kapangyarihan na $k$ na ating pipiliin, maaari tayong lumikha ng circuit para sa $M_a^k$ hindi sa pamamagitan ng pag-ulit ng $k$ beses ng circuit para sa $M_a,$ kundi sa pamamagitan ng pagkalkula ng $b = a^k \in \mathbb{Z}_N^{\ast}$ at pagkatapos ay paggamit ng circuit para sa $M_b.$

Ang pagkalkula ng mga kapangyarihan na $a^k \in \mathbb{Z}_N$ ay ang modular exponentiation na problema na binanggit sa nakaraang aralin. Ang kalkulasyong ito ay maaaring gawin nang klasikal, gamit ang algorithm para sa modular exponentiation na binanggit sa nakaraang aralin (madalas na tinatawag na power algorithm sa computational number theory). Sa katunayan, kailangan lamang natin ang power-of-2 na mga kapangyarihan ng $a,$ partikular na $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast},$ at maaari nating makuha ang mga kapangyarihang ito sa pamamagitan ng paulit-ulit na pagpaparami sa sarili nang $m-1$ beses. Ang bawat squaring ay maaaring isagawa ng isang Boolean circuit na may laki na $O(n^2).$

Sa esensya, ang epektibong ginagawa natin dito ay inililipat ang problema ng pag-ulit ng $M_a$ nang hanggang $2^{m-1}$ beses sa isang mahusay na klasikal na kalkulasyon. At magandang kapalaran na posible ito! Para sa isang arbitrary na pagpili ng quantum circuit sa problema ng phase estimation, malamang na hindi ito magiging posible — at sa kasong iyon ang nagresultang gastos para sa phase estimation ay lumalaki nang exponentially sa bilang ng mga control qubit na $m.$

Solusyon sa pag-aakalang may maginhawang eigenvector

Upang maunawaan kung paano natin malulutas ang order-finding problem gamit ang phase estimation, magsimula tayo sa pag-aakalang nagpapatakbo tayo ng pamamaraan ng phase estimation sa operasyon na $M_a$ gamit ang eigenvector na $\vert\psi_1\rangle.$ Ang pagkuha ng eigenvector na ito ay hindi madali, gaya ng makikita, kaya hindi ito magiging katapusan ng kuwento — ngunit kapaki-pakinabang na magsimula dito.

Ang eigenvalue ng $M_a$ na katumbas ng eigenvector na $\vert \psi_1\rangle$ ay

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

Iyon ay, $\omega_r = e^{2\pi i \theta}$ para sa $\theta = 1/r.$ Kaya, kung magpapatakbo tayo ng pamamaraan ng phase estimation sa $M_a$ gamit ang eigenvector na $\vert\psi_1\rangle,$ makakakuha tayo ng pagtatantya sa $1/r.$ Sa pamamagitan ng pagkalkula ng reciprocal malalaman natin ang $r$ — kung sapat ang katumpakan ng ating pagtatantya.

Sa mas detalyadong pagsasalita, kapag nagpapatakbo tayo ng pamamaraan ng phase estimation gamit ang $m$ control qubit, ang nakukuha natin ay isang bilang na $y\in\{0,\ldots,2^m-1\}.$ Pagkatapos ay kinukuha natin ang $y/2^m$ bilang hula para sa $\theta,$ na $1/r$ sa kasong ito. Upang malaman kung ano ang $r$ mula sa pagtatantyaang ito, ang natural na gawin ay kalkulahin ang reciprocal ng ating pagtatantya at i-round sa pinakamalapit na integer.

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

Halimbawa, ipagpalagay natin na $r = 6$ at nagsasagawa tayo ng phase estimation sa $M_a$ kasama ang eigenvector na $\vert\psi_1\rangle$ gamit ang $m = 5$ control bit. Ang pinakamahusay na $5$-bit na pagtatantya sa $1/r = 1/6$ ay $5/32,$ at mayroon tayong medyo magandang pagkakataon (mga $68\%$ sa kasong ito) na makuha ang resulta na $y=5$ mula sa phase estimation. Mayroon tayo

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

at ang pag-round sa pinakamalapit na integer ay nagbibigay ng $6,$ na siyang tamang sagot.

Sa kabilang banda, kung hindi tayo gumamit ng sapat na katumpakan, maaaring hindi tayo makakuha ng tamang sagot. Halimbawa, kung kukunin natin ang $m = 4$ control qubit sa phase estimation, maaari tayong makuha ang pinakamahusay na $4$-bit na pagtatantya sa $1/r = 1/6,$ na $3/16.$ Ang pagkuha ng reciprocal ay nagbubunga ng

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

at ang pag-round sa pinakamalapit na integer ay nagbibigay ng maling sagot na $5.$

Kaya gaano karaming katumpakan ang kailangan natin upang makuha ang tamang sagot? Alam natin na ang order $r$ ay isang integer, at sa intuitive na pagsasalita ang kailangan natin ay sapat na katumpakan upang matukoy ang $1/r$ mula sa mga kalapit na posibilidad, kasama ang $1/(r+1)$ at $1/(r-1).$ Ang pinakamalapit na bilang sa $1/r$ na dapat nating pangalagaan ay $1/(r+1),$ at ang distansya sa pagitan ng dalawang bilang na ito ay

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

Kaya, kung nais nating tiyaking hindi natin ipagkakamali ang $1/r$ para sa $1/(r+1),$ sapat na ang gumamit ng sapat na katumpakan upang matiyak na ang pinakamahusay na pagtatantya na $y/2^m$ sa $1/r$ ay mas malapit sa $1/r$ kaysa sa $1/(r+1).$ Kung gagamit tayo ng sapat na katumpakan upang matiyak na

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

upang ang error ay mas mababa sa kalahati ng distansya sa pagitan ng $1/r$ at $1/(r+1),$ kung gayon ang $y/2^m$ ay magiging mas malapit sa $1/r$ kaysa sa anumang ibang posibilidad, kasama ang $1/(r+1)$ at $1/(r-1).$

Maaari nating i-double-check ito tulad ng sumusunod. Ipagpalagay na

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

para sa $\varepsilon$ na sumasaklaw sa

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

Kapag kinuha natin ang reciprocal nakukuha natin

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

Sa pamamagitan ng pag-maximize sa numerator at pag-minimize sa denominator, maaari nating limitahan kung gaano kalayo tayo mula sa $r$ tulad ng sumusunod.

$$\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}$$

Mas mababa tayo sa $1/2$ mula sa $r,$ kaya tulad ng inaasahan makukuha natin ang $r$ kapag nag-round tayo.

Sa kasamaang-palad, dahil hindi pa natin alam kung ano ang $r,$ hindi natin ito magagamit upang sabihin sa atin kung gaano karaming katumpakan ang kailangan natin. Ang maaari nating gawin sa halip ay gamitin ang katotohanang ang $r$ ay dapat na mas mababa sa $N$ upang matiyak na ginagamit natin ang sapat na katumpakan. Sa partikular, kung gagamit tayo ng sapat na katumpakan upang matiyak na ang pinakamahusay na pagtatantya na $y/2^m$ sa $1/r$ ay sumasaklaw sa

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

kung gayon magkakaroon tayo ng sapat na katumpakan upang tama ang pagdetermina sa $r$ kapag kinuha natin ang reciprocal. Ang pagkuha ng $m = 2\operatorname{lg}(N)+1$ ay tinitiyak na mayroon tayong mataas na pagkakataon na makakuha ng pagtatantya na may katumpakang ito gamit ang pamamaraang inilarawan dati. (Ang pagkuha ng $m = 2\operatorname{lg}(N)$ ay sapat kung komportable tayo sa lower bound na 40% sa probabilidad ng tagumpay.)

Pangkalahatang solusyon

Tulad ng ating nakita, kung mayroon tayo ang eigenvector na $\vert \psi_1 \rangle$ ng $M_a,$ maaari nating matutunan ang $r$ sa pamamagitan ng phase estimation, hangga't gumagamit tayo ng sapat na mga control qubit upang gawin ito nang may sapat na katumpakan. Sa kasamaang-palad, hindi madaling makuha ang eigenvector na $\vert\psi_1\rangle,$ kaya kailangan nating malaman kung paano magpatuloy.

Ipagpalagay natin sandali na magpapatuloy tayo tulad ng nasa itaas, maliban na gamit ang eigenvector na $\vert\psi_k\rangle$ sa lugar ng $\vert\psi_1\rangle,$ para sa anumang pagpili ng $k\in\{0,\ldots,r-1\}$ na gusto nating pag-isipan. Ang resulta na makukuha natin mula sa pamamaraan ng phase estimation ay magiging isang pagtatantya

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

Sa pag-aakalang hindi natin alam ang $k$ o $r,$ maaari itong o hindi magbigay-daan sa atin na matukoy ang $r.$ Halimbawa, kung $k = 0$ makakakuha tayo ng pagtatantya na $y/2^m$ sa $0,$ na sa kasamaang-palad ay walang sinasabi sa atin. Ngunit ito ay isang hindi karaniwang kaso; para sa ibang mga halaga ng $k,$ maaari tayong matuto ng kahit ilang bagay tungkol sa $r.$

Maaari tayong gumamit ng algorithm na kilala bilang continued fraction algorithm upang gawing mga kalapit na fraction ang ating pagtatantya na $y/2^m$ — kasama ang $k/r$ kung sapat ang pagtatantya. Hindi natin ipapaliwanag dito ang continued fraction algorithm. Sa halip, narito ang pahayag ng isang kilalang katotohanan tungkol sa algorithm na ito.

Katotohanan

Binibigyan ng isang integer $N\geq 2$ at isang tunay na bilang $\alpha\in(0,1),$ may pinakamaraming isang pagpili ng mga integer na $u,v\in\{0,\ldots,N-1\}$ na may $v\neq 0$ at $\gcd(u,v)=1$ na sumasaklaw sa $\vert \alpha - u/v\vert < \frac{1}{2N^2}.$ Binibigyan ng $\alpha$ at $N,$ ang continued fraction algorithm ay naghahanap ng $u$ at $v,$ o nag-uulat na hindi sila umiiral. Ang algorithm na ito ay maaaring ipatupad bilang isang Boolean circuit na may laki na $O((\operatorname{lg}(N))^3).$

Kung mayroon tayong napakalapit na pagtatantya na $y/2^m$ sa $k/r,$ at pinapatakbo natin ang continued fraction algorithm para sa $N$ at $\alpha = y/2^m,$ makukuha natin ang $u$ at $v,$ tulad ng inilarawan sa katotohanan. Ang pagsusuri ng katotohanan ay nagbibigay-daan sa atin na tapusin na

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

Pansinin na sa partikular na hindi natin kinakailangang matutunan ang $k$ at $r,$ natututo lamang tayo ng $k/r$ sa pinakamababang termino.

Halimbawa, at tulad ng ating napansin na, hindi tayo matututo ng anuman mula sa $k=0.$ Ngunit iyon lamang ang halaga ng $k$ na nangyayari iyon. Kapag ang $k$ ay hindi zero, maaaring mayroon itong mga common factor sa $r,$ ngunit ang bilang na $v$ na nakukuha natin mula sa continued fraction algorithm ay dapat na hindi bababa sa hatiin ang $r.$

Malayo sa pagiging halata, ngunit totoo na kung mayroon tayong kakayahang matuto ng $u$ at $v$ para sa $u/v = k/r$ para sa $k\in\{0,\ldots,r-1\}$ na pinili nang random na pare-pareho, kung gayon malamang na malalaman natin ang $r$ pagkatapos ng ilang sample lamang. Sa partikular, kung ang ating hula para sa $r$ ay ang least common multiple ng lahat ng mga halaga para sa denominator na $v$ na ating naobserbahan, tama tayo nang may mataas na probabilidad. Sa intuitive na pagsasalita, ang ilang mga halaga ng $k$ ay hindi maganda dahil nagbabahagi sila ng mga common factor sa $r,$ at ang mga common factor na iyon ay nakatago sa atin kapag natuto tayo ng $u$ at $v.$ Ngunit ang mga random na pagpili ng $k$ ay malamang na hindi magtago ng mga factor ng $r$ nang matagal, at ang probabilidad na hindi tayo tama sa paghula ng $r$ sa pamamagitan ng pagkuha ng least common multiple ng mga denominator na ating naobserbahan ay bumabagsak nang exponentially sa bilang ng mga sample.

Nananatiling harapin ang isyu kung paano natin makukuha ang eigenvector na $\vert\psi_k\rangle$ ng $M_a$ kung saan ipapatakbo natin ang pamamaraan ng phase estimation. Tulad ng makikita, hindi talaga nating kailangan na likhain ang mga ito!

Ang gagawin natin sa halip ay patakbuhin ang pamamaraan ng phase estimation sa estado na $\vert 1\rangle,$ na ibig sabihin ay ang $n$-bit binary encoding ng bilang na $1,$ sa lugar ng isang eigenvector na $\vert\psi\rangle$ ng $M_a.$ Hanggang ngayon, pinag-usapan lamang natin ang pagpapatakbo ng pamamaraan ng phase estimation sa isang partikular na eigenvector, ngunit walang pumipigil sa atin na patakbuhin ang pamamaraan sa isang input state na hindi eigenvector ng $M_a,$ at iyon ang ating ginagawa dito sa estado na $\vert 1\rangle.$ (Hindi ito eigenvector ng $M_a$ maliban kung $a=1,$ na hindi isang pagpili na magiging interesado tayo.)

Ang dahilan para sa pagpili ng estado na $\vert 1\rangle$ sa lugar ng isang eigenvector ng $M_a$ ay ang sumusunod na ekwasyon ay totoo.

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

Isang paraan upang ma-verify ang ekwasyong ito ay ang paghahambing ng mga inner product ng dalawang panig sa bawat standard basis state, gamit ang mga formula na binanggit kanina sa aralin upang makatulong sa pag-evaluate ng mga resulta para sa kanang panig. Bilang resulta, makakakuha tayo ng eksaktong parehong mga resulta ng pagsukat na parang pinili natin ang $k\in\{0,\ldots,r-1\}$ nang random na pare-pareho at gumamit ng $\vert\psi_k\rangle$ bilang eigenvector.

Sa mas detalyadong pagsasalita, isipin natin na pinapatakbo natin ang pamamaraan ng phase estimation na may estado na $\vert 1\rangle$ sa lugar ng isa sa mga eigenvector na $\vert\psi_k\rangle.$ Pagkatapos isagawa ang inverse quantum Fourier transform, iniiwan tayo nito sa estado

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

kung saan

$$\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.$$

Ang vector na $\vert\gamma_k\rangle$ ay kumakatawan sa estado ng nangungunang $m$ qubit pagkatapos maisagawa ang inverse ng quantum Fourier transform sa kanila.

Kaya, dahil sa katotohanang $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ ay isang orthonormal set, nakikita natin na ang pagsukat ng nangungunang $m$ qubit ay nagbubunga ng isang pagtatantya na $y/2^m$ sa halaga ng $k/r$ kung saan ang $k\in\{0,\ldots,r-1\}$ ay pinili nang random na pare-pareho. Tulad ng ating pinag-usapan na, nagbibigay-daan ito sa atin na matutunan ang $r$ nang may mataas na antas ng kumpiyansa pagkatapos ng ilang independiyenteng pagpapatakbo, na siyang ating layunin.

Kabuuang gastos

Ang gastos sa pagpapatupad ng bawat controlled-unitary na $M_a^k$ ay $O(n^2).$ Mayroong $m$ controlled-unitary na operasyon, at mayroon tayong $m = O(n),$ kaya ang kabuuang gastos para sa mga controlled-unitary na operasyon ay $O(n^3).$ Bukod pa rito, mayroon tayong $m$ Hadamard gate (na nagdadagdag ng $O(n)$ sa gastos), at ang inverse quantum Fourier transform ay nagdadagdag ng $O(n^2)$ sa gastos. Kaya, ang gastos ng mga controlled-unitary na operasyon ay nangunguna sa gastos ng buong pamamaraan — na samakatuwid ay $O(n^3).$

Bukod pa sa quantum circuit mismo, mayroong ilang mga klasikal na kalkulasyon na kailangang isagawa sa daan. Kasama dito ang pagkalkula ng mga kapangyarihan na $a^k$ sa $\mathbb{Z}_N$ para sa $k = 2, 4, 8, \ldots, 2^{m-1},$ na kinakailangan upang lumikha ng mga controlled-unitary gate, pati na rin ang continued fraction algorithm na nagko-convert ng mga pagtatantya ng $\theta$ sa mga fraction. Ang mga kalkulasyong ito ay maaaring isagawa ng mga Boolean circuit na may kabuuang gastos na $O(n^3).$

Tulad ng karaniwan, ang lahat ng mga boundna ito ay maaaring mapabuti gamit ang mga asymptotically fast na algorithm; ipinapalagay ng mga boundna ito na gumagamit tayo ng mga karaniwang algorithm para sa mga pangunahing operasyong aritmetika.

Factoring sa pamamagitan ng order finding

Ang huling bagay na kailangan nating talakayin ay kung paano ang paglutas ng order-finding problem ay tumutulong sa atin na mag-factor. Ang bahaging ito ay ganap na klasikal — wala itong partikular na kaugnayan sa quantum computing.

Narito ang pangunahing ideya. Nais nating i-factorize ang bilang na $N,$ at magagawa natin ito nang recursive. Partikular, maaari tayong tumutok sa gawain ng paghati sa $N,$ na nangangahulugang paghahanap ng anumang dalawang integer na $b,c\geq 2$ kung saan $N = bc.$ Hindi ito posible kung ang $N$ ay isang prime number, ngunit maaari nating mahusay na subukan upang makita kung ang $N$ ay prime gamit muna ang isang primality testing algorithm, at kung ang $N$ ay hindi prime susubukan nating hatiin ito. Sa sandaling hatiin natin ang $N,$ maaari tayong simpleng mag-recurse sa $b$ at $c$ hanggang ang lahat ng ating mga factor ay prime at makuha natin ang prime factorization ng $N.$

Ang paghati ng mga even integer ay madali: inilalabas lamang natin ang $2$ at $N/2.$

Madali rin ang paghati ng mga perfect power, na nangangahulugang mga numero ng anyo na $N = s^j$ para sa mga integer na $s,j\geq 2,$ sa pamamagitan ng pagtatantya sa mga ugat na $N^{1/2},$ $N^{1/3},$ $N^{1/4},$ at iba pa, at sinusuri ang mga kalapit na integer bilang mga suspek para sa $s.$ Hindi na tayo kailangang pumunta nang higit sa $\log(N)$ na hakbang sa sekwensyang ito, dahil sa puntong iyon ang ugat ay bumababa sa ibaba ng $2$ at hindi na magrerevela ng mga karagdagang kandidato.

Maganda na magagawa natin ang parehong mga bagay na ito dahil ang order finding ay hindi makakatulong sa atin na mag-factor ng mga even number o para sa mga prime power, kung saan ang bilang na $s$ ay nagkataong prime. Kung ang $N$ ay odd at hindi isang prime power, gayunpaman, ang order finding ay nagbibigay-daan sa atin na hatiin ang $N.$

Probabilistic algorithm to split an odd, composite integer N that is not a prime power

1. Random na pumili ng $a\in\{2,\ldots,N-1\}.$

2. Kalkulahin ang $d=\gcd(a,N).$

3. Kung $d > 1$ kung gayon ilabas ang $b = d$ at $c = N/d$ at huminto. Kung hindi ay magpatuloy sa susunod na hakbang na alam na ang $a\in\mathbb{Z}_N^{\ast}.$

4. Hayaan ang $r$ na maging order ng $a$ modulo $N.$ (Dito kailangan natin ang order finding.)

5. Kung ang $r$ ay even:

   5.1 Kalkulahin ang $x = a^{r/2} - 1$ modulo $N$
   5.2 Kalkulahin ang $d = \gcd(x,N).$
   5.3 Kung $d>1$ kung gayon ilabas ang $b=d$ at $c = N/d$ at huminto.

6. Kung maaabot ang puntong ito, nabigo ang algorithm na mahanap ang isang factor ng $N.$

Ang isang pagpapatakbo ng algorithm na ito ay maaaring mabigo na mahanap ang isang factor ng $N.$ Partikular, nangyayari ito sa dalawang sitwasyon:

• Ang order ng $a$ modulo $N$ ay odd.
• Ang order ng $a$ modulo $N$ ay even at $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1.$

Gamit ang pangunahing number theory maaaring mapatunayang, para sa isang random na pagpili ng $a,$ na may probabilidad na hindi bababa sa $1/2$ ang alinman sa mga pangyayaring ito ay hindi nangyayari. Sa katunayan, ang probabilidad na ang alinman sa mga pangyayari ay nangyayari ay hindi hihigit sa $2^{-(m-1)}$ para sa $m$ bilang bilang ng mga natatanging prime factor ng $N,$ na siyang dahilan kung bakit kinakailangan ang pag-aakalang ang $N$ ay hindi isang prime power. (Ang pag-aakalang ang $N$ ay odd ay kinakailangan din para maging totoo ang katotohanang ito.)

Nangangahulugan ito na ang bawat pagpapatakbo ay may hindi bababa sa 50% na pagkakataon na hatiin ang $N.$ Samakatuwid, kung pinapatakbo natin ang algorithm nang $t$ beses, random na pinipili ang $a$ sa bawat pagkakataon, magtatagumpay tayo sa paghati ng $N$ nang may probabilidad na hindi bababa sa $1 - 2^{-t}.$

Ang pangunahing ideya sa likod ng algorithm ay ang sumusunod. Kung mayroon tayong pagpili ng $a$ kung saan ang order $r$ ng $a$ modulo $N$ ay even, kung gayon ang $r/2$ ay isang integer at maaari nating isaalang-alang ang mga bilang

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

Gamit ang formula na $Z^2 - 1 = (Z+1)(Z-1),$ matapos nating tapusin na

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

Ngayon, alam natin na ang $a^r \; (\textrm{mod}\; N) = 1$ sa pamamagitan ng kahulugan ng order — na isa pang paraan ng pagsasabing ang $N$ ay pantay na naghahati sa $a^r - 1.$ Nangangahulugan ito na ang $N$ ay pantay na naghahati sa produkto

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

Para maging totoo ito, ang lahat ng prime factor ng $N$ ay dapat na prime factor rin ng $a^{r/2} - 1$ o ng $a^{r/2} + 1$ (o ng pareho) — at para sa isang random na seleksyon ng $a$ ay lumalabas na hindi malamang na ang lahat ng prime factor ng $N$ ay hahatiin ang isa sa mga termino at wala ang hahatiin sa isa pa. Kung hindi, hanggang sa ilang prime factor ng $N$ ang hahatiin sa unang termino at ang ilan ay hahatiin sa pangalawang termino, malalaman natin ang isang non-trivial na factor ng $N$ sa pamamagitan ng pagkalkula ng GCD kasama ang unang termino.