Proseso ng phase estimation

Susunod, tatalakayin natin ang proseso ng phase estimation, na isang quantum algorithm para sa paglutas ng problema ng phase estimation.

Magsisimula tayo sa isang low-precision na warm-up, na nagpapaliwanag ng ilang pangunahing intuisyon sa likod ng pamamaraan. Pagkatapos ay pag-uusapan natin ang quantum Fourier transform, na isang mahalagang quantum na operasyon na ginagamit sa proseso ng phase estimation, kasama ang implementasyon nito sa quantum circuit. Kapag mayroon na tayong quantum Fourier transform, ilalarawan natin ang proseso ng phase estimation sa buong pangkalahatang paraan at susuriin ang performance nito.

Warm-up: pagtatantya ng mga phase nang may mababang katumpakan

Magsisimula tayo sa ilang simpleng bersyon ng proseso ng phase estimation na nagbibigay ng low-precision na solusyon sa problema ng phase estimation. Nakakatulong ito para maipaliwanag ang intuisyon sa likod ng pangkalahatang proseso na makikita natin nang kaunti pa sa aralin.

Paggamit ng phase kickback

Isang simpleng approach sa phase-estimation problem, na nagbibigay-daan sa atin na matuto ng kaunti tungkol sa value ng $\theta$ na hinahanap natin, ay nakabatay sa phase kick-back na phenomenon. Gaya ng makikita natin, ito ay mahalagang isang single-qubit na bersyon ng pangkalahatang phase-estimation procedure na tatalakayin sa ibang bahagi ng lesson.

Bilang bahagi ng input sa phase estimation problem, mayroon tayong unitary quantum circuit para sa operation na $U$. Maaari nating gamitin ang paglalarawan ng circuit na ito para gumawa ng circuit para sa isang controlled-$U$ operation, na maaaring ilarawan tulad ng iminumungkahi ng figure na ito (na may operation na $U$, na tinitingnan bilang isang quantum gate, sa kaliwa at isang controlled-$U$ operation sa kanan).

Puwede tayong gumawa ng quantum circuit para sa controlled-$U$ operation sa pamamagitan ng unang pagdadagdag ng control qubit sa circuit para sa $U$, at pagkatapos ay pagpapalit ng bawat gate sa circuit para sa $U$ ng controlled version ng gate na iyon — kaya ang isa nating bagong control qubit ay epektibong kumokontrol sa bawat isang gate sa circuit para sa $U$. Kailangan nito na mayroon tayong controlled version ng bawat gate sa ating circuit, ngunit maaari natin palaging gumawa ng mga circuit para sa mga controlled operation na ito kung sakaling hindi sila kasama sa ating gate set.

Ngayon, isaalang-alang ang sumusunod na circuit, kung saan ang input state $\vert\psi\rangle$ ng lahat ng qubit maliban sa pinakaunahan ay ang quantum state eigenvector ng $U$.

Ang measurement outcome probabilities para sa circuit na ito ay nakadepende sa eigenvalue ng $U$ na tumutugma sa eigenvector $\vert\psi\rangle$. Suriin natin nang detalyado ang circuit upang matukoy kung paano eksakto ito nangyayari.

Ang initial state ng circuit ay

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

at ang unang Hadamard gate ay nagbabago ng state na ito tungo sa

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

Susunod, isinasagawa ang controlled-$U$ operation, na nagreresulta sa state na

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

Gamit ang assumption na ang $\vert\psi\rangle$ ay isang eigenvector ng $U$ na may eigenvalue $\lambda = e^{2\pi i\theta}$, maaari nating alternatibong ipahayag ang state na ito tulad ng sumusunod.

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

Dito natin mapapansin ang penomenon ng phase kickback. Bahagyang naiiba ito ngayon kumpara sa nakita natin sa algorithm ni Deutsch at sa Deutsch-Jozsa algorithm dahil hindi tayo gumagamit ng query gate — ngunit magkatulad ang ideya.

Sa wakas, isinasagawa ang pangalawang Hadamard gate. Pagkatapos ng kaunting simplification, makukuha natin ang expression na ito para sa state na ito.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

Kaya't ang measurement ay nagbibigay ng mga outcome na $0$ at $1$ na may mga probabilities na ito:

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

Narito ang isang plot ng mga probabilities para sa dalawang posibleng outcome, $0$ at $1$, bilang mga function ng $\theta$.

Natural, ang dalawang probabilidad ay palaging nagbubuod sa $1$. Pansinin na kapag $\theta = 0$, ang resulta ng pagsukat ay palaging $0$, at kapag $\theta = 1/2$, ang resulta ng pagsukat ay palaging $1$. Kaya, bagama't hindi inihahayag ng resulta ng pagsukat kung ano mismo ang $\theta$, nagbibigay ito sa atin ng ilang impormasyon tungkol sa kanya — at kung ipinangako sa atin na alinman sa $\theta = 0$ o $\theta = 1/2$, malalaman natin mula sa circuit kung alin ang tama nang walang pagkakamali.

Sa madaling salita, maaari nating isipin ang resulta ng pagsukat ng circuit bilang isang hula para sa $\theta$ na may "isang bit na katumpakan." Sa ibang salita, kung isusulat natin ang $\theta$ sa binary notation at ii-round ito sa isang bit, magkakaroon tayo ng numero tulad nito:

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

