Pagsusuri

Susuriin natin ngayon ang Grover's algorithm para maunawaan kung paano ito gumagana. Magsisimula tayo sa isang uri ng simbolikong pagsusuri, kung saan kinakalkula natin kung paano kumikilos ang Grover operation na $G$ sa ilang partikular na estado, at pagkatapos ay iuugnay natin ang simbolikong pagsusuring ito sa isang geometric na larawan na nakakatulong para maislarawan kung paano gumagana ang algorithm.

Mga solusyon at hindi solusyon

Magsimula tayo sa pamamagitan ng pagtukoy ng dalawang set ng mga string.

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

Ang set na $A_1$ ay naglalaman ng lahat ng solusyon sa ating problema sa paghahanap, habang ang $A_0$ naman ay naglalaman ng mga string na hindi solusyon (na maaari nating tawaging hindi-solusyon kung maginhawa). Ang dalawang set na ito ay nagsasatisfy ng $A_0 \cap A_1 = \varnothing$ at $A_0 \cup A_1 = \Sigma^n,$ ibig sabihin, ito ay isang bipartition ng $\Sigma^n.$

Susunod, tutukuyin natin ang dalawang unit vector na kumakatawan sa mga uniform superposition sa mga set ng solusyon at hindi-solusyon.

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

Sa teknikal na pagsasalita, ang bawat isa sa mga vector na ito ay natutukoy lamang kapag ang kaukulang set ay hindi walang laman, ngunit mula rito ay magtutuon tayo sa kasong hindi walang laman ang $A_0$ at $A_1$. Ang mga kaso na $A_0 = \varnothing$ at $A_1 = \varnothing$ ay madaling harapin nang hiwalay, at gagawin natin ito mamaya.

Sa karagdagan, ang notasyong ginagamit dito ay karaniwan: sa tuwing mayroon tayong finite at hindi walang lamang set na $S,$ maaari tayong magsulat ng $\vert S\rangle$ para ilarawan ang quantum state vector na uniform sa mga elemento ng $S.$

Tukuyin din natin ang $\vert u \rangle$ bilang isang uniform quantum state sa lahat ng $n$-bit string:

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

Pansinin na

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

Mayroon din tayong $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle,$ kaya ang $\vert u\rangle$ ay kumakatawan sa estado ng register na $\mathsf{Q}$ pagkatapos ng initialization sa hakbang 1 ng Grover's algorithm.

Ibig sabihin nito, bago pa mangyari ang mga iteration ng $G$ sa hakbang 2, ang estado ng $\mathsf{Q}$ ay nasa loob ng two-dimensional vector space na spanned ng $\vert A_0\rangle$ at $\vert A_1\rangle,$ at bukod doon, ang mga coefficient ng mga vector na ito ay mga tunay na numero. Makikita natin na ang estado ng $\mathsf{Q}$ ay palaging magkakaroon ng mga katangiang ito — ibig sabihin, ang estado ay isang tunay na linear combination ng $\vert A_0\rangle$ at $\vert A_1\rangle$ — pagkatapos ng anumang bilang ng iteration ng operation na $G$ sa hakbang 2.

Isang obserbasyon tungkol sa Grover operation

Titingnan natin ngayon ang Grover operation

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

simula sa isang kawili-wiling obserbasyon tungkol dito.

Isipin nang sandali na pinalitan natin ang function na $f$ ng composition ng $f$ at ng NOT function — o, sa madaling salita, ang function na nakukuha natin sa pamamagitan ng pag-flip ng output bit ng $f.$ Tatawagin natin itong bagong function na $g,$ at maaari nating ipahayag ito gamit ang mga simbolo sa ilang alternatibong paraan.

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

Pansinin na

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

para sa bawat string na $x\in\Sigma^n,$ at samakatuwid

$$Z_g = - Z_f.$$

Ibig sabihin nito, kung papalitan natin ang function na $f$ ng function na $g,$ hindi magbabago ang Grover's algorithm — dahil ang mga estado na nakukuha natin mula sa algorithm sa dalawang kaso ay kinakailangang katumbas hanggang sa isang global phase.

Wala itong problema! Sa simpleng pagsasalita, hindi pinapansin ng algorithm kung aling mga string ang solusyon at aling mga string ang hindi — kailangan lang nitong makilala ang mga solusyon at hindi-solusyon para gumana nang tama.

Kilos ng Grover operation

Tingnan natin ngayon ang kilos ng $G$ sa mga quantum state vector na $\vert A_0\rangle$ at $\vert A_1\rangle.$

Una, pansinin na ang operation na $Z_f$ ay may napakasimpleng kilos sa $\vert A_0\rangle$ at $\vert A_1\rangle.$

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

Pangalawa, mayroon tayong operation na $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ Ang operation na $Z_{\mathrm{OR}}$ ay tinukoy bilang

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[2mm] -\vert x\rangle & x \neq 0^n, \end{cases}$$

muli para sa bawat string na $x\in\Sigma^n,$ at ang isang maginhawang alternatibong paraan ng pagpapahayag ng operation na ito ay ganito:

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

Ang isang simpleng paraan para i-verify na ang expression na ito ay naaayon sa kahulugan ng $Z_{\mathrm{OR}}$ ay ang suriin ang kilos nito sa mga standard basis state.

