Paglalarawan ng algorithm ni Grover

Sa seksyong ito, ilalarawan natin ang algorithm ni Grover. Magsisimula tayo sa pagtalakay sa phase query gates at kung paano itayo ang mga ito, kasunod ng paglalarawan ng algorithm mismo. Sa huli, tatalakayin natin nang maikli kung paano natural na inilalapat ang algorithm na ito sa paghahanap.

Mga phase query gate

Gumagamit ang algorithm ni Grover ng mga operasyong kilala bilang phase query gates. Kaiba sa isang ordinaryong query gate na $U_f,$ na tinukoy para sa isang ibinigay na function na $f$ sa karaniwang paraan na inilarawan dati, ang phase query gate para sa function na $f$ ay tinukoy bilang

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

para sa bawat string na $x\in\Sigma^n.$

Ang operasyong $Z_f$ ay maaaring ipatupad gamit ang isang query gate na $U_f$ gaya ng iminumungkahi ng diagram na ito:

Gumagamit ang implementasyong ito ng phenomenon na phase kickback, at kailangan nitong magkaroon ng isang workspace qubit, na sinimulan sa $\vert -\rangle$ na estado. Nananatili ang qubit na ito sa $\vert - \rangle$ na estado pagkatapos makumpleto ang implementasyon, at maaaring gamitin ulit (para ipatupad ang mga kasunod na $Z_f$ gate, halimbawa) o basta itapon na lang.

Bukod sa operasyong $Z_f,$ gagamitin din natin ang isang phase query gate para sa $n$-bit OR function, na tinukoy tulad ng sumusunod para sa bawat string na $x\in\Sigma^n.$

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

Partikular, ang phase query gate para sa $n$-bit OR function ay gumagana nang ganito:

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

Para maging malinaw, ito ang paraan ng paggugunapawa ng $Z_{\mathrm{OR}}$ sa mga standard basis state; ang gawi nito sa mga arbitrary na estado ay natutukoy mula sa expression na ito sa pamamagitan ng linearity.

Ang operasyong $Z_{\mathrm{OR}}$ ay maaaring ipatupad bilang isang quantum circuit sa pamamagitan ng pagsisimula sa isang Boolean circuit para sa OR function, pagkatapos ay gumawa ng operasyong $U_{\mathrm{OR}}$ (iyon ay, isang standard query gate para sa $n$-bit OR function) gamit ang pamamaraang inilarawan sa aralin na Quantum algorithmic foundations, at sa wakas ang operasyong $Z_{\mathrm{OR}}$ gamit ang phase kickback phenomenon gaya ng inilarawan sa itaas. Pansinin na ang operasyong $Z_{\mathrm{OR}}$ ay walang depensya sa function na $f$ kaya maaari itong ipatupad ng isang quantum circuit na walang mga query gate.

Paglalarawan ng algorithm

Ngayong mayroon na tayong dalawang operasyong $Z_f$ at $Z_{\mathrm{OR}},$ maaari na nating ilarawan ang algorithm ni Grover.

Binabanggit ng algorithm ang isang bilang na $t,$ na siyang bilang ng mga iteration na ginagawa nito (at samakatuwid ang bilang ng mga query sa function na $f$ na kailangan nito). Hindi tinutukoy ng algorithm ni Grover ang bilang na $t$ na ito ayon sa ating paglalarawan, at tatalakayin natin sa ibang pagkakataon sa aralin kung paano ito pipiliin.

Algorithm ni Grover

1. I-initialize ang isang $n$ qubit register na $\mathsf{Q}$ sa all-zero state na $\vert 0^n \rangle$ at pagkatapos ay mag-apply ng Hadamard operation sa bawat qubit ng $\mathsf{Q}.$
2. I-apply nang $t$ beses ang unitary operation na $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ sa register na $\mathsf{Q}$
3. Sukatin ang mga qubit ng $\mathsf{Q}$ gamit ang mga standard basis measurement at i-output ang resultang string.

Ang operasyong $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ na paulit-ulit sa hakbang 2 ay tatawagin na Grover operation sa natitirang bahagi ng araling ito. Narito ang isang quantum circuit na representasyon ng Grover operation kapag $n=7\!:$

Sa diagram na ito, ang operasyong $Z_f$ ay inilalarawan na mas malaki kaysa sa $Z_{\mathrm{OR}}$ bilang isang impormal na biswal na pahiwatig na malamang na ito ang mas mahal na operasyon. Partikular, kapag nagtatrabaho tayo sa loob ng query model, ang $Z_f$ ay nangangailangan ng isang query habang ang $Z_{\mathrm{OR}}$ ay hindi nangangailangan ng mga query. Kung sa halip mayroon tayong Boolean circuit para sa function na $f,$ at pagkatapos ay i-convert ito sa isang quantum circuit para sa $Z_f,$ maaari tayong makatwirang asahan na ang resultang quantum circuit ay magiging mas malaki at mas kumplikado kaysa sa isang para sa $Z_{\mathrm{OR}}.$

Narito ang isang diagram ng isang quantum circuit para sa buong algorithm kapag $n=7$ at $t=3.$ Para sa mas malalaking halaga ng $t$ maaari tayong magsingit ng mga karagdagang instance ng Grover operation agad bago ang mga sukat.

Paglalapat sa paghahanap

Ang algorithm ni Grover ay maaaring ilapat sa problemang Search tulad ng sumusunod:

• Pumili ng bilang na $t$ sa hakbang 2. (Ito ay tatalakayin sa ibang pagkakataon sa aralin.)
• Patakbuhin ang algorithm ni Grover sa function na $f,$ gamit ang anumang pagpili na ginawa natin para sa $t,$ para makakuha ng string na $x\in\Sigma^n.$
• I-query ang function na $f$ sa string na $x$ para malaman kung ito ay valid na solusyon:
  • Kung $f(x) = 1,$ nakahanap na tayo ng solusyon, kaya maaari tayong huminto at i-output ang $x.$
  • Kung hindi, kung $f(x) = 0,$ maaari tayong muling patakbuhin ang pamamaraan, posibleng may ibang pagpili para sa $t,$ o maaari tayong magpasyang sumuko at i-output ang "walang solusyon."

Kapag nasuri na natin kung paano gumagana ang algorithm ni Grover, makikita natin na sa pag-take ng $t = O(\sqrt{N}),$ makakakuha tayo ng solusyon sa ating search problem (kung mayroon) nang may mataas na posibilidad.