Algoritmo ni Grover

Para sa Qiskit in Classrooms module na ito, kailangan ng mga estudyante ng isang gumaganang Python environment na may mga sumusunod na naka-install na package:

• qiskit v2.1.0 o mas bago
• qiskit-ibm-runtime v0.40.1 o mas bago
• qiskit-aer v0.17.0 o mas bago
• qiskit.visualization
• numpy
• pylatexenc

Para i-set up at i-install ang mga package sa itaas, tingnan ang gabay na I-install ang Qiskit. Para makapagpatakbo ng mga trabaho sa tunay na mga quantum computer, kailangan ng mga estudyante na mag-set up ng account sa IBM Quantum® sa pamamagitan ng pagsunod sa mga hakbang sa gabay na I-set up ang iyong IBM Cloud account.

Ang module na ito ay nasubok at gumamit ng 12 segundo ng QPU time. Ito ay isang mabuting-loob na pagtatantya; ang iyong aktwal na paggamit ay maaaring mag-iba.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Panimula

Ang algoritmo ni Grover ay isang pangunahing quantum algorithm na tumutugon sa problema ng hindi nakaayos na paghahanap: kapag may isang hanay ng $N$ na mga aytem at isang paraan para suriin kung ang isang partikular na aytem ang hinahanap mo, gaano kabilis mo mahahanap ang nais na aytem? Sa klasikal na computing, kung ang data ay hindi nakaayos at walang istraktura na magagamit, ang pinakamainam na diskarte ay ang suriin ang bawat aytem nang isa-isa, na humahantong sa query complexity na $O(N)$ — sa karaniwan, kailangan mong suriin ang halos kalahati ng mga aytem bago mahanap ang target.

Ang algoritmo ni Grover, na ipinakilala ni Lov Grover noong 1996, ay nagpapakita kung paano malulutas ng isang quantum computer ang problemang ito nang mas mahusay, na nangangailangan lamang ng $O(\sqrt{N})$ na mga hakbang para mahanap ang minarkahang aytem nang may mataas na posibilidad. Kumakatawan ito sa isang quadratic speedup kumpara sa mga klasikal na pamamaraan, na mahalaga para sa malalaking dataset.

Ang algoritmo ay gumagana sa sumusunod na konteksto:

• Setup ng problema: Mayroon kang isang function na $f(x)$ na nagbabalik ng 1 kung ang $x$ ang aytem na hinahanap mo, at 0 kung hindi. Ang function na ito ay madalas na tinatawag na oracle o black box, dahil ang tanging paraan mo para malaman ang tungkol sa data ay sa pamamagitan ng pagtatanong kay $f(x)$.
• Pagiging kapaki-pakinabang ng quantum: Habang ang mga klasikal na algorithm para sa problemang ito ay nangangailangan, sa karaniwan, ng $N/2$ na mga query, ang algoritmo ni Grover ay makakahanap ng solusyon sa humigit-kumulang $\pi\sqrt{N}/4$ na mga query, na mas mabilis para sa malaking $N$.
• Kung paano ito gumagana (sa mataas na antas):
  • Una, nilikha ng quantum computer ang isang superposition ng lahat ng posibleng estado, na kumakatawan sa lahat ng posibleng aytem nang sabay-sabay.
  • Pagkatapos, paulit-ulit nitong inilalapat ang isang serye ng mga quantum operation (ang Grover iteration) na nagpapalaki ng posibilidad ng tamang sagot at nagpapaliit sa iba.
  • Pagkatapos ng sapat na mga ulit, ang pagsukat ng quantum state ay nagbubunga ng tamang sagot nang may mataas na posibilidad.

Narito ang isang napaka-simpleng diagram ng algoritmo ni Grover na lumalaktaw sa maraming detalye. Para sa mas detalyadong diagram, tingnan ang paper na ito.

Ilang mga bagay na dapat pansinin tungkol sa algoritmo ni Grover:

• Ito ay pinakamainam para sa hindi nakaayos na paghahanap: walang quantum algorithm ang makakalutas ng problema nang may mas kaunti pang $O(\sqrt{N})$ na mga query.
• Nagbibigay lamang ito ng quadratic, hindi exponential, speedup — hindi katulad ng ilang ibang quantum algorithm (halimbawa, ang algoritmo ni Shor para sa factoring).
• Mayroon itong mga praktikal na implikasyon, tulad ng posibilidad na mapabilis ang mga brute-force na pag-atake sa mga cryptographic system, kahit ang speedup ay hindi sapat para sirain ang karamihan ng modernong encryption sa sarili nitong lakas.

Para sa mga undergraduate na estudyante na pamilyar sa mga pangunahing konsepto ng computing at mga query model, ang algoritmo ni Grover ay nagbibigay ng malinaw na ilustrasyon kung paano maaaring mahigitan ng quantum computing ang mga klasikal na diskarte para sa ilang partikular na problema, kahit ang pagpapabuti ay "tanging" quadratic lamang. Nagsisilbi rin itong daan para maunawaan ang mas advanced na mga quantum algorithm at ang mas malawak na potensyal ng quantum computing.

Ang amplitude amplification ay isang pangkalahatang layunin na quantum algorithm, o subroutine, na maaaring gamitin para makakuha ng quadratic speedup kumpara sa iilang klasikal na algorithm. Ang algoritmo ni Grover ang una na nagpakita ng speedup na ito sa mga problema ng hindi nakaayos na paghahanap. Ang pagbuo ng isang Grover search problem ay nangangailangan ng isang oracle function na nagmamarka ng isa o higit pang mga computational basis state bilang mga estado na nais naming hanapin, at isang amplification circuit na nagpapalaki ng amplitude ng mga minarkahang estado, na nagpipigil sa natitirang mga estado.

Dito, ipinapakita namin kung paano bumuo ng mga Grover oracle at gamitin ang GroverOperator mula sa Qiskit circuit library para madaling mag-set up ng isang Grover search instance. Ang runtime Sampler primitive ay nagbibigay-daan sa maayos na pagpapatupad ng mga Grover circuit.

Teorya

Ipagpalagay na mayroon itong function na $f$ na nagmamapa ng mga binary string sa isang solong binary variable, ibig sabihin

$$f: \Sigma^n \rightarrow \Sigma$$

Isang halimbawa na tinukoy sa $\Sigma^6$ ay

$$f(x)= \begin{cases} 1 \qquad \text{if }x=\{010101\}\\ 0 \qquad \text{otherwise } \end{cases}$$

Isa pang halimbawa na tinukoy sa $\Sigma^{2n}$ ay

$$f(x)= \begin{cases} 1 \qquad \text{if equal numbers of 1's and 0's in string}\\ 0 \qquad \text{otherwise } \end{cases}$$

Ang iyong gawain ay hanapin ang mga quantum state na tumutugma sa mga argumento $x$ ng $f(x)$ na nakamap sa 1. Sa ibang salita, hanapin ang lahat ng $\{x_1\}\in \Sigma^n$ na kung saan ang $f(x_1)=1$ (o kung walang solusyon, iulat iyon). Ang mga hindi solusyon ay tinutukoy namin bilang $x_0$. Siyempre, gagawin natin ito sa isang quantum computer, gamit ang mga quantum state, kaya kapaki-pakinabang na ipahayag ang mga binary string na ito bilang mga estado:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

