Pagpili ng bilang ng iterations

Napatunayan na natin na ang state vector ng register $\mathsf{Q}$ sa Grover's algorithm ay nananatili sa two-dimensional subspace na sinasaklaw ng $\vert A_0\rangle$ at $\vert A_1\rangle$ kapag natapos na ang initialization step.

Ang layunin ay mahanap ang isang elemento $x\in A_1,$ at maaabot ito kung makukuha natin ang state $\vert A_1\rangle$ — dahil kapag sinukat natin ang state na ito, garantisadong makukuha natin ang measurement outcome na $x\in A_1.$ Dahil ang state ng $\mathsf{Q}$ pagkatapos ng $t$ iterations sa step 2 ay

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

dapat nating piliin ang $t$ upang

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

ay maging kalapit ng $1$ hangga't maaari sa absolute value, para mapalaki ang probabilidad na makakuha ng $x\in A_1$ mula sa measurement. Para sa anumang anggulo $\theta \in (0,2\pi),$ ang halaga ng $\sin((2t + 1)\theta)$ ay nag-o-oscillate habang tumataas ang $t$, kahit hindi ito kailangang peryodiko — walang garantiya na makukuha natin ang parehong halaga ng dalawang beses.

Natural na, bukod sa pagiging malaki ng probabilidad na makakuha ng elemento $x\in A_1$ mula sa measurement, nais din nating piliin ang pinakamaliit na $t$ hangga't maaari, dahil ang $t$ na aplikasyon ng operasyon $G$ ay nangangailangan ng $t$ na queries sa function $f.$ Dahil layunin nating gawing malapit sa $1$ ang $\sin( (2t + 1) \theta)$ sa absolute value, isang natural na paraan ay ang pumili ng $t$ upang

$$(2t + 1) \theta \approx \frac{\pi}{2}.$$

Kapag sinolve para sa $t$ makukuha natin ang

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

Siyempre, dapat integer ang $t$, kaya hindi natin palaging maaabot nang eksakto ang halagang ito — ngunit ang magagawa natin ay ang kumuha ng pinakamalapit na integer sa halagang ito, na kung saan ay

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

Ito ang inirerekomendang bilang ng iterations para sa Grover's algorithm. Habang tinatapusin ang pagsusuri, makikita natin na ang pagiging malapit ng integer na ito sa target na halaga ay natural na nakakaapekto sa performance ng algorithm.

(Bilang paalala, kung ang target na halaga na $\pi/(4\theta) - 1/2$ ay eksaktong nasa kalagitnaan ng dalawang integer, ang expression na ito ng $t$ ang makukuha sa pamamagitan ng pag-round up. Maaari ring i-round down, na mas makatuwirang gawin dahil nangangahulugang isang query na mas kaunti — ngunit ito ay pangalawa at hindi mahalaga para sa layunin ng aralin.)

Alalahanin na ang halaga ng anggulo $\theta$ ay ibinibigay ng formula

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

makikita natin na ang inirerekomendang bilang ng iterations na $t$ ay nakasalalay sa bilang ng mga string sa $A_1.$ Nagdudulot ito ng hamon kung hindi natin alam kung gaano karaming solusyon mayroon tayo, tulad ng tatalakayin natin sa ibang pagkakataon.

Natatanging paghahanap

Una, tukuyin natin ang sitwasyon kung saan mayroon lamang isang string na $x$ na $f(x)=1.$ Isa pang paraan ng pagsabi nito ay isinasaalang-alang natin ang isang instance ng problema ng Unique search. Sa kasong ito mayroon tayong

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

na maaaring maginhawang i-approximate bilang

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

kapag nagiging malaki ang $N.$ Kung papalitan natin ng $\theta = 1/\sqrt{N}$ sa expression na

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

makukuha natin

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

Alalahanin na ang $t$ ay hindi lamang ang bilang ng beses na ginagawa ang operasyon $G$, kundi pati na rin ang bilang ng queries sa function $f$ na kailangan ng algorithm, kaya nakikita nating papalapit na tayo sa pagkuha ng algorithm na nangangailangan ng $O(\sqrt{N})$ na queries.

Ngayon ay susuriin natin kung gaano kahusay ang inirerekomendang pagpili ng $t.$ Ang probabilidad na ang panghuling measurement ay magreresulta sa natatanging solusyon ay maaaring ipahayag nang malinaw bilang

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

Ang unang argument, $N,$ ay tumutukoy sa bilang ng mga item na hinahanap natin, at ang pangalawang argument, na $1$ sa kasong ito, ay tumutukoy sa bilang ng mga solusyon. Kalaunan ay gagamitin natin ang parehong notasyon nang mas pangkalahataan, kung saan may maramihang solusyon.

Narito ang isang talahanayan ng mga probabilidad ng tagumpay para sa mga tumataas na halaga ng $N = 2^n.$

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

Pansinin na ang mga probabilidad na ito ay hindi mahigpit na tumataas. Partikular na, may kagiliw-giliw na anomalya kapag $N=4,$ kung saan nakakakuha tayo ng solusyon nang may katiyakan. Ngunit maaaring mapatunayan sa pangkalahatan na