Ang resulta ng pagsukat ay maaaring tingnan bilang isang hula para sa bit na $a$. Kapag ang $\theta$ ay hindi $0$ ni $1/2$, may hindi-zero na probabilidad na ang hula ay mali — ngunit ang probabilidad ng pagkakamali ay nagiging mas maliit at mas maliit habang lumalapit tayo sa $0$ o $1/2$.

Natural na itanong kung anong papel ang ginagampanan ng dalawang Hadamard gate sa pamamaraang ito:

• Itinatakda ng unang Hadamard gate ang control qubit sa isang uniform superposition ng $\vert 0\rangle$ at $\vert 1\rangle$, upang kapag nangyari ang phase kickback, nangyayari ito para sa estado ng $\vert 1\rangle$ at hindi para sa estado ng $\vert 0\rangle$, na lumilikha ng relative na pagkakaiba ng phase na nakakaapekto sa mga resulta ng pagsukat. Kung hindi natin ito gagawin at ang phase kickback ay makagawa ng isang global na phase, wala itong epekto sa mga probabilidad ng pagkuha ng iba't ibang resulta ng pagsukat.

• Pinapayagan tayo ng ikalawang Hadamard gate na matuto ng kaunti tungkol sa bilang na $\theta$ sa pamamagitan ng penomenon ng interference. Bago ang ikalawang Hadamard gate, ang estado ng pinaka-itaas na qubit ay

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  at kung susukatin natin ang estado na ito, makukuha natin ang $0$ at $1$ na bawat isa ay may probabilidad na $1/2$, na walang sinasabi sa atin tungkol sa $\theta$. Sa pamamagitan ng paggawa ng ikalawang Hadamard gate, gayunpaman, pinipili natin ang bilang na $\theta$ na makaapekto sa mga probabilidad ng output.

Pagdoble ng phase

Ginagamit ng circuit sa itaas ang penomenon ng phase kickback para tantiyahin ang $\theta$ sa isang bit na katumpakan. Ang isang bit na katumpakan ay maaaring sapat sa ilang sitwasyon — ngunit para sa factoring kakailanganin natin ng mas maraming katumpakan kaysa doon. Isang natural na tanong ay, paano natin malalaman ang higit pa tungkol sa $\theta?$

Isang napaka-simpleng bagay na magagawa natin ay palitan ang controlled-$U$ na operasyon sa ating circuit ng dalawang kopya ng operasyong ito, tulad ng sa circuit na ito:

Ang dalawang kopya ng isang controlled-$U$ na operasyon ay katumbas ng isang controlled-$U^2$ na operasyon. Kung ang $\vert\psi\rangle$ ay isang eigenvector ng $U$ na may eigenvalue na $\lambda = e^{2\pi i \theta}$, ang estado na ito ay isang eigenvector din ng $U^2$, sa pagkakataong ito ay may eigenvalue na $\lambda^2 = e^{2\pi i (2\theta)}$.

Kaya, kung tatakbohin natin ang bersyon ng circuit na ito, epektibo tayong nagsasagawa ng parehong komputasyon tulad ng dati, maliban na ang bilang na $\theta$ ay pinalitan ng $2\theta$. Narito ang isang plot na naglalarawan ng mga probabilidad ng output habang ang $\theta$ ay nagmumula sa $0$ hanggang $1$.

Ang paggawa nito ay talagang makapagbibigay sa atin ng ilang karagdagang impormasyon tungkol sa $\theta$. Kung ang binary representation ng $\theta$ ay

$$\theta = 0.a_1 a_2 a_3\cdots$$

ang pagdoble ng $\theta$ ay epektibong inililipat ang binary point ng isang posisyon sa kanan:

$$2\theta = a_1. a_2 a_3\cdots$$

At dahil inilalagay natin ang $\theta = 1$ at $\theta = 0$ na magkatumbas habang umiikot tayo sa unit circle, nakikita natin na ang bit na $a_1$ ay walang impluwensya sa ating mga probabilidad, at epektibo tayong kumukuha ng hula para sa ikalawang bit pagkatapos ng binary point kung ii-round natin ang $\theta$ sa dalawang bit. Halimbawa, kung alam natin nang maaga na ang $\theta$ ay alinman sa $0$ o $1/4$, maaari nating lubos na pagkatiwalaan ang resulta ng pagsukat para sabihin sa atin kung alin.

Hindi agad malinaw, gayunpaman, kung paano dapat ipagkasundo ang pagtatantyang ito sa natutunan natin mula sa orihinal na (hindi dindoble) na circuit ng phase kickback para mabigyan tayo ng pinakatumpak na impormasyon hangga't maaari tungkol sa $\theta$. Kaya bumalik tayo ng isang hakbang at isaalang-alang kung paano magpapatuloy.

Dalawang-qubit na phase estimation

Sa halip na isaalang-alang nang magkahiwalay ang dalawang opsyon na inilarawan sa itaas, pagsamahin natin ang mga ito sa isang circuit tulad nito.

Ang mga Hadamard gate pagkatapos ng mga controlled na operasyon ay tinanggal at wala pang mga pagsukat dito. Magdadagdag tayo ng higit pa sa circuit habang isinasaalang-alang natin ang ating mga opsyon para matuto ng hangga't maaari tungkol sa $\theta$.

Kung tatakbohin natin ang circuit na ito kapag ang $\vert\psi\rangle$ ay isang eigenvector ng $U$, ang estado ng mga ibabang qubit ay mananatiling $\vert\psi\rangle$ sa buong circuit, at ang mga phase ay "matatapak" sa estado ng dalawang pinaka-itaas na qubit. Suriin natin nang maingat ang circuit, sa pamamagitan ng sumusunod na figure.