Gamit ang notasyong quantum state (Dirac), naghahanap tayo ng isa o higit pang espesyal na estado $\{|x_1\rangle\}$ sa isang hanay ng $N=2^n$ na posibleng estado, kung saan ang $n$ ay ang bilang ng mga qubit, at ang mga hindi solusyon ay tinutukoy ng $\{|x_0\rangle\}.$

Maaari nating isipin ang function na $f$ bilang ibinibigay ng isang oracle: isang black-box na maaari nating i-query para matukoy ang epekto nito sa isang estado $|x\rangle.$ Sa praktis, madalas nating malalaman ang function, ngunit maaaring napakakomplikadong ipatupad, na nangangahulugang ang pagbabawas ng bilang ng mga query o aplikasyon ng $f$ ay maaaring mahalaga. Bilang kahalili, maaari nating isipin ang isang paradigma kung saan ang isang tao ay nagtatanong sa isang oracle na kinokontrol ng isa pang tao, upang hindi natin alam ang oracle function, alam lang natin ang epekto nito sa partikular na mga estado mula sa pag-query.

Ito ay isang "problema ng hindi nakaayos na paghahanap", dahil walang espesyal sa $f$ na tumutulong sa atin sa ating paghahanap. Ang mga output ay hindi nakaayos at ang mga solusyon ay hindi alam na magkakasamang makikita, at iba pa. Isaalang-alang ang paggamit ng lumang, papel na phone book bilang analohiya. Ang hindi nakaayos na paghahanap na ito ay katulad ng pag-scan nito para hanapin ang isang partikular na numero, at hindi katulad ng paghahanap sa pamamagitan ng isang nakaayos na listahan ng mga pangalan.

Sa kaso kung saan isang solusyon ang hinahanap, klasikal na, nangangailangan ito ng bilang ng mga query na linear sa $N$. Malinaw na maaari mong mahanap ang isang solusyon sa unang pagsubok, o maaaring wala kang mahanap na solusyon sa unang $N-1$ na hula, upang kailangan mong i-query ang $N^{th}$ na input para makita kung mayroon bang anumang solusyon. Dahil ang mga function ay walang magagamit na istraktura, kakailanganin mo ng $N/2$ na mga hula sa karaniwan. Ang algoritmo ni Grover ay nangangailangan ng bilang ng mga query o computations ng $f$ na lumalaki tulad ng $\sqrt{N}.$

Buod ng mga circuit sa Algoritmo ni Grover

Ang isang kumpletong mathematical na walkthrough ng algoritmo ni Grover ay matatagpuan, halimbawa, sa Mga Pangunahing Kaalaman ng Quantum Algorithms, isang kurso ni John Watrous sa IBM Quantum Learning. Isang pinaikling pagtrato ang ibinibigay sa isang apendiks sa dulo ng module na ito. Ngunit sa ngayon, susuriin lamang natin ang pangkalahatang istraktura ng quantum circuit na nagpapatupad ng algoritmo ni Grover.

Ang algoritmo ni Grover ay maaaring hatiin sa mga sumusunod na yugto:

• Paghahanda ng isang paunang superposition (pag-apply ng mga Hadamard gate sa lahat ng qubit)
• "Pagmamarka" sa target na estado/s na may phase flip
• Isang "diffusion" na yugto kung saan ang mga Hadamard gate at isang phase flip ay inilalapat sa lahat ng qubit.
• Posibleng mga paulit-ulit na pagmamarka at diffusion na yugto para mapakinabangan ang posibilidad ng pagsukat sa target na estado
• Pagsukat

Kadalasan, ang marking gate na $Z_f$ at ang mga diffusion layer na binubuo ng $H,$ $Z_{\text{OR}},$ at $H$ ay sama-samang tinutukoy bilang "Grover operator". Sa diagram na ito, isang paulit-ulit lamang ng Grover operator ang ipinapakita.

Ang mga Hadamard gate na $H$ ay kilala at malawakang ginagamit sa buong quantum computing. Ang Hadamard gate ay lumilikha ng mga superposition state. Partikular, ito ay tinukoy ng

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

Ang operasyon nito sa anumang ibang estado ay tinukoy sa pamamagitan ng linearity. Partikular na, ang isang layer ng mga Hadamard gate ay nagbibigay-daan sa atin na lumipat mula sa paunang estado na ang lahat ng qubit ay nasa $|0\rangle$ (tinutukoy na $|0\rangle^{\otimes n}$) patungo sa isang estado kung saan ang bawat qubit ay may ilang posibilidad na masukat sa alinman sa $|0\rangle$ o $|1\rangle;$ pinapayagan nito tayong sondahin ang espasyo ng lahat ng posibleng estado nang naiiba kaysa sa klasikal na computing.

Isang mahalagang corollary na katangian ng Hadamard gate ay ang pag-aplay ng pangalawang beses ay maaaring i-undo ang mga ganitong superposition state:

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

Mahalaga ito sa susunod na sandali.

Suriin ang iyong pag-unawa

Basahin ang tanong sa ibaba, isipin ang iyong sagot, pagkatapos ay i-click ang tatsulok para makita ang solusyon.

Simula sa kahulugan ng Hadamard gate, ipakita na ang pangalawang aplikasyon ng Hadamard gate ay nag-u-undo ng mga ganitong superposition gaya ng sinasabi sa itaas.

Sagot:

Kapag inilapat natin ang X sa estado na $|+\rangle$, makukuha natin ang halaga na +1 at sa estado na $|-\rangle$ makakakuha tayo ng -1, kaya kung mayroon tayong 50-50 na distribusyon, makakakuha tayo ng inaasahang halaga na 0.

Ang $Z_\text{OR}$ gate ay hindi gaanong karaniwan, at tinukoy ayon sa

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{if } x = 0^n \\ -|x\rangle & \text{if } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

Panghuli, ang $Z_f$ gate ay tinukoy ng

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

Pansinin na ang epekto nito ay binabaligtad ng $Z_f$ ang tanda ng isang target na estado kung saan ang $f(x) = 1$ at iniiwan ang iba pang mga estado nang hindi nababago.

Sa isang napaka-mataas at abstract na antas, maaari mong isipin ang mga hakbang sa circuit sa mga sumusunod na paraan:

• Unang Hadamard layer: inilalagay ang mga qubit sa isang superposition ng lahat ng posibleng estado.
• $Z_f$: minmamarka ang target na estado/s sa pamamagitan ng pagdaragdag ng "-" na tanda sa harap. Hindi agad nito binabago ang mga posibilidad ng pagsukat, ngunit binabago nito kung paano kikilos ang target na estado sa mga kasunod na hakbang.
• Isa pang Hadamard layer: Ang "-" na tanda na ipinakilala sa nakaraang hakbang ay magbabago ng kamag-anak na tanda sa pagitan ng ilang mga term. Dahil ang mga Hadamard gate ay nagpapalit ng isang pinagsamang computational state $(|0\rangle+|1\rangle)/\sqrt{2}$ sa isang computational state, $|0\rangle,$ at nagpapalit ng $(|0\rangle-|1\rangle)/\sqrt{2}$ sa $|1\rangle$, ang pagkakaibang ito ng kamag-anak na tanda ay maaari na ngayong maglaro ng papel sa kung anong mga estado ang nasusukat.
• Isang huling layer ng mga Hadamard gate ang inilalapat, at pagkatapos ay ginagawa ang mga pagsukat. Makikita natin nang mas detalyado kung paano ito gumagana sa susunod na seksyon.

Halimbawa