$$p(N,1) \geq 1 - \frac{1}{N}$$

para sa lahat ng $N,$ kaya ang probabilidad ng tagumpay ay papalapit sa $1$ sa limitasyon habang nagiging malaki ang $N,$ tulad ng iminumungkahi ng mga halagang nabanggit sa itaas. Maganda ito!

Ngunit pansinin, gayunpaman, na kahit isang mahinang hangganan tulad ng $p(N,1) \geq 1/2$ ay nagpapatunay ng utility ng Grover's algorithm. Para sa anumang measurement outcome na $x$ na makukuha natin mula sa pagpapatakbo ng pamamaraan, palagi nating masusuri kung $f(x) = 1$ gamit ang isang query sa $f.$ At kung mabigo tayong makuha ang natatanging string $x$ na $f(x) = 1$ na may probabilidad na hindi hihigit sa $1/2$ sa isang pagpapatakbo ng pamamaraan, pagkatapos ng $m$ na magkakalayong pagpapatakbo ng pamamaraan ay mabibigo tayong makuha ang natatanging string $x$ na ito na may probabilidad na hindi hihigit sa $2^{-m}.$ Ibig sabihin, gamit ang $O(m \sqrt{N})$ na queries sa $f,$ makukuha natin ang natatanging solusyon $x$ na may probabilidad na hindi bababa sa $1 - 2^{-m}.$ Gamit ang mas mahusay na hangganan na $p(N,1) \geq 1 - 1/N$ makikita na ang probabilidad ng paghanap ng $x\in A_1$ gamit ang pamamaraang ito ay talagang hindi bababa sa $1 - N^{-m}.$

Maramihang solusyon

Habang nagbabago ang bilang ng mga elemento sa $A_1$, nagbabago rin ang anggulo $\theta,$ na maaaring magkaroon ng malaking epekto sa probabilidad ng tagumpay ng algorithm. Para sa brevity, isulat natin ang $s = \vert A_1 \vert$ upang tukuyin ang bilang ng mga solusyon, at tulad ng dati ay ipagpalagay nating $s\geq 1.$

Bilang motivating example, isipin natin na mayroon tayong $s = 4$ na solusyon sa halip na isang solusyon, tulad ng tiningnan natin sa itaas. Ibig sabihin nito

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

na halos doble ng anggulo na mayroon tayo sa kaso ng $\vert A_1 \vert = 1$ kapag malaki ang $N.$ Ipagpalagay nating hindi natin alam nang mas mabuti, at pinili ang parehong halaga ng $t$ tulad sa setting ng natatanging solusyon:

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

Ang epekto ay magiging mapaminsala tulad ng ipinapakita ng sumusunod na talahanayan ng mga probabilidad.

$$\begin{array}{ll} N & \text{Success probability}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

Sa pagkakataong ito ang probabilidad ng tagumpay ay papalapit sa $0$ habang lumalaki ang $N.$ Nangyayari ito dahil epektibo tayong umiikot nang doble ang bilis kumpara sa noong may natatanging solusyon, kaya nalalampasan natin ang target na $\vert A_1\rangle$ at napupunta malapit sa $-\vert A_0\rangle.$

Gayunpaman, kung gagamitin natin ang inirerekomendang pagpili ng $t,$ na kung saan ay

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

para sa

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

mas maganda ang magiging performance. Upang maging mas tiyak, ang paggamit ng pagpiling ito ng $t$ ay nagdudulot ng tagumpay na may mataas na probabilidad.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

Ginagawang pangkalahataan ang nabanggit nang mas maaga, maaaring mapatunayan na

$$p(N,s) \geq 1 - \frac{s}{N},$$

kung saan ginagamit natin ang notasyong iminungkahi nang mas maaga: ang $p(N,s)$ ay tumutukoy sa probabilidad na ang Grover's algorithm na pinatakbo para sa $t$ na iterations ay magsisiwalat ng solusyon kapag mayroon $s$ na solusyon sa kabuuan mula sa $N$ na posibilidad.

Ang lower bound na ito na $1 - s/N$ sa probabilidad ng tagumpay ay medyo kakaiba dahil ang mas maraming solusyon ay nagbibigay ng mas masamang lower bound — ngunit sa ilalim ng pagpapalagay na ang $s$ ay makabuluhang mas maliit kaysa $N,$ maaari pa ring masabi natin na ang probabilidad ng tagumpay ay medyo mataas. Tulad ng dati, ang katotohanan lamang na ang $p(N,s)$ ay medyo malaki ay nagpapatunay ng utility ng algorithm.

Nangyayari rin na

$$p(N,s) \geq \frac{s}{N}.$$

Ang lower bound na ito ay naglalarawan ng probabilidad na ang isang string na $x\in\Sigma^n$ na pinili nang random ay isang solusyon — kaya ang Grover's algorithm ay palaging hindi bababa sa random guessing. (Sa katunayan, kapag $t=0,$ ang Grover's algorithm ay random guessing.)

Ngayon tingnan natin ang bilang ng iterations (at samakatuwid ang bilang ng queries)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

para sa

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

Para sa bawat $\alpha \in [0,1],$ totoo na ang $\sin^{-1}(\alpha)\geq \alpha,$ kaya

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

Ipinapahiwatig nito na

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

Nagdudulot ito ng pagtitipid sa bilang ng queries habang lumalaki ang $s.$ Partikular na, ang kinakailangang bilang ng queries ay

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

Hindi kilalang bilang ng solusyon

Kung ang bilang ng mga solusyon na $s = \vert A_1 \vert$ ay hindi kilala, kailangan ng ibang diskarte, dahil sa sitwasyong ito wala tayong kaalaman sa $s$ na magbibigay-impormasyon sa ating pagpili ng $t.$ Sa katunayan, mayroon pang maraming diskarte.

Isang simpleng diskarte ay ang pumili ng

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

nang random na pantay-pantay. Ang pagpili ng $t$ sa ganitong paraan ay palaging nakakahanap ng solusyon (kung mayroon man) na may probabilidad na higit sa 40%, kahit hindi ito halata at nangangailangan ng pagsusuri na hindi isasama dito. Makatuwiran naman ito, partikular na kapag iniisip natin ang geometric na larawan: ang pag-ikot ng state ng $\mathsf{Q}$ nang random na bilang ng beses tulad nito ay hindi iba sa pagpili ng random na unit vector sa space na sinasaklaw ng $\vert A_0\rangle$ at $\vert A_1\rangle,$ na para sa mga iyon ay malamang na malaki ang coefficient ng $\vert A_1\rangle.$ Sa pamamagitan ng pag-uulit ng pamamaraang ito at pagsusuri ng outcome sa parehong paraan tulad ng inilarawan nang mas maaga, ang probabilidad na mahanap ang solusyon ay maaaring gawing malapit sa $1.$

Mayroong isang pinahusay na pamamaraan na nakakahanap ng solusyon kapag mayroon gamit ang $O(\sqrt{N/s})$ na queries, kahit hindi kilala ang bilang ng solusyon na $s$, at nangangailangan ng $O(\sqrt{N})$ na queries upang matukoy na walang solusyon kapag $s=0.$

Ang pangunahing ideya ay ang pumili ng $t$ nang random mula sa set na $\{1,\ldots,T\}$ nang paulit-ulit, para sa mga tumataas na halaga ng $T.$ Partikular na, maaari tayong magsimula sa $T = 1$ at taasan ito nang exponential, palaging tinatatapos ang proseso sa sandaling mahanap ang solusyon at nililimitahan ang $T$ upang hindi masayang ang mga queries kapag walang solusyon. Ginagamit ng proseso ang katotohanan na mas kaunting queries ang kailangan kapag mas maraming solusyon. Ngunit kailangan ng ilang pag-iingat upang balansehin ang rate ng paglaki ng $T$ sa probabilidad ng tagumpay para sa bawat iteration. (Ang paggamit ng $T \leftarrow \lceil \frac{5}{4}T\rceil$ ay gumagana, halimbawa, tulad ng ipinapakita ng pagsusuri. Ang pag-double ng $T,$ gayunpaman, ay hindi gumagana — ito pala ay masyadong mabilis na pagtaas.)

Ang mga trivial na kaso

Sa buong pagsusuri na ginawa natin ngayon, ipinagpalagay natin na ang bilang ng mga solusyon ay hindi zero. Sa katunayan, sa pamamagitan ng pagtukoy sa mga vector

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

impliside nating ipinagpalagay na ang $A_0$ at $A_1$ ay parehong hindi walang laman. Dito natin titingnan nang maikli kung ano ang nangyayari kapag isa sa mga set na ito ay walang laman.

Bago pa man natin simulan ang pagsusuri, pansinin ang halata: kung bawat string na $x\in\Sigma^n$ ay isang solusyon, makikita natin ang solusyon kapag nasukat natin; at kapag walang solusyon, hindi natin makikita ang isa. Sa ilang paraan ay hindi na kailangang pumunta pa nang mas malalim kaysa dito.

Maaari nating, gayunpaman, mabilis na i-verify ang matematika para sa mga trivial na kasong ito. Ang sitwasyon kung saan isa sa $A_0$ at $A_1$ ay walang laman ay nangyayari kapag constant ang $f$; ang $A_1$ ay walang laman kapag $f(x) = 0$ para sa bawat $x\in\Sigma^n,$ at ang $A_0$ ay walang laman kapag $f(x) = 1$ para sa bawat $x\in\Sigma^n.$ Ibig sabihin nito

$$Z_f \vert u\rangle = \pm \vert u\rangle,$$

at samakatuwid

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

Kaya, anuman ang bilang ng iterations na $t$ na ginagawa natin sa mga kasong ito, ang mga measurement ay palaging magsisiwalat ng uniform random string na $x\in\Sigma^n.$