Maaari nating isulat ang estado na $\vert\pi_1\rangle$ tulad nito:

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

Kapag ginawa ang unang controlled-$U$ na operasyon, ang eigenvalue na $\lambda = e^{2\pi i\theta}$ ay natatapon sa phase kapag ang $a_0$ (ang pinaka-itaas na qubit) ay katumbas ng $1$, ngunit hindi kapag ito ay $0$. Kaya, maaari nating ipahayag ang nagresultang estado tulad nito:

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

Ang ikalawa at ikatlong controlled-$U$ gate ay gumagawa ng katulad, maliban para sa $a_1$ sa halip na $a_0$, at na ang $\theta$ ay pinalitan ng $2\theta$. Maaari nating ipahayag ang nagresultang estado tulad nito:

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

Kung iisipin natin ang binary string na $a_1 a_0$ bilang kumakatawan sa isang integer na $x \in \{0,1,2,3\}$ sa binary notation, na $x = 2 a_1 + a_0$, maaari nating ipahayag ang estado na ito sa alternatibong paraan tulad ng sumusunod.

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

Ang ating layunin ay kumuha ng hangga't maaaring impormasyon tungkol sa $\theta$ mula sa estado na ito.

Sa puntong ito ay isasaalang-alang natin ang isang espesyal na kaso, kung saan ipinangako sa atin na ang $\theta = \frac{y}{4}$ para sa ilang integer na $y\in\{0,1,2,3\}.$ Sa ibang salita, mayroon tayong $\theta\in \{0, 1/4, 1/2, 3/4\},$ kaya maaari nating ipahayag ang bilang na ito nang eksakto gamit ang binary notation na may dalawang bit, bilang $.$00, $.$01, $.$10, o $.$11. Sa pangkalahatan, ang $\theta$ ay maaaring hindi isa sa apat na halagang ito, ngunit ang pag-iisip tungkol sa espesyal na kasong ito ay makakatulong sa atin na malaman kung paano pinaka-epektibong makakuha ng impormasyon tungkol sa $\theta$ sa pangkalahatan.

Una, magtutukoy tayo ng isang dalawang-Qubit na state vector para sa bawat posibleng halaga na $y \in \{0, 1, 2, 3\}$.

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

Pagkatapos ng pagpapasimple ng mga exponential, maaari nating isulat ang mga vector na ito tulad ng sumusunod.

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

Ang mga vector na ito ay orthogonal: kung pipiliin natin ang anumang pares ng mga ito at kalkulahin ang kanilang inner product, makuha natin ang $0$. Ang bawat isa ay isang unit vector din, kaya ang $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ ay isang orthonormal basis. Kaya naman agad na nalalaman natin na may pagsukat na kayang i-discriminate ang mga ito nang perpekto — ibig sabihin, kung bibigyan tayo ng isa sa mga ito ngunit hindi natin alam kung alin, masasabi natin kung alin ito nang walang pagkakamali.

Para magsagawa ng ganitong diskriminasyon gamit ang quantum circuit, maaari tayong magtukoy muna ng isang unitary na operasyong $V$ na nagbabago ng mga standard basis state sa apat na estado na nakalista sa itaas.

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

Para isulat ang $V$ bilang isang $4\times 4$ matrix, kailangan lang nating gawin ang mga column ng $V$ na maging mga estado na $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$.

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Ito ay isang espesyal na matrix, at malamang na nakilala na ito ng ilang mambabasa: ito ang matrix na nauugnay sa $4$-dimensional na discrete Fourier transform. Sa liwanag ng katotohanang ito, tawagan natin ito ng pangalang $\mathrm{QFT}_4$ sa halip na $V$. Ang pangalang $\mathrm{QFT}$ ay maikling pangalan para sa quantum Fourier transform — na essentially ay ang discrete Fourier transform lamang, na tinitingnan bilang isang unitary na operasyon. Tatalakayin natin ang quantum Fourier transform nang mas detalyado at sa mas pangkalahatang paraan sa lalong madaling panahon.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Maaari nating gawin ang inverse ng operasyong ito para pumunta sa kabilang direksyon, para baguhin ang mga estado na $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ sa mga standard basis state na $\vert 0\rangle,\ldots,\vert 3\rangle$. Kung gagawin natin ito, maaari tayong sumukat para malaman kung aling halaga ng $y\in\{0,1,2,3\}$ ang naglarawan sa $\theta$ bilang $\theta = y/4$. Narito ang isang diagram ng quantum circuit na gumagawa nito.

Sa buod, kung tatakbohin natin ang circuit na ito kapag $\theta = y/4$ para sa $y\in\{0,1,2,3\}$, ang estado kaagad bago mangyari ang mga pagsukat ay magiging $\vert \psi\rangle \vert y\rangle$ (para sa $y$ na naka-encode bilang isang dalawang-bit na binary string), kaya ang mga pagsukat ay magpapakita ng halagang $y$ nang walang pagkakamali.

Ang circuit na ito ay nagmumula sa espesyal na kaso na $\theta \in \{0,1/4,1/2,3/4\}$ — ngunit maaari nating patakbuhin ito para sa anumang pagpili ng $U$ at $\vert \psi\rangle$, at samakatuwid para sa anumang halaga ng $\theta$, na nais natin. Narito ang isang plot ng mga probabilidad ng output na ginagawa ng circuit para sa mga arbitrary na pagpili ng $\theta$.