Para mas maunawaan kung paano gumagana ang algoritmo ni Grover, halina't magtrabaho tayo sa isang maliit na dalawang-qubit na halimbawa. Maaaring ituring itong opsyonal para sa mga hindi nakatuon sa quantum mechanics at Dirac notation. Ngunit para sa mga umaasang magtrabaho nang malaki sa mga quantum computer, lubos itong inirerekomenda.

Narito ang circuit diagram na may mga quantum state na nalagyan ng label sa iba't ibang posisyon sa buong proseso. Pansinin na sa dalawang qubit lamang, mayroon lamang apat na posibleng estado na maaaring masukat sa anumang kalagayan: $|00\rangle$, $|01\rangle$, $|10\rangle$, at $|11\rangle$.

Ipagpalagay nating ang oracle ($Z_f$, hindi alam sa atin) ay nagmamarka ng estado na $|01\rangle$. Tatrabahuin natin ang mga aksyon ng bawat hanay ng mga quantum gate, kasama ang oracle, at makikita kung anong distribusyon ng mga posibleng estado ang lumalabas sa oras ng pagsukat. Sa pinakasimula, mayroon tayong

$$|\psi_0\rangle = |00\rangle$$

Gamit ang kahulugan ng mga Hadamard gate, mayroon tayong

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

Ngayon ang oracle ay nagmamarka ng target na estado:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

Pansinin na sa estadong ito, lahat ng apat na posibleng kinalabasan ay may parehong posibilidad na masukat. Lahat sila ay may bigat na may magnitude na $1/2,$ ibig sabihin bawat isa ay may $|1/2|^2=1/4$ na tsansa na masukat. Kaya habang ang estado na $|01\rangle$ ay namarkahan sa pamamagitan ng "-" na phase, hindi pa ito nagresulta sa anumang pagtaas ng posibilidad ng pagsukat sa estadong iyon. Nagpapatuloy tayo sa pag-aplay ng susunod na layer ng mga Hadamard gate.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Sa pagsasama ng magkaparehong term, makikita natin

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

Ngayon ang $Z_{\text{OR}}$ ay nagbabalik-tanda sa lahat ng estado maliban sa $|00\rangle$:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

At panghuli, inilalapat natin ang huling layer ng mga Hadamard gate:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

Sulit na trabahuin ang pagsasama ng mga term na ito para kumbinsihin ang iyong sarili na ang resulta ay talagang:

$$|\psi_5\rangle =|01\rangle$$

Iyon ay, ang posibilidad ng pagsukat sa $|01\rangle$ ay 100% (sa kawalan ng ingay at mga error) at ang posibilidad ng pagsukat sa anumang ibang estado ay zero.

Ang dalawang-qubit na halimbawang ito ay isang espesyal na malinis na kaso; ang algoritmo ni Grover ay hindi laging magreresulta sa 100% na tsansa ng pagsukat sa target na estado. Sa halip, pinalalakas nito ang posibilidad ng pagsukat sa target na estado. Gayundin, maaaring kailanganin na ulitin ang Grover operator nang higit sa isang beses.

Sa susunod na seksyon, ilalagay natin ang algorithm na ito sa praktis gamit ang tunay na mga IBM® quantum computer.

Ang geometric na larawan

Ang dalawang-qubit na halimbawa sa itaas ay nagpapakita kung paano gumagana ang algebra para sa isang maliit na kaso, ngunit may mas intuitive na paraan para maunawaan ang algoritmo ni Grover: bilang isang serye ng geometric reflections sa isang dalawang-dimensional na eroplano. Sa ibaba inilalarawan natin ang larawang ito. Maaari mo ring tingnan ang kurso ni John Watrous na Fundamentals of Quantum Algorithms para sa mas maraming detalye.

Pag-set up ng eroplano. Maaari nating hatiin ang paunang superposition state na $|\psi\rangle$ sa dalawang bahagi. Ang tamang estado — ang hinahanap natin — ay tinatawag nating $|A_1\rangle$. Ang bawat ibang estado, pinagsama, ay tinatawag nating $|A_0\rangle$. Sa kahulugan, ang $|A_1\rangle$ at $|A_0\rangle$ ay ortogonal sa isa't isa, kaya maaari nating i-plot sila bilang mga perpendikular na aksis sa isang abstract, dalawang-dimensional na espasyo. Dahil ang $|\psi\rangle$ ay isang linear na kombinasyon ng dalawang bahaging ito, ito ay nasa isang maliit na anggulo $\theta$ sa $|A_0\rangle$ na aksis — malapit sa $|A_0\rangle$, dahil sa simula, isang napakaliit na bahagi lamang ng estado ang nasa tamang bahagi na $|A_1\rangle$.

Mga reflection. Ang pangunahing mathematical na katotohanan na kailangan natin ay ang isang operator ng form na

$$2|v\rangle\langle v| - I$$

ay nagre-reflect ng anumang estado tungkol sa aksis na tinukoy ng $|v\rangle.$ Para makita kung bakit, isaalang-alang ang dalawang kaso: ang isang estado kasabay ng $|v\rangle$ ay hindi nagbabago, at ang isang estado na perpendikular sa $|v\rangle$ ay nababago ang tanda nito. Ang anumang ibang estado ay maaaring hatiin sa dalawang bahaging ito, at ang operator ay kumikilos sa bawat isa nang naaayon — na eksaktong isang reflection tungkol sa $|v\rangle$.

Lumalabas na ang oracle at ang diffusion step sa algoritmo ni Grover ay maaaring ipahayag bilang mga reflection sa geometric na larawang ito.

Ang oracle bilang reflection. Ang oracle ay nagba-flip ng tanda ng $|A_1\rangle$ na estado at iniiwan ang lahat ng iba pa. Iyan ay katulad ng isang reflection tungkol sa $|A_0\rangle$ na aksis.

Ang diffusion bilang reflection. Medyo mas mahirap makita kung paano ang diffusion operator ay isang reflection din. Ang diffusion operator ay

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

Ang $Z_{\text{OR}}$ nang mag-isa ay isang reflection tungkol sa all-zero state, dahil nagba-flip ito ng tanda ng bawat estado na hindi $|0\rangle^{\otimes n}$. Maaaring isulat ito bilang $2|0\rangle\langle 0| - I$. Ang mga nakapalibot na Hadamard layer ay epektibong nagsasagawa ng pagbabago ng basis, binabago ang aksis ng reflection. Alalahanin na ang $H^{\otimes n}$ ay nagma-map ng $|0\rangle^{\otimes n}$ sa uniform superposition na $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Dahil ang Hadamard ay sarili nitong inverse, ang buong ekspresyon ay nagiging

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

na isang reflection tungkol sa $|u\rangle$. Dahil ang $|u\rangle$ ay napakalapit sa $|\psi\rangle$ (parehong halos kasabay ng $|A_0\rangle$), ang ikalawang reflection na ito ay nagpapadala ng estado sa anggulo na $2\theta$ mula sa kinatatayuan nito.

Rotation na $2\theta$. Ang pinagsama-samang epekto ng dalawang reflection na ito ay isang rotation ng $2\theta$ patungo sa $|A_1\rangle$. Ang bawat sunud-sunod na pag-uulit ng Grover operator ay nag-i-rotate ng estado ng isa pang $2\theta.$

Pinakamainam na bilang ng pag-uulit. Ang aming layunin ay i-rotate ang estado nang kasing lapit sa $|A_1\rangle$ hangga't maaari, na nangangahulugang mag-rotate ng kabuuang halos $\pi/2$ radians (isang quarter turn). Kung ang bawat pag-uulit ay nag-aambag ng $2\theta$, ang pinakamainam na bilang ng pag-uulit $t$ ay nagtatugon sa

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