Ang operation na $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ ay maaaring isulat nang ganito:

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

gamit ang parehong notasyon, $\vert u \rangle,$ na ginamit natin sa itaas para sa uniform superposition sa lahat ng $n$-bit string.

At ngayon mayroon na tayong kailangan para kalkulahin ang kilos ng $G$ sa $\vert A_0\rangle$ at $\vert A_1\rangle.$ Una, kalkulahin natin ang kilos ng $G$ sa $\vert A_0\rangle.$

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

At pangalawa, kalkulahin natin ang kilos ng $G$ sa $\vert A_1\rangle.$

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

Sa dalawang kaso, ginagamit natin ang equation na

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

kasama ang mga expression na

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{and}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

na sumusunod.

Sa buod, mayroon tayong

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

Tulad ng nabanggit na natin, ang estado ng $\mathsf{Q}$ bago pa mangyari ang hakbang 2 ay nasa loob ng two-dimensional space na spanned ng $\vert A_0\rangle$ at $\vert A_1\rangle,$ at napatunayan na natin na ang $G$ ay nagmamapa ng anumang vector sa space na ito patungo sa isa pang vector sa parehong space. Ibig sabihin nito, para sa layunin ng pagsusuri, maaari nating itutok ang ating atensyon nang eksklusibo sa subspace na ito.

Para mas maunawaan kung ano ang nangyayari sa loob ng two-dimensional space na ito, ipahayag natin ang kilos ng $G$ sa space na ito bilang isang matrix,

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

kung saan ang una at ikalawang row/column ay naaayon sa $\vert A_0\rangle$ at $\vert A_1\rangle,$ ayon sa pagkakasunod. Sa ngayon sa seryeng ito, palagi tayong nag-uugnay ng mga row at column ng mga matrix sa mga classical state ng isang sistema, ngunit ang mga matrix ay maaari ring gamitin para ilarawan ang mga kilos ng mga linear mapping sa iba't ibang basis tulad ng mayroon tayo dito.

Bagaman hindi ito halatang makikita sa unang tingin, ang matrix na $M$ ay ang makukuha natin sa pamamagitan ng pag-square ng isang mas simpleng matrix.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

Ang matrix na

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

ay isang rotation matrix, na maaari rin nating ipahayag bilang

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

para sa

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr).$$

Ang angle na $\theta$ ay magkakaroon ng napakahalagang papel sa pagsusuring susunod, kaya sulit na bigyang-diin ang kahalagahan nito dito habang nakikita natin ito sa unang pagkakataon.

Sa liwanag ng expression na ito ng matrix, mapapansing

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

Ito ay dahil ang pag-rotate ng angle na $\theta$ nang dalawang beses ay katumbas ng pag-rotate ng angle na $2\theta.$ Ang isa pang paraan para makita ito ay ang gamitin ang alternatibong expression na

$$\theta = \cos^{-1}\biggl(\sqrt{\frac{\vert A_0\vert}{N}}\biggr),$$

kasama ang mga double angle formula mula sa trigonometry:

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

Sa buod, ang estado ng register na $\mathsf{Q}$ sa simula ng hakbang 2 ay

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

at ang epekto ng pag-apply ng $G$ sa estado na ito ay ang pag-rotate nito ng angle na $2\theta$ sa loob ng space na spanned ng $\vert A_0\rangle$ at $\vert A_1\rangle.$ Halimbawa, mayroon tayong

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

at sa pangkalahatan

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle.$$

Geometric na larawan

Iuugnay natin ngayon ang pagsusuring dumaan tayo kanina sa isang geometric na larawan. Ang ideya ay ang operation na $G$ ay produkto ng dalawang reflection, $Z_f$ at $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ At ang net effect ng pagsasagawa ng dalawang reflection ay ang pagsasagawa ng isang rotation.

Magsimula tayo sa $Z_f.$ Tulad ng naobserbahan na natin kanina, mayroon tayong

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

Sa loob ng two-dimensional vector space na spanned ng $\vert A_0\rangle$ at $\vert A_1\rangle,$ ito ay isang reflection tungkol sa linya na parallel sa $\vert A_0\rangle,$ na tatawagin nating $L_1.$ Narito ang isang figure na naglalarawan ng kilos ng reflection na ito sa isang hypothetical unit vector na $\vert\psi\rangle,$ na inaasahan nating isang tunay na linear combination ng $\vert A_0\rangle$ at $\vert A_1\rangle.$

Pangalawa, mayroon tayong operation na $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$ na nakita na nating maaaring isulat bilang

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

Ito rin ay isang reflection, sa pagkakataong ito tungkol sa linya $L_2$ na parallel sa vector na $\vert u\rangle.$ Narito ang isang figure na naglalarawan ng kilos ng reflection na ito sa isang unit vector na $\vert\psi\rangle.$

Kapag sinama natin ang dalawang reflection na ito, nakakakuha tayo ng rotation — ng dalawang beses ang angle sa pagitan ng mga linya ng reflection — tulad ng inilalarawan ng figure na ito.

Ipinapaliwanag nito, sa geometric na termino, kung bakit ang epekto ng Grover operation ay ang pag-rotate ng mga linear combination ng $\vert A_0\rangle$ at $\vert A_1\rangle$ ng angle na $2\theta.$