Ito ay isang malinaw na pagpapabuti kumpara sa single-qubit na variant na inilarawan nang mas maaga sa aralin. Hindi ito perpekto — maaari itong magbigay sa atin ng maling sagot — ngunit ang sagot ay lubos na nakiling sa mga halaga ng $y$ para sa kung saan ang $y/4$ ay malapit sa $\theta$. Sa partikular, ang pinakamalamang na resulta ay palaging tumutugma sa pinakamalapit na halaga ng $y/4$ sa $\theta$ (na inilalagay ang $\theta = 0$ at $\theta = 1$ na magkatumbas tulad ng dati), at mula sa plot mukhang laging lumalabas ang pinakamalapit na halagang ito para sa $x$ na may probabilidad na kaunti sa itaas ng $40\%$. Kapag ang $\theta$ ay eksaktong nasa gitna ng dalawang ganoong halaga, tulad ng $\theta = 0.375$ halimbawa, ang dalawang pantay na malapit na halaga ng $y$ ay pantay na malamang.

Paghahanda para sa pagpapalawak sa maraming qubit

Dahil sa pagpapabuting nakamit natin sa pamamagitan ng paggamit ng dalawang control qubit sa halip na isa, kasabay ng inverse ng $4$-dimensional na quantum Fourier transform, natural na isaalang-alang ang karagdagang pagpapalawak nito — sa pamamagitan ng pagdaragdag ng mas maraming control qubit. Kapag ginawa natin ito, makuha natin ang pangkalahatang proseso ng phase estimation. Makikita natin kung paano ito gumagana sa lalong madaling panahon, ngunit para mailarawan ito nang tumpak kakailanganin nating talakayin ang quantum Fourier transform sa mas pangkalahatang paraan, para makita kung paano ito tinutukoy para sa ibang mga dimensyon at para makita kung paano natin ito maipapatupad (o ang inverse nito) gamit ang isang quantum circuit.

Quantum Fourier Transform

Ang quantum Fourier transform ay isang unitary na operasyon na maaaring tukuyin para sa anumang positibong integer na dimensyon na $N$. Sa seksyong ito, makikita natin kung paano natatukoy ang operasyong ito at kung paano ito maipapatupad gamit ang isang quantum circuit sa $m$ na qubit na may gastos na $O(m^2)$ kapag $N = 2^m$.

Ang mga matrix na naglalarawan sa quantum Fourier transform ay hinango mula sa isang katulad na operasyon sa mga $N$-dimensional na vector na kilala bilang discrete Fourier transform. Ang operasyong ito ay maaaring pag-aralan sa iba't ibang paraan. Halimbawa, maaari nating tingnan ang discrete Fourier transform sa purong abstrakto at matematikal na paraan bilang isang linear na pagmamapa. O maaari rin nating tingnan ito sa computational na paraan, kung saan binibigyan tayo ng isang $N$-dimensional na vector ng mga kumplikadong numero (gamit ang binary notation para i-encode ang real at imaginary na bahagi ng mga entry, halimbawa) at ang layunin ay kalkulahin ang $N$-dimensional na vector na nakuha sa pamamagitan ng pag-apply ng discrete Fourier transform. Ang ating pokus ay sa ikatlong paraan, na ang pagtingin sa transformasyong ito bilang isang unitary na operasyon na maaaring isagawa sa isang quantum na sistema.

Mayroong isang mahusay na algorithm para sa pagkukuwenta ng discrete Fourier transform sa isang ibinigay na input vector na kilala bilang fast Fourier transform. Mayroon itong mga aplikasyon sa signal processing at marami pang iba, at itinuturing ng marami na isa sa mga pinakamahalagang algorithm na natuklasan. Ang totoo, ang implementasyon ng quantum Fourier transform kapag $N$ ay kapangyarihan ng 2 na ating pag-aaralan ay nakabatay sa eksakto ring pinagbabatayan na istruktura na nagpapahintulot sa fast Fourier transform.

Kahulugan ng quantum Fourier transform

Para tukuyin ang quantum Fourier transform, tutukuyin muna natin ang isang kumplikadong numero $\omega_N$, para sa bawat positibong integer na $N$, tulad nito:

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

Ito ang numero sa complex unit circle na nakukuha natin kapag nagsimula tayo sa $1$ at lumipat nang counter-clockwise ng anggulo na $2\pi/N$ radians, o isang bahagi na $1/N$ ng sirkumperensya ng bilog. Narito ang ilang halimbawa:

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

Ngayon ay maaari na nating tukuyin ang $N$-dimensional na quantum Fourier transform, na inilalarawan ng isang $N\times N$ na matrix kung saan ang mga row at column ay nauugnay sa mga standard basis state na $\vert 0\rangle,\ldots,\vert N-1\rangle$. Kailangan lamang natin ang operasyong ito kapag $N = 2^m$ ay kapangyarihan ng $2$ para sa phase estimation, ngunit ang operasyon ay maaaring tukuyin para sa anumang positibong integer na $N$.

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

Tulad ng nasabi na, ito ang matrix na nauugnay sa $N$-dimensional na discrete Fourier transform. Kadalasan ang nangunguna na factor na $1/\sqrt{N}$ ay hindi kasama sa kahulugan ng matrix na ito, ngunit kailangan natin itong isama para makakuha ng unitary matrix.

Narito ang quantum Fourier transform, nakasulat bilang matrix, para sa ilang maliliit na halaga ng $N$.

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

Pansinin, sa partikular, na ang $\mathrm{QFT}_2$ ay isa pang pangalan para sa isang Hadamard na operasyon.

Unitarity

Suriin natin kung ang $\mathrm{QFT}_N$ ay unitary, para sa anumang pagpili ng $N$. Isang paraan para gawin ito ay ipakita na ang mga column nito ay bumubuo ng isang orthonormal na batayan. Maaari tayong tumukoy ng isang vector na naaayon sa column na bilang $y$, simula sa $y = 0$ hanggang sa $y = N-1$, tulad nito:

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

Ang pagkuha ng inner product sa pagitan ng anumang dalawa sa mga vector na ito ay nagbibigay sa atin ng sumusunod na ekspresyon:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

Maaari nating suriin ang mga kabuuang tulad nito gamit ang sumusunod na pormula para sa kabuuan ng unang $N$ na termino ng isang geometric series.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Sa partikular, maaari nating gamitin ang pormulang ito kapag $\alpha = \omega_N^{y-z}$. Kapag $y = z$, mayroon tayong $\alpha = 1$, kaya gamit ang pormula at paghahati sa $N$ ay nagbibigay ng

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

Kapag $y\neq z$, mayroon tayong $\alpha \neq 1$, kaya ipinapakita ng pormula ang sumusunod:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

Nangyayari ito dahil ang $\omega_N^N = e^{2\pi i} = 1$, kaya ang $\omega_N^{N(y-z)} = 1^{y-z} = 1$, na ginagawang zero ang numerator, habang ang denominator ay hindi zero dahil ang $\omega_N^{y-z} \neq 1$. Sa intuitive na pagsasalita, ang ginagawa natin ay ang pagbubuod ng isang grupo ng mga punto na nakakalat sa paligid ng unit circle, at nagkakansela ang mga ito at nag-iiwan ng $0$ kapag binuod.

Kaya naman, napatunayan na natin na ang $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ ay isang orthonormal na set,

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

na nagpapakita na ang $\mathrm{QFT}_N$ ay unitary.

Mga controlled-phase gate

Para maipatupad ang quantum Fourier transform gamit ang isang quantum circuit, kailangan nating gumamit ng mga controlled-phase gate. Alalahanin na ang isang phase operation ay isang single-qubit unitary na operasyon ng anyo

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

para sa anumang tunay na numero $\alpha$. Ang isang controlled na bersyon ng gate na ito ay may sumusunod na matrix:

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

Para sa controlled gate na ito, hindi talaga mahalaga kung aling qubit ang control at aling qubit ang target dahil katumbas ang dalawang posibilidad. Maaari nating gamitin ang alinman sa mga sumusunod na simbolo para katawanin ang gate na ito sa mga quantum circuit diagram.

Para sa ikatlong anyo, ang label na $\alpha$ ay minsan inilalagay sa tabi ng control line o sa ilalim ng mas mababang control kapag maginhawa iyon.

Para maisagawa ang quantum Fourier transform kapag $N = 2^m$ at $m\geq 2$, kailangan nating magsagawa ng isang operasyon sa $m$ na qubit na ang aksyon sa mga standard basis state ay maaaring ilarawan bilang

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

kung saan ang $a$ ay isang bit at ang $y \in \{0,\ldots,2^{m-1} - 1\}$ ay isang numero na naka-encode sa binary notation bilang isang string ng $m-1$ na bit. Maaaring gawin ito gamit ang mga controlled-phase gate sa pamamagitan ng paggeneralize ng sumusunod na halimbawa, kung saan ang $m=5$.

Sa pangkalahatan, para sa isang arbitrary na pagpili ng $m\geq 2$, ang pinakamataas na qubit na naaayon sa bit na $a$ ay maaaring tingnan bilang control, na may mga phase gate na $P_{\alpha}$ mula sa $\alpha = \pi/2^{m-1}$ sa qubit na naaayon sa least significant bit ng $y$ hanggang sa $\alpha = \frac{\pi}{2}$ sa qubit na naaayon sa most significant bit ng $y$. Ang lahat ng mga controlled-phase gate na ito ay commute sa isa't isa at maaaring isagawa sa anumang pagkakasunud-sunod.

Implementasyon ng circuit para sa QFT

Ngayon ay makikita natin kung paano natin maipapatupad ang quantum Fourier transform gamit ang isang circuit kapag ang dimensyon na $N = 2^m$ ay kapangyarihan ng $2$. Sa katunayan, may maraming paraan para maipatupad ang quantum Fourier transform, ngunit ito malamang ang pinakasimpleng pamamaraan na kilala. Kapag alam na natin kung paano maipapatupad ang quantum Fourier transform gamit ang isang quantum circuit, straightforward na ang pagpapatupad ng inverse nito: maaari nating palitan ang bawat gate ng inverse nito (o, katumbas, conjugate transpose) at ilapat ang mga gate sa reverse na pagkakasunud-sunod. Ang bawat quantum circuit na binubuo ng mga unitary gate lamang ay maaaring i-invert sa ganitong paraan.

Ang implementasyon ay recursive ang kalikasan, kaya ito ang pinaka-natural na paraan ng paglalarawan nito. Ang base case ay $m=1$, kung saan ang quantum Fourier transform ay isang Hadamard na operasyon.

Para maisagawa ang quantum Fourier transform sa $m$ na qubit kapag $m \geq 2$, maaari nating isagawa ang mga sumusunod na hakbang, na ang mga aksyon nito ay ilalarawan natin para sa mga standard basis state ng anyo $\vert x \rangle \vert a\rangle$, kung saan ang $x\in\{0,\ldots,2^{m-1} - 1\}$ ay isang integer na naka-encode bilang $m-1$ na bit gamit ang binary notation at ang $a$ ay isang solong bit.

1. Una, i-apply ang $2^{m-1}$-dimensional na quantum Fourier transform sa ibaba/kaliwa na $m-1$ na qubit para makuha ang estado na ito:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   Ginagawa ito sa pamamagitan ng recursive na pag-apply ng pamamaraang inilalarawan para sa isang qubit na mas kaunti, gamit ang Hadamard na operasyon sa isang solong qubit bilang base case.

2. Gamitin ang pinakamataas/kanan na qubit bilang control para mag-inject ng phase na $\omega_{2^m}^y$ para sa bawat standard basis state na $\vert y\rangle$ ng natitirang $m-1$ na qubit (tulad ng inilalarawan sa itaas) para makuha ang estado na ito:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. Magsagawa ng Hadamard gate sa pinakamataas/kanan na qubit para makuha ang estado na ito:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. I-permute ang pagkakasunud-sunod ng mga qubit upang ang least significant bit ay maging most significant bit, na inililipat ang lahat ng iba pa pataas/pakanan:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

Halimbawa, narito ang circuit na nakuha natin para sa $N = 32 = 2^5$. Sa diagram na ito, ang mga qubit ay binibigyan ng mga pangalan na naaayon sa mga standard basis vector na $\vert x\rangle \vert a\rangle$ (para sa input) at $\vert b\rangle \vert y\rangle$ (para sa output) para sa kalinawan.

Pagsusuri

Ang pangunahing pormula na kailangan nating i-verify na ang circuit na inilarawan ay nagpapatupad ng $2^m$-dimensional na quantum Fourier transform ay ito:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

Ang pormulang ito ay gumagana para sa anumang pagpili ng mga integer na $a,$ $b,$ $x,$ at $y,$ ngunit kailangan lamang natin ito para sa $a,b\in\{0,1\}$ at $x,y\in\{0,\ldots,2^{m-1}-1\}.$ Maaaring i-verify ito sa pamamagitan ng pag-expand ng produkto sa exponent sa kanang bahagi,

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

kung saan ang pangalawang pagkakapantay-pantay ay gumagamit ng obserbasyon na

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

Ang $2^m$-dimensional na quantum Fourier transform ay tinukoy tulad ng sumusunod para sa bawat $u\in\{0,\ldots,2^m - 1\}$.

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

Kung isusulat natin ang $u$ at $v$ bilang

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

para sa $a,b\in\{0,1\}$ at $x,y\in\{0,\ldots,2^{m-1} - 1\}$, makukuha natin ang

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

Sa wakas, sa pamamagitan ng pag-iisip tungkol sa mga standard basis state na $\vert x \rangle \vert a\rangle$ at $\vert b \rangle \vert y \rangle$ bilang mga binary encoding ng mga integer sa hanay na $\{0,\ldots,2^m-1\}$,

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

makikita natin na ang circuit sa itaas ay nagpapatupad ng kinakailangang operasyon. Kung ang pamamaraang ito para sa pagsasagawa ng quantum Fourier transform ay tila kapansin-pansin, ito ay dahil totoo nga: ito ay mahalagang ang fast Fourier transform sa anyo ng isang quantum circuit.

Sa wakas, bilangin natin kung ilang gate ang ginagamit sa circuit na inilarawan lamang. Ang mga controlled-phase gate ay wala sa standard gate set na tinalakay natin sa nakaraang aralin, ngunit sa simula ay hindi natin ito isasaalang-alang at bibilangin ang bawat isa sa kanila bilang isang solong gate.

Hayaan nating $s_m$ ang manukuoy sa bilang ng mga gate na kailangan natin para sa bawat posibleng pagpili ng $m$. Kung ang $m=1$, ang quantum Fourier transform ay isang Hadamard na operasyon lamang, kaya

$$s_1 = 1.$$

Kung $m\geq 2$, sa circuit sa itaas ay kailangan natin ng $s_{m-1}$ na gate para sa quantum Fourier transform sa $m-1$ na qubit, kasama ang $m-1$ na controlled-phase gate, kasama ang isang Hadamard gate, kasama ang $m-1$ na swap gate, kaya

$$s_m = s_{m-1} + (2m - 1).$$

Maaari tayong makakuha ng closed-form na ekspresyon sa pamamagitan ng pagbubuod:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

Hindi natin talaga kailangan ng kasinlaking bilang ng swap gate na inilalarawan ng pamamaraan. Kung i-rearrange natin ang mga gate nang kaunti, maaari nating itulak ang lahat ng swap gate sa kanan at bawasan ang bilang ng swap gate na kinakailangan sa $\lfloor m/2\rfloor$. Sa asymptotic na pagsasalita, hindi ito malaking pagpapabuti: makakakuha pa rin tayo ng mga circuit na may sukat na $O(m^2)$ para sa pagsasagawa ng $\mathrm{QFT}_{2^m}$.

Kung nais nating ipatupad ang quantum Fourier transform gamit lamang ang mga gate mula sa ating standard gate set, kailangan nating buuin o i-approximate ang bawat isa sa mga controlled-phase gate gamit ang mga gate mula sa ating set. Ang bilang na kinakailangan ay nakasalalay sa kung gaano karaming katumpakan ang hinihingi natin, ngunit bilang function ng $m$ ang kabuuang gastos ay nananatiling quadratic.

Sa katunayan, posible ring i-approximate ang quantum Fourier transform nang medyo malapit gamit ang isang sub-quadratic na bilang ng mga gate sa pamamagitan ng paggamit ng katotohanan na ang $P_{\alpha}$ ay napakalapit sa identity operation kapag napakaliit ng $\alpha$ — ibig sabihin, maaari tayong mag-iwan ng karamihan sa mga controlled-phase gate nang hindi masyadong nawawalan ng katumpakan.

Pangkalahatang pamamaraan at pagsusuri

Ngayon ay susuriin natin ang phase-estimation procedure sa pangkalahatan. Ang ideya ay palawigin ang two-qubit na bersyon ng phase estimation na tinalakay natin sa itaas sa natural na paraan na iminumungkahi ng sumusunod na diagram.

Pansinin na, para sa bawat bagong control qubit na idinaragdag sa itaas, dino-double natin ang bilang ng beses na isinasagawa ang unitary na operasyon na $U.$ Ito ay ipinahiwatig sa diagram sa pamamagitan ng mga kapangyarihan sa $U$ para sa bawat isa sa mga controlled-unitary na operasyon.

Ang pinakasimpleng paraan para maipatupad ang isang controlled-$U^k$ na operasyon para sa ilang pagpili ng $k$ ay ang simpleng pag-ulit ng isang controlled-$U$ na operasyon nang $k$ beses. Kung ito nga ang metodolohiyang ginagamit, dapat malaman na ang pagdaragdag ng control qubit ay malaki ang kontribusyon sa sukat ng circuit: kung mayroon tayong $m$ na control qubit, tulad ng inilalarawan ng diagram, kabuuang $2^m - 1$ na kopya ng controlled-$U$ na operasyon ang kinakailangan. Ibig sabihin, isang malaking computational na gastos ang natitikman habang tumataas ang $m$ — ngunit tulad ng makikita natin, nagdudulot din ito ng mas tumpak na approximation ng $\theta$.

Mahalaga ring tandaan, gayunpaman, na para sa ilang pagpili ng $U$ ay posibleng lumikha ng circuit na nagpapatupad ng operasyong $U^k$ para sa malalaking halaga ng $k$ nang mas mahusay kaysa sa simpleng pag-ulit ng circuit para sa $U$ nang $k$ beses. Makikita natin ang isang tiyak na halimbawa nito sa konteksto ng integer factorization mamaya sa aralin, kung saan ang mahusay na algorithm para sa modular exponentiation na tinalakay sa nakaraang aralin ay darating sa ating tulong.

Suriin natin ngayon ang circuit na inilarawan lamang. Ang estado bago pa man isagawa ang inverse quantum Fourier transform ay ganito ang hitsura:

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

Isang espesyal na kaso

Katulad ng ginawa natin sa kaso ng $m=2$, unang isasaalang-alang natin ang espesyal na kaso na $\theta = y/2^m$ para sa $y\in\{0,\ldots,2^m-1\}$. Sa kasong ito, ang estado bago ang inverse quantum Fourier transform ay maaaring isulat ding ganito:

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

Kaya, kapag naisagawa ang inverse quantum Fourier transform, ang estado ay nagiging

$$\vert\psi\rangle \vert y\rangle$$

at ang mga sukat ay nagpapakita ng $y$ (naka-encode sa binary).

Pagtatakda ng hangganan sa mga probabilidad

Para sa ibang mga halaga ng $\theta$, ibig sabihin ang mga hindi sumusunod sa anyo na $y/2^m$ para sa isang integer na $y$, ang mga resulta ng sukat ay hindi magiging tiyak, ngunit maaari nating patunayan ang mga hangganan sa mga probabilidad para sa iba't ibang resulta. Mula dito, isaalang-alang natin ang isang arbitrary na pagpili ng $\theta$ na tumutugon sa $0\leq \theta < 1$.

Pagkatapos maisagawa ang inverse quantum Fourier transform, ang estado ng circuit ay ito:

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

Kaya, kapag isinasagawa ang mga sukat sa nangungunang $m$ na qubit, makikita natin ang bawat resulta na $y$ na may probabilidad

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

Para mas maunawaan ang mga probabilidad na ito, gagamit tayo ng parehong pormula na nakita natin dati, para sa kabuuan ng paunang bahagi ng isang geometric series.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Maaari nating i-simplify ang kabuuang lumalabas sa pormula para sa $p_y$ sa pamamagitan ng pagkuha ng $\alpha = e^{2\pi i (\theta - y/2^m)}$. Narito ang nakuha natin.

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

Kaya, sa kaso na $\theta = y/2^m$, nalaman natin na ang $p_y = 1$ (tulad ng alam na natin mula sa pagsasaalang-alang ng espesyal na kasong ito), at sa kaso na $\theta \neq y/2^m$, nalaman natin na

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

Maaari tayong matuto nang higit pa tungkol sa mga probabilidad na ito sa pamamagitan ng pag-iisip tungkol sa kung paano nauugnay ang mga haba ng arc at chord sa unit circle. Narito ang isang figure na naglalarawan ng mga relasyong kailangan natin para sa anumang tunay na numero $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr]$.

Una, ang haba ng chord (iginuhit sa asul) ay hindi maaaring mas malaki kaysa sa haba ng arc (iginuhit sa lila):

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

Pag-ugnay ng mga habang ito sa kabaligtarang direksyon, nakikita natin na ang ratio ng haba ng arc sa haba ng chord ay pinakamalaki kapag $\delta = \pm 1/2$, at sa kasong ito ang ratio ay kalahati ng sirkumperensya ng bilog na hinati sa diameter, na siyang $\pi/2$. Kaya, mayroon tayong

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

at kaya

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

Isang pagsusuri batay sa mga relasyong ito ay nagpapakita ng sumusunod na dalawang katotohanan.

1. Ipagpalagay na ang $\theta$ ay isang tunay na numero at ang $y\in \{0,\ldots,2^m-1\}$ ay tumutugon sa

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

   Ibig sabihin nito, ang $y/2^m$ ay alinman sa pinakamahusay na $m$-bit na approximation sa $\theta$, o eksaktong nasa gitna sa pagitan ng $y/2^m$ at alinman sa $(y-1)/2^m$ o $(y+1)/2^m$, kaya isa ito sa dalawang pinakamahusay na approximation sa $\theta$.

   Papatunayan natin na ang $p_y$ ay medyo malaki sa kasong ito. Sa pamamagitan ng pagpapalagay na ating isinasaalang-alang, sumusunod na ang $\vert 2^m \theta - y \vert \leq 1/2$, kaya maaari nating gamitin ang pangalawang obserbasyon sa itaas tungkol sa arc at chord na haba para maisipan na

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Maaari rin nating gamitin ang unang obserbasyon tungkol sa arc at chord na haba para maisipan na

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Ang paggamit ng dalawang inequality na ito sa $p_y$ ay nagpapakita ng

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   Ipinapaliwanag nito ang ating obserbasyon na ang pinakamahusay na resulta ay nangyayari na may probabilidad na mas malaki kaysa sa $40\%$ sa $m=2$ na bersyon ng phase estimation na tinalakay natin dati. Hindi talaga ito eksaktong 40%, kundi $4/\pi^2$, at sa katunayan, ang limitasyong ito ay may bisa para sa bawat pagpili ng $m$.

2. Ngayon ipagpalagay na ang $y\in \{0,\ldots,2^m-1\}$ ay tumutugon sa

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   Ibig sabihin nito, mayroong mas mahusay na approximation na $z/2^m$ sa $\theta$ sa pagitan ng $\theta$ at $y/2^m$.

   Sa pagkakataong ito ay papatunayan natin na ang $p_y$ ay hindi masyadong malaki. Maaari tayong magsimula sa simpleng obserbasyon na

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   na sumusunod mula sa katotohanan na ang anumang dalawang punto sa unit circle ay maaaring magkaiba sa absolute value ng hindi hihigit sa $2$.

   Maaari rin nating gamitin ang pangalawang obserbasyon tungkol sa arc at chord na haba mula sa itaas, sa pagkakataong ito ay nagtatrabaho sa denominator ng $p_y$ sa halip na ang numerator, para maisipan na

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   Ang paglalagay ng dalawang inequality na magkasama ay nagpapakita ng

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   Tandaan na, habang ang limitasyong ito ay sapat para sa ating mga layunin, ito ay medyo magaspang — ang probabilidad ay karaniwang mas mababa kaysa sa $1/4$.

Ang mahalagang aral mula sa pagsusuring ito ay ang malapit na mga approximation sa $\theta$ ay malamang na mangyari — makakakuha tayo ng pinakamahusay na $m$-bit na approximation na may probabilidad na mas malaki kaysa sa $40\%$ — samantalang ang mga approximation na nalalayo nang higit sa $2^{-m}$ ay hindi gaanong malamang na mangyari, na may probabilidad na hindi hihigit sa $25\%$.

Dahil sa mga garantiyang ito, posible na palakasin ang ating kumpiyansa sa pamamagitan ng paulit-ulit na pagsasagawa ng phase estimation procedure nang ilang beses, para makakalap ng statistical na ebidensya tungkol sa $\theta$. Mahalaga ring tandaan na ang estado ng $\vert\psi\rangle$ ng ibabang koleksyon ng mga qubit ay hindi binabago ng phase estimation procedure, kaya maaari itong gamitin para patakbuhin ang pamamaraan nang maraming beses hangga't gusto natin. Sa partikular, sa bawat pagkakataon na patakbuhin natin ang circuit, makakakuha tayo ng pinakamahusay na $m$-bit na approximation sa $\theta$ na may probabilidad na mas malaki kaysa sa $40\%$, habang ang probabilidad ng paglihis nang higit sa $2^{-m}$ ay hindi hihigit sa $25\%$. Kung patakbuhin natin ang circuit nang ilang beses at kunin ang pinaka-madalas na lumalabas na resulta ng mga pagpapatakbo, lubhang malamang na ang pinaka-madalas na lumalabas na resulta ay hindi isa na nangyayari nang hindi hihigit sa $25\%$ ng oras. Bilang resulta, malamang na makakakuha tayo ng approximation na $y/2^m$ na nasa loob ng $1/2^m$ ng halaga ng $\theta$. Ang hindi malamang na pagkakataon na malayo tayo nang higit sa $1/2^m$ ay bumababa nang exponential sa bilang ng beses na isinasagawa ang pamamaraan.

Narito ang dalawang plot na nagpapakita ng mga probabilidad para sa tatlong magkakasunod na halaga ng $y$ kapag ang $m = 3$ at $m=4$ bilang mga function ng $\theta$. (Tatlong resulta lamang ang ipinapakita para sa kalinawan. Ang mga probabilidad para sa ibang mga resulta ay nakuha sa pamamagitan ng cyclically na pag-shift ng parehong pinagbabatayan na function.)