Para sa isang solusyon sa gitna ng $N$ na estado, ang paunang anggulo ay $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (para sa malaking $N$). Sa pamamagitan ng pag-substitute,

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

Dito nanggagaling ang sikat na $\sqrt{N}$ speedup: kailangan lang natin ng $O(\sqrt{N})$ na pag-uulit para maabot ang target, sa halip na ang $O(N)$ na mga tsek na kakailanganin ng klasikal na paghahanap.

Sa pangkalahatang kaso, kung mayroon $|A_1|$ na mga solusyon sa gitna ng $N$ na kabuuang estado, ang pinakamainam na bilang ng pag-uulit ay

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

Tandaan na kung mag-a-apply ka ng masyadong maraming pag-uulit, iro-rotate mo ang estado nang lampas sa $|A_1\rangle$ at ang posibilidad ng paghanap ng iyong target na estado ay magsisimulang bumaba ulit. Mahalaga ang paghanap ng tamang bilang ng pag-uulit, kahit sa maingay na quantum hardware ang eksperimentong pinakamainam na bilang ay maaaring mag-iba sa ideal na formula na ito.

Bakit kapaki-pakinabang ang algoritmo ni Grover?

Sa puntong ito maaari kang magtaka: kaka-build lang natin ng isang oracle na nagmamarka ng target na estado — ngunit para mabuo ito, kailangan nating malaman ang target na estado. Kaya ano talaga ang hinahanap natin?

Ito ay isang makatwirang tanong, at may ilang magagandang sagot.

• Ang query model ay isang theoretical na kasangkapan. Ang query model ng computation ay hindi dinisenyo para maging direktang praktikal. Ang layunin nito ay magbigay sa atin ng malinis na paraan para suriin ang algorithmic complexity sa pamamagitan ng paghihiwalay ng isang problema sa dalawang bahagi: ang oracle, at lahat ng iba pa. Gaano kahirap ang paghahanap, kung libre ang verification? Paano lumalaki ang bilang ng mga query sa laki ng input? Ang mga ito ay kapaki-pakinabang na mga tanong kahit walang tunay na sistema na gumagana nang eksakto sa ganitong paraan.

• Maaari mo rin itong isipin bilang isang dalawang-partido na aktibidad: isang tao ang nakaalam ng target na estado at nagtatayo ng oracle; ang trabaho ng isa pang tao ay hanapin ang sagot gamit ang oracle bilang isang black box, nang hindi sumisilip sa loob. Sa Aktibidad 2 sa ibaba, gagawin mo nang eksakto ito kasama ang isang kasosyo.

• Ang amplitude amplification ay isang malawak na kapaki-pakinabang na subroutine. Kahit tila paikot ang unang demonstrasyong ito, ang pinagbabatayang mekanismo — na tinatawag na amplitude amplification — ay paulit-ulit na lumalabas sa quantum computing. Ang tunay na binubuo natin dito ay intuwisyon para sa isang kasangkapan na lumalabas bilang subroutine sa marami pang mas kumplikadong quantum algorithm.

• Mayroon mga problema kung saan maaari kang bumuo ng oracle nang hindi alam ang sagot. Ang pangunahing kaalaman ay may isang buong klase ng mga problema kung saan napakahirap hanapin ang isang solusyon, ngunit napakadali suriin na ang isang ibinigay na solusyon ay tama. Ang factoring ay isang halimbawa: kapag may produkto ng dalawang malalaking primo, napakahirap matukoy kung ano ang mga primo na iyon, ngunit kapag nakuha mo na sila, madali mong mami-multiply sila upang ma-verify. (Mayroon kaming mas magandang algorithm kaysa Grover's para sa factoring nang partikular — tingnan ang Shor's algorithm — ngunit ito ay malayo sa nag-iisang problema na may katangiang ito.) Ang Sudoku, constraint satisfaction, at kahit ang klasikong laro ng Minesweeper ay lahat ng mga problema na mahirap lutasin ngunit madaling suriin.

Bakit ito may kaugnayan? Nangangahulugan ito na maaari nating malaman ang lahat ng kondisyon at kinakailangan na dapat matugunan ng isang solusyon, at maaari nating i-encode ang mga kinakailangan na iyon sa isang quantum circuit na nagsisilbing oracle — kahit hindi natin alam ang solusyon mismo. Hahanapin ito ng algoritmo ni Grover para sa atin.

Sa mga ideyang ito sa isip, halina't magtrabaho tayo sa ilang mga halimbawa. Magsisimula tayo sa isang halimbawa kung saan ang solution state ay malinaw na tinukoy upang masundan natin ang lohika ng algorithm. Pagkatapos ay lilipat tayo sa isang dalawang-partido na aktibidad, at sa wakas sa isang halimbawa kung saan ang oracle ay binuo mula sa mga constraint ng problema kaysa mula sa kaalaman ng sagot.

Mga Pangkalahatang Import at Diskarte

Magsisimula tayo sa pag-import ng ilang kinakailangang package.

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

Sa buong tutorial na ito at iba pang mga tutorial, gagamit tayo ng isang balangkas para sa quantum computing na kilala bilang "Qiskit patterns", na hinahati ang mga workflow sa mga sumusunod na hakbang:

• Hakbang 1: I-map ang mga klasikal na input sa isang quantum na problema
• Hakbang 2: I-optimize ang problema para sa quantum execution
• Hakbang 3: Isagawa gamit ang Qiskit Runtime Primitives
• Hakbang 4: Post-processing at klasikal na pagsusuri

Karaniwang susundin natin ang mga hakbang na ito, kahit hindi natin palaging tahasang lalagyan ng label ang mga ito.

Aktibidad 1: Hanapin ang isang partikular na target na estado

Hakbang 1: I-map ang mga klasikal na input sa isang quantum na problema

Kailangan ng phase query gate na maglagay ng pangkalahatang phase (-1) sa mga solusyong estado, at huwag baguhin ang mga hindi solusyon. Sa madaling salita, ang Grover's algorithm ay nangangailangan ng isang oracle na nagtatakda ng isa o higit pang markadong computational basis na estado, kung saan ang "markado" ay nangangahulugang ang estado ay may phase na -1. Ginagawa ito gamit ang isang controlled-Z gate, o ang multi-controlled na generalization nito sa $N$ na qubit. Upang makita kung paano ito gumagana, isaalang-alang ang isang partikular na halimbawa ng bitstring na {110}. Gusto namin ng isang circuit na kumikilos sa estado na $|\psi\rangle = |q_2,q_1,q_0\rangle$ at nag-aaplay ng phase kung $|\psi\rangle = |011\rangle$ (kung saan pinbaliktad namin ang pagkakasunod-sunod ng binary string, dahil sa notasyon sa Qiskit, na naglalagay ng pinaka-hindi makabuluhang (least significant, kadalasang 0) qubit sa kanan).

Kaya, gusto namin ng circuit na $Z_f$ na nagagawa ang sumusunod:

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{if} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{if} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

Maaari naming gamitin ang multiple control multiple target gate (MCMTGate) upang mag-apply ng Z gate na kinokontrol ng lahat ng qubit (i-flip ang phase kung ang lahat ng qubit ay nasa estado na $|1\rangle$). Siyempre, ang ilang qubit sa aming nais na estado ay maaaring $|0\rangle$. Kaya, para sa mga qubit na iyon, kailangan muna naming mag-apply ng X gate, pagkatapos ay gawin ang multiply-controlled Z gate, at pagkatapos ay mag-apply ng isa pang X gate upang i-undo ang aming pagbabago. Ganito ang hitsura ng MCMTGate:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

Pansinin na maraming qubit ang maaaring kasangkot sa proseso ng kontrol (dito ay tatlong qubit ang kasangkot), ngunit walang iisang qubit na itinakda bilang target. Ito ay dahil ang buong estado ay nakakakuha ng pangkalahatang "-" na tanda (phase flip); ang gate ay pantay na naka-apekto sa lahat ng qubit. Ito ay naiiba sa maraming ibang multiple qubit gate, tulad ng CX gate, na may isang control qubit at isang target qubit.

Sa sumusunod na code, nagtatakda kami ng isang phase query gate (o oracle) na gumagawa ng inilarawan namin sa itaas: nagmamarka ng isa o higit pang input na basis na estado na tinukoy sa pamamagitan ng kanilang bitstring na representasyon. Ang MCMT gate ay ginagamit upang ipatupad ang multi-controlled Z-gate.

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

Ngayon pipili tayo ng isang partikular na "markadong" estado bilang ating target, at ia-apply ang function na aming tinukoy. Tingnan natin kung anong uri ng circuit ang nagawa nito.

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Kung ang mga qubit 1-3 ay nasa estado na $|1\rangle$, at ang qubit 0 ay una sa estado na $|0\rangle$, ang unang X gate ay mag-fi-flip ng qubit 0 sa $|1\rangle$ at lahat ng qubit ay mapupunta sa $|1\rangle.$ Ibig sabihin nito, ang MCMT gate ay mag-a-apply ng pangkalahatang pagbabago ng tanda o phase flip, gaya ng nais. Para sa anumang ibang kaso, alinman sa mga qubit 1-3 ay nasa $|0\rangle$ na estado, o ang qubit 0 ay nai-flip sa $|0\rangle$ na estado, at ang phase flip ay hindi ia-apply. Makikita natin na ang circuit na ito ay tunay na nagmamarka ng ating ninanais na estado na $|0111\rangle,$ o ang bitstring na {1110}.

Ang buong Grover operator ay binubuo ng phase query gate (oracle), Hadamard layers, at ang $Z_\text{OR}$ operator. Maaari nating gamitin ang built-in na grover_operator upang itayo ito mula sa oracle na aming tinukoy sa itaas.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Gaya ng aming tinalakay sa geometric na larawan sa itaas, maaaring kailangan naming i-apply ang Grover operator nang maraming beses. Ang pinakamainam na bilang ng pag-uulit $t$ upang ma-maximize ang amplitude ng target na estado nang wala sa noise ay

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

kung saan ang $|A_1|$ ay ang bilang ng mga estado ng solusyon at ang $N=2^n$ ay ang kabuuang bilang ng mga estado. Sa mga modernong maingay na quantum na computer, ang eksperimentong pinakamainam na bilang ng pag-uulit ay maaaring magkaiba — ngunit dito kinakalkula at ginagamit natin ang teoretikal na pinakamainam na bilang gamit ang $|A_1|=1$.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

Buuin natin ngayon ang isang circuit na kinabibilangan ng mga paunang Hadamard gate upang lumikha ng superposisyon ng lahat ng posibleng estado, at i-apply ang Grover operator ng pinakamainam na bilang ng beses.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Nabuo na natin ang ating Grover circuit!

Hakbang 2: I-optimize ang problema para sa pagpapatakbo sa quantum hardware

Natukoy na natin ang ating abstract na quantum circuit, ngunit kailangan naming isulat ito ulit sa mga gate na katutubong sa quantum na computer na talagang nais naming gamitin. Kailangan din naming tukuyin kung aling mga qubit sa quantum na computer ang dapat gamitin. Dahil sa mga dahilang ito at iba pa, kailangan nating i-transpile ang ating circuit. Una, tukuyin natin ang quantum na computer na nais nating gamitin.

May code sa ibaba para sa pag-save ng iyong mga kredensyal sa unang paggamit. Siguraduhing burahin ang impormasyong ito mula sa notebook pagkatapos i-save ito sa iyong environment, upang ang iyong mga kredensyal ay hindi aksidenteng maibahagi kapag ibinabahagi mo ang notebook. Tingnan ang Set up your IBM Cloud account at Initialize the service in an untrusted environment para sa karagdagang gabay.

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.

# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',
# instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

Ngayon gagamit tayo ng preset pass manager upang i-optimize ang ating quantum circuit para sa Backend na aming pinili.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Kapansin-pansing ang lalim ng transpiled na quantum circuit ay malaki.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

Medyo malaki ang mga numerong ito, kahit para sa simpleng kasong ito. Dahil lahat ng quantum gate (at lalo na ang mga two-qubit gate) ay may kasamang mga error at napapailalim sa noise, ang isang serye ng mahigit 100 two-qubit gate ay magreresulta lamang sa ingay kung ang mga qubit ay hindi napakataas ang pagganap. Tingnan natin kung paano ang pagganap ng mga ito.

Hakbang 3: I-execute gamit ang Qiskit primitives

Gusto naming gumawa ng maraming sukat at makita kung aling estado ang pinakamalamang. Ang ganitong amplitude amplification ay isang sampling na problema na angkop para sa pagpapatakbo gamit ang Sampler Qiskit Runtime primitive.

Pansinin na ang run() method ng Qiskit Runtime SamplerV2 ay tumatanggap ng isang iterable ng primitive unified blocks (PUBs). Para sa Sampler, ang bawat PUB ay isang iterable sa format na (circuit, parameter_values). Gayunpaman, sa pinakamababa, ito ay tumatanggap ng isang listahan ng quantum circuit(s).

# To run on a real quantum computer (this was tested on a Heron r2 processor and
# used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Upang mapakinabangan nang husto ang karanasang ito, lubos naming inirerekomenda na patakbuhin mo ang iyong mga eksperimento sa mga tunay na quantum na computer na available mula sa IBM Quantum. Gayunpaman, kung naubusan ka na ng iyong QPU time, maaari mong i-uncomment ang mga linya sa ibaba upang makumpleto ang aktibidad na ito gamit ang isang simulator.

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Hakbang 4: I-post-process at ibalik ang resulta sa nais na klasikal na format

Ngayon maaari na nating i-plot ang mga resulta ng ating sampling sa isang histogram.

plot_distribution(dist)

Makikita natin na ang Grover's algorithm ay nagbalik ng nais na estado na may pinakamataas na posibilidad nang malayo, kahit isang order of magnitude na mas mataas kaysa sa iba pang mga opsyon. Sa susunod na aktibidad, gagamitin natin ang algorithm sa paraang mas naaayon sa dalawang-partido na workflow ng isang query algorithm.

Suriin ang iyong pag-unawa

Basahin ang mga tanong sa ibaba, isipin ang iyong sagot, pagkatapos ay i-click ang tatsulok upang ipakita ang solusyon.

Naghanap lang tayo ng isang solusyon sa isang set ng $2^4=16$ na posibleng estado. Natukoy namin na ang pinakamainam na bilang ng pag-uulit ng Grover operator ay $t=3$. Tataas o bababa ba ang pinakamainam na bilang na ito kung naghanap tayo ng (a) alinman sa maraming solusyon, o (b) isang solusyon sa isang espasyo ng higit pang posibleng estado?

Sagot:

Alalahanin na hangga't ang bilang ng mga solusyon ay maliit kumpara sa buong espasyo ng mga solusyon, maaari nating i-expand ang sine function sa maliit na mga anggulo at gamitin ang:

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(a) Makikita natin mula sa ekspresyon sa itaas na ang pagdaragdag ng bilang ng mga estado ng solusyon ay magbabawas ng bilang ng pag-uulit. Sa kondisyon na ang fraction na $\frac{|\mathcal{A}_1|}{N}$ ay maliit pa rin, maaari nating ilarawan kung paano bababa ang $t$: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) Habang tumataas ang espasyo ng mga posibleng solusyon ($N$), tumataas din ang bilang ng mga kinakailangang pag-uulit, ngunit katulad lang ng $t~\sqrt{N}$.

Ipagpalagay na maaari tayong dagdagan ang laki ng target na bitstring nang walang hanggan at mayroon pa ring resulta na ang target na estado ay may probability amplitude na kahit isang order of magnitude na mas malaki kaysa sa anumang ibang estado. Ibig sabihin ba nito na maaari nating gamitin ang Grover's algorithm upang maaasahang mahanap ang target na estado?

Sagot:

Hindi. Ipagpalagay na inulit natin ang unang aktibidad na may 20 qubit, at pinatakbo natin ang quantum circuit nang ilang beses na num_shots = 10,000. Ang pantay na distribusyon ng posibilidad ay nangangahulugang ang bawat estado ay may posibilidad na $10,000/2^{20}=0.00954$ na masukat kahit isang beses. Kung ang posibilidad ng pagsusukat ng target na estado ay 10 beses na higit sa mga hindi solusyon (at ang posibilidad ng bawat hindi solusyon ay bahagyang bumaba nang naaayon), mayroon lamang mga 10% na pagkakataon na masukat ang target na estado kahit isang beses. Magiging napakahirap na masukat ang target na estado nang maraming beses, na magpapahirap na makilala ito mula sa maraming randomly na nakuhang estado na hindi solusyon. Ang magandang balita ay makakakuha tayo ng mas mataas na katumpakan ng mga resulta sa pamamagitan ng paggamit ng error suppression at mitigation.

Aktibidad 2: Isang tumpak na query algorithm na workflow

Sisimulan natin ang aktibidad na ito nang eksakto gaya ng una, maliban na ngayon ay magkasamang makikipagtulungan ka sa isa pang Qiskit enthusiast. Pipili ka ng isang lihim na bitstring, at pipili ang iyong kasosyo ng (sa pangkalahatan) ibang bitstring. Bawat isa sa inyo ay magge-generate ng quantum circuit na gumaganap bilang oracle, at ipagpapalit ninyo ang mga ito. Pagkatapos ay gagamit ka ng Grover's algorithm gamit ang oracle na iyon upang matukoy ang lihim na bitstring ng iyong kasosyo.

Hakbang 1: I-map ang mga klasikal na input sa isang quantum na problema

Gamit ang grover_oracle function na tinukoy sa itaas, bumuo ng isang oracle circuit para sa isa o higit pang markadong estado. Siguraduhing ipaalam mo sa iyong kasosyo kung gaano karaming estado ang iyong minarkahan, upang makapag-apply sila ng Grover operator ng pinakamainam na bilang ng beses. Huwag gawing masyadong mahaba ang iyong bitstring. Ang 3-5 bits ay dapat gumana nang walang kahirapan. Ang mas mahabang bitstring ay magreresulta sa mas malalim na circuit na nangangailangan ng mas advanced na mga teknik tulad ng error mitigation.

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

Ngayon ay lumikha ka ng isang quantum circuit na nagba-flip ng phase ng iyong target na estado. Maaari mong i-save ang circuit na ito bilang my_circuit.qpy gamit ang syntax sa ibaba.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

Ngayon ipadala ang file na ito sa iyong kasosyo (sa pamamagitan ng email, messaging service, shared repo, at iba pa). Ipapadala rin ng iyong kasosyo ang kanilang circuit sa iyo. Siguraduhing i-save ang file sa isang lugar na madali mong mahanap. Kapag natanggap mo na ang circuit ng iyong kasosyo, maaari mo itong i-visualize — ngunit iyon ay lalabag sa query model. Ibig sabihin, nagmo-modelo tayo ng sitwasyon kung saan maaari mong i-query ang oracle (gamitin ang oracle circuit) ngunit hindi ito suriin upang matukoy kung anong estado ang nita-target nito.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

Tanungin ang iyong kasosyo kung gaano karaming target na estado ang kanilang na-encode at ilagay ito sa ibaba.

# Update according to your partner's number of target states.
num_marked_states = 1

Ginagamit ito sa susunod na ekspresyon upang matukoy ang pinakamainam na bilang ng Grover iterations.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

Hakbang 2: I-optimize ang problema para sa pagpapatakbo sa quantum hardware

Ito ay eksaktong tulad ng dati.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

Hakbang 3: I-execute gamit ang Qiskit primitives

Ito ay kapareho rin ng proseso sa unang aktibidad.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used
# 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

Hakbang 4: I-post-process at ibalik ang resulta sa nais na klasikal na format

Ngayon ipakita ang isang histogram ng iyong mga resulta sa sampling. Ang isa o higit pang estado ay dapat na may mas mataas na posibilidad ng pagsusukat kaysa sa iba. I-ulat ang mga ito sa iyong kasosyo at suriin kung tama ang iyong natukoy na mga target na estado. Bilang default, ang histogram na ipinapakita ay mula sa parehong circuit ng unang aktibidad. Dapat kang makakuha ng iba't ibang resulta mula sa circuit ng iyong kasosyo.

plot_distribution(dist)

Suriin ang iyong pag-unawa

Basahin ang mga tanong o prompt sa ibaba, isipin ang iyong sagot o pag-usapan ang proseso kasama ang iyong kasosyo. I-click ang tatsulok para sa mga pahiwatig o mungkahi.

Dapat nang tama mong natukoy ang mga target na estado ng iyong kasosyo. Kung hindi, makipagtulungan sa iyong kasosyo upang matukoy kung ano ang nagkamali. I-click sa ibaba para sa ilang ideya.

Mga Pahiwatig:

• I-visualize/iguhit ang circuit ng iyong kasosyo at tiyaking na-load ito nang tama.
• Ikumpara ang mga circuit na ginamit at ikumpara ang inaasahang resulta sa nakuha mo.
• Suriin ang lalim ng mga circuit na ginamit upang matiyak na ang bitstring ay hindi masyadong mahaba o ang bilang ng Grover iterations ay hindi masyadong mataas.

Kung hindi mo pa nagagawa, iguhit ang oracle circuit na ipinadala ng iyong kasosyo sa iyo. Tingnan kung kaya mong pag-aralan ang epekto ng bawat gate at ipaliwanag kung ano ang dapat na target na estado. Ito ay magiging mas madali para sa kaso ng isang markadong estado kaysa sa marami.

Mga Pahiwatig:

• Alalahanin na ang trabaho ng oracle ay i-flip ang tanda ng target na estado.
• Alalahanin na ang MCMTGate ay nagba-flip ng tanda sa isang estado kung at tanging kung lahat ng qubit na kasangkot sa kontrol ay nasa estado na $|1\rangle$.
• Kung ang iyong target na estado ay magkakaroon ng $|1\rangle$ sa isang partikular na qubit, hindi mo na kailangang gawin ang anuman sa qubit na iyon. Kung ang iyong target ay may $|0\rangle$ sa isang partikular na qubit at gusto mong i-flip ng MCMTGate ang tanda, kailangan mong mag-apply ng X gate sa qubit na iyon sa iyong oracle (at pagkatapos ay i-undo ang X gate pagkatapos ng MCMTGate).

Ulitin ang eksperimento na may isang beses na mas kaunting pag-uulit ng Grover operator. Makukuha mo pa ba ang tamang sagot? Bakit o bakit hindi?

Gabay:

Malamang na oo, bagaman ito ay maaaring depende sa bilang ng mga na-encode na solusyon. Itinatampok nito ang isang subtlety: ang "pinakamainam" na bilang ng Grover iterations ay ang bilang na nagpapataas ng posibilidad ng pagsusukat ng markadong estado nang pinakamaataas. Ngunit ang mas kaunting pag-uulit kaysa roon ay maaari pa ring gawing mas malamang ang markadong estado kaysa sa iba pang mga estado. Kaya, maaari kang makarating sa mas kaunting pag-uulit kaysa sa pinakamainam na bilang. Binabawasan nito ang lalim ng circuit, at sa gayon ay binabawasan ang mga rate ng error.

Bakit gugustuhin ng isang tao na gumamit ng mas kaunting Grover iterations kaysa sa "pinakamainam na bilang" na natukoy dito?

Sagot:

Ang "pinakamainam" na bilang ng Grover iterations ay ang bilang na nagpapataas ng posibilidad ng pagsusukat ng markadong estado nang pinakamaataas nang wala sa noise. Ngunit ang mas kaunting pag-uulit kaysa roon ay maaari pa ring gawing mas malamang ang markadong estado kaysa sa iba pang mga estado. Kaya, maaari kang makarating sa mas kaunting pag-uulit kaysa sa pinakamainam na bilang. Binabawasan nito ang lalim ng circuit, at sa gayon ay binabawasan ang mga rate ng error.

Aktibidad 3: Lutasin ang isang Minesweeper grid gamit ang Grover's algorithm

Sa nakaraang seksyon, napansin natin na ang Grover's algorithm ay tunay na nagiging kapaki-pakinabang kapag maaari tayong bumuo ng oracle mula sa mga constraint ng isang problema, sa halip na mula sa kaalaman ng sagot. Ang Minesweeper ay isang perpektong halimbawa: ang mga numeradong cell ay nagsasabi sa atin kung ilang mina ang katabing, at ang mga constraint na iyon ay ganap na nagtatakda kung nasaan dapat ang mga mina — ngunit ang paghanap ng configuration ay nangangailangan ng paghahanap.

Napatunayan na ang Minesweeper ay NP-complete: mahirap lutasin ngunit madaling suriin. Ginagawa itong natural na kandidato para sa Grover's algorithm. Siyempre, hindi pa tayo makakalutas ng buong 9$\times$9 grid sa isang maingay na quantum computer — ang mga circuit ay magiging masyadong malalim. Sa halip, gagamit tayo ng napakaliit na grid bilang isang laruan na demonstrasyon kung paano lalalapitin ang isang mas malaking board sa isang hinaharap na fault-tolerant na makina.

Ilang mahahalagang caveat. Ang Grover's algorithm ay nagbibigay lamang ng quadratic speedup kumpara sa unstructured na klasikal na paghahanap. Ang Minesweeper ay halos tiyak na may magagamit na istraktura na maaaring gamitin ng isang matalinong klasikal na algorithm. At para sa exponentially lumalagong espasyo ng paghahanap, kahit ang $\sqrt{N}$ na pagpapabuti ay may limitasyon. Ngunit itabi natin muna ang mga alalahanin na iyon at gamitin ang laruang problemang ito para ilarawan kung paano ang mga constraint ng problema ay na-encode sa isang quantum oracle.

Ang grid

Narito ang ating baby minesweeper grid:

Ang bawat blangkong cell ay maaaring katawanin ng isang binary na variable na nagpapahiwatig kung naglalaman ito ng isang mina. Lalagyan natin ito ng label na $x_0$, $x_1$, at $x_2$, kung saan ang $x_i = 1$ ay nangangahulugang may mina sa cell na iyon at ang $x_i = 0$ ay nangangahulugang wala:

Maaari nating lutasin ito sa ating isipan sa halos kalahating segundo, ngunit ginagamit natin ang laruang problemang ito para ilarawan kung paano malalapitan ang isang mas mahirap na board gamit ang isang quantum computer.

I-encode ang mga constraint

Ang bawat numeradong cell ay naglalagay ng kondisyon sa mga katabing blangkong cell. Kailangan nating ipahayag ang mga kondisyon na ito bilang mga Boolean na ekspresyon na maaaring i-encode sa isang quantum circuit.

Ang cell na "1" na katabi ng $x_0$ at $x_1$ ay nagsasabi na eksaktong isa sa kanila ang naglalaman ng mina. Ito ay eksakto ang exclusive-OR (XOR) na operasyon, $\oplus$, na nagbabalik ng true kapag eksaktong isa sa mga input nito ay true:

$$(x_0 \oplus x_1)$$

Katulad nito, ang isa pang cell na "1" (katabi ng $x_1$ at $x_2$) ay nagbibigay sa atin ng:

$$(x_1 \oplus x_2)$$

Ang cell na "2" ay nagsasabi na dalawa sa tatlong blangkong cell ang dapat maglaman ng mga mina. Dahil ang XOR ay isang parity na operasyon, ang $x_0 \oplus x_1 \oplus x_2$ ay nagbabalik ng true kapag gansal na bilang ng mga variable ay true. Gusto namin ng pares na bilang (partikular na dalawa) na maging true, kaya itinatanggi namin gamit ang $\lnot$:

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

Nang mag-isa, ang ekspresyong ito ay matutugunan ng alinman sa zero o dalawang qubit sa $|1\rangle$ na estado, dahil ito ay isang pahayag tungkol sa parity. Ngunit kasama ang iba pang dalawang clause, na bawat isa ay nangangailangan ng hindi bababa sa isang mina, ang tanging nakakatugon na assignment ay may eksaktong dalawang mina.

Ang tatlong kondisyon ay dapat matugunan nang sabay-sabay, kaya pinagsama namin sila gamit ang mga simbolo ng and $\land$:

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

Hakbang 1: I-map ang mga klasikal na input sa isang quantum na problema

Ngayon kailangan nating i-encode ang Boolean na ekspresyong ito sa isang quantum circuit na nagsisilbing oracle. Ang quantum na bersyon ng XOR ay maaaring gawin gamit ang mga CX (CNOT) gate: ang pag-apply ng dalawang CX gate mula sa mga data qubit patungo sa isang workspace (ancilla) qubit ay epektibong nagkukuwenta ng kanilang XOR at nag-iimbak ng resulta sa ancilla.

Nagpapakilala tayo ng tatlong workspace qubit — isa para sa bawat clause. Iniimbak natin ang resulta ng bawat Boolean na ekspresyon sa katumbas na workspace qubit nito, pagkatapos ay gumagamit ng multi-controlled Z gate para i-flip ang phase ng three-qubit state na gumagawa ng lahat ng tatlong workspace qubit na $|1\rangle$ (ibig sabihin ang lahat ng clause ay natutugunan nang sabay-sabay).

Sa unang code cell sa ibaba, binubuo natin ang "compute" na kalahati ng oracle — ang bahaging nagse-evaluate ng bawat clause at nagsusulat ng resulta sa mga workspace qubit.

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

Sa puntong ito, ang resulta ng bawat clause ay nakaimbak sa katumbas na workspace qubit nito. Ngayon kailangan ang three-qubit data state na gumagawa ng lahat ng tatlong workspace qubit na $|1\rangle$ para kumuha ng minus sign. Ginagawa natin ito gamit ang isang multi-controlled Z gate (ipinatupad bilang isang MCX gate na napapalibutan ng mga Hadamard gate sa target).

Pagkatapos i-apply ang phase flip, kailangan nating i-uncompute — i-undo ang lahat ng mga hakbang ng clause-evaluation sa kabaligtarang pagkakasunod-sunod — para i-reset ang mga workspace qubit pabalik sa $|0\rangle.$ Mahalaga ito upang ang mga workspace qubit ay malinis para sa mga kasunod na pag-uulit ng Grover operator.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

Ang circuit na ito ang ating oracle: nagba-flip ito ng phase ng data-qubit state na nakakatugon sa lahat ng tatlong Minesweeper constraint, at iniiwan ang mga workspace qubit pabalik sa $|0\rangle.$

Ngayon bumubuo tayo ng buong Grover operator mula sa oracle na ito. Pansinin ang reflection_qubits argument: nagpapasa lang tayo ng mga data qubit x, dahil ang mga workspace qubit ay hindi bahagi ng espasyo ng paghahanap. Tapos na ang kanilang trabaho kapag nailapat na ang oracle.

grover_op = grover_operator(qc, reflection_qubits=x)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

Sa tatlong data qubit at isang estado ng solusyon, ang pinakamainam na bilang ng Grover iteration ay $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, kaya gumagamit tayo ng dalawang pag-uulit. Nag-a-apply tayo ng mga Hadamard gate sa mga data qubit para lumikha ng paunang superposition, kino-compose ang Grover operator nang dalawang beses, at sinusukat lamang ang mga data qubit.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

Hakbang 2: I-optimize ang problema para sa pagpapatakbo sa quantum hardware

Tulad ng dati, tina-transpile natin ang circuit para sa target backend.

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

Ngayon maaari na nating suriin ang lalim ng transpiled na circuit. Dahil ang Minesweeper oracle ay gumagamit ng mga workspace qubit at maraming CX gate, ang transpiled na circuit ay magiging mas malalim kaysa sa mga mula sa mga nakaraang aktibidad.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

Hakbang 3: I-execute gamit ang Qiskit primitives

# To run on a real quantum computer (this was tested on a Heron r2 processor and
#  used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

Hakbang 4: I-post-process at ibalik ang resulta sa nais na klasikal na format

plot_distribution(dist)

Ang estado na 101 ay dapat lumabas nang may mas mataas na posibilidad kaysa sa anumang iba pa, na nagpapahiwatig na ang mga mina ay matatagpuan sa $x_0$ at $x_2$. Ginamit natin ang isang quantum computer para lutasin ang isang maliit na laro ng Minesweeper!

Siyempre, ang pinakamahusay na mga klasikal na algorithm para sa minesweeper ay mas mahusay kaysa sa isang brute-force na paghahanap sa lahat ng posibleng configuration ng mina — pinagsasamantalahan nila ang istraktura ng grid. Ang Grover's algorithm ay mag-aalok lamang ng kalamangan sa mga napakahirap na board na dinisenyo para maging pinaka-malabo, at kahit noon, ang quadratic speedup ay hindi makakasabay sa exponential na paglago nang walang katiyakan. Ngunit ang tunay na aral ay ang pamamaraan: ang pag-encode ng mga constraint ng problema sa isang quantum oracle ay isang makapangyarihang pattern na umaabot sa constraint satisfaction, combinatorial optimization, at marami pang ibang domain.

Mga Tanong at kritikal na konsepto:

Mga kritikal na konsepto:

Sa module na ito, natutunan natin ang ilang pangunahing katangian ng Grover's algorithm:

• Habang ang mga klasikal na unstructured search algorithm ay nangangailangan ng bilang ng mga query na lumalago nang linearly sa laki ng espasyo, $N,$ ang Grover's algorithm ay nangangailangan ng bilang ng mga query na lumalago tulad ng $\sqrt{N}.$
• Ang Grover's algorithm ay kinabibilangan ng pag-uulit ng isang serye ng mga operasyon (karaniwang tinatawag na "Grover operator") nang $t$ na beses, na pinili upang gawing pinaka-malamang na masukat ang mga target na estado.
• Ang Grover's algorithm ay maaaring patakbuhin na may mas kaunti kaysa sa $t$ na pag-uulit at makapag-amplify pa rin ng mga target na estado.
• Ang Grover's algorithm ay angkop sa query model ng computation at pinakamakatuturan kapag isang tao ang kumokontrol sa paghahanap at ang isa ay kumokontrol/nagtatayo ng oracle. Maaari din itong maging kapaki-pakinabang bilang isang subroutine sa iba pang mga quantum computation.
• Ang isang oracle ay maaaring maitayo mula sa mga constraint ng problema sa halip na mula sa kaalaman ng solusyon, gaya ng ipinakita sa halimbawa ng Minesweeper.

Mga T/M na tanong:

1. T/M Ang Grover's algorithm ay nagbibigay ng exponential na pagpapabuti kumpara sa mga klasikal na algorithm sa bilang ng mga query na kailangan upang mahanap ang isang markadong estado sa unstructured search.

2. T/M Ang Grover's algorithm ay gumagana sa pamamagitan ng paulit-ulit na pagdaragdag ng posibilidad na masukat ang isang estado ng solusyon.

3. T/M Habang mas maraming beses na ini-iterate ang Grover operator, mas mataas ang posibilidad ng pagsusukat ng isang estado ng solusyon.

Mga MC na tanong:

1. Piliin ang pinakamahusay na opsyon upang makumpleto ang pangungusap. Ang pinakamahusay na estratehiya upang matagumpay na magamit ang Grover's algorithm sa mga modernong quantum na computer ay ang pag-iterate ng Grover operator...

• a. Isang beses lamang.
• b. Palaging $t$ na beses, upang ma-maximize ang probability amplitude ng mga estado ng solusyon.
• c. Hanggang $t$ na beses, bagaman ang mas kaunti ay maaaring sapat upang mapansin ang mga estado ng solusyon.
• d. Hindi bababa sa 10 beses.

2. Ang isang phase query circuit ay ipinapakita dito na gumaganap bilang isang oracle upang markahan ang isang tiyak na estado ng isang phase flip. Alin sa mga sumusunod na estado ang minarkahan ng circuit na ito?

• a. $|0000\rangle$
• b. $|0101\rangle$
• c. $|0110\rangle$
• d. $|1001\rangle$
• e. $|1010\rangle$
• f. $|1111\rangle$

3. Ipagpalagay na nais mong maghanap ng tatlong markadong estado mula sa isang set ng 128. Ano ang pinakamainam na bilang ng pag-uulit ng Grover operator upang ma-maximize ang mga amplitude ng mga markadong estado?

• a. 1
• b. 3
• c. 5
• d. 6
• e. 20
• f. 33

Mga tanong para sa talakayan:

1. Anong iba pang mga problema ang maaari mong i-formulate bilang isang Grover search? Mag-isip ng mga problema kung saan mahirap hanapin ang solusyon ngunit madali itong ma-verify.

2. Makikita mo ba ang anumang mga problema sa pag-scale ng Grover's algorithm sa mga modernong quantum na computer?