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.

Matematika

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 paghahanapna 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 nagbabalik-tanda ng $Z_f$ sa 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.

Malinaw na caveat

Para makapag-apply ng algoritmo ni Grover, kailangan naming buuin ang Grover operator, na nangangahulugang kailangan naming makapag-flip ng phase sa mga estado na nakakatugon sa aming mga pamantayan sa solusyon. Nagtatanong ito: kung gayon na ang aming alam tungkol sa aming hanay ng solusyon upang makadisenyo tayo ng isang quantum circuit para malagyan ng label ang bawat isa, ano pa ang hinahanap natin?! Ang sagot ay tatlong-bahagi, at babalik tayo rito sa buong tutorial:

(1) Ang mga ganitong uri ng query algorithm ay madalas na kinabibilangan ng dalawang partido: ang isa na may oracle na nagtatatag ng mga pamantayan sa solusyon, at isa pang sumusubok na hulaan/hanapin ang isang solution state. Ang katotohanan na ang isang tao ay maaaring bumuo ng oracle ay hindi nagpapawalang-bisa ng pangangailangan para sa paghahanap.

(2) Mayroong mga problema kung saan mas madaling tukuyin ang isang pamantayan sa solusyon kaysa hanapin ang solusyon. Ang pinakakilalang halimbawa nito ay malamang ang pagtukoy ng mga pangunahing salik ng malalaking numero. Ang algoritmo ni Grover ay hindi partikular na epektibo sa paglutas ng partikular na problemang iyon; gagamitin namin ang algoritmo ni Shor para sa prime factoring. Ito ay isang halimbawa lamang para ituro na ang pag-alam ng pamantayan sa gawi ng isang estado ay hindi laging katulad ng pag-alam sa estado mismo.

(3) Ang algoritmo ni Grover ay hindi nagbabalik lamang ng klasikal na data. Totoo, kung gagawa tayo ng pagsukat ng panghuling estado pagkatapos ng $t$ na mga paulit-ulit ng Grover operator, malamang na makakakuha tayo ng klasikal na impormasyon na nagtatukoy sa solution state. Ngunit paano kung hindi natin gusto ang klasikal na impormasyon; paano kung gusto natin ng isang solution state na inihanda sa isang quantum computer para sa karagdagang paggamit sa isa pang algorithm? Ang algoritmo ni Grover ay talagang gumagawa ng isang quantum state na may mabibigat na mga solusyon. Kaya maaari mong asahan na mahanap ang algoritmo ni Grover bilang isang subroutine sa mas kumplikadong mga quantum algorithm.

Sa mga bagay na 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, at lilipat tayo sa mga halimbawa kung saan nagiging mas malinaw ang pagiging kapaki-pakinabang ng algoritmo ni Grover.

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
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-makabuluhang (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 itinalo 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 makukuha mula sa ekspresyong ito:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

Dito, ang $A_1$ ay ang bilang ng mga solusyon o target na 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.

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: Pamantayan maliban sa isang partikular na bitstring

Bilang huling ilustrasyon ng kung paano maaaring maging kapaki-pakinabang ang Grover's algorithm sa konteksto ng isang subroutine, isipin natin na kailangan natin ng mga quantum na estado na may isang tiyak na bilang ng 1 sa representasyong bitstring. Ito ay karaniwan sa mga sitwasyon kung saan kasangkot ang mga batas ng konserbasyon. Halimbawa, sa konteksto ng quantum chemistry, ang isang 1 na estado ng isang qubit ay madalas na ina-map sa pag-ocupar ng isang electronic orbital. Upang mapanatili ang singil, ang kabuuang bilang ng 1 ay dapat na manatiling pare-pareho. Ang mga constraint na tulad nito ay napakaraming gamitin kaya may espesyal silang pangalan: Hamming weight constraints, at ang bilang ng 1 sa estado ay tinatawag na Hamming weight.

Hakbang 1:

Una ay sumulat tayo ng function na nagmamarka ng mga estado na may nais na Hamming weight. Isusulat natin ito sa pangkalahatan para sa hindi tinukoy na bilang ng mga qubit na num_qubits at target na Hamming weight na target_weight.

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

Mula dito ang buong proseso ay kapareho ng sa nakaraang dalawang aktibidad. Para sa kaiklian, ang mga hakbang ng Qiskit patterns ay ipinapakita lamang sa mga komento ng code dito.

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(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()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

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)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

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()

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

ibm_brisbane

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  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

Dito ang Grover's algorithm ay tunay na naghanda ng mga estado na may Hamming weight na 2 upang mas malamang na masukat kaysa sa anumang ibang estado, halos isang order of magnitude na mas malamang.

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.

Mga Tanong

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 kondisyon ang maaari mong gamitin sa isang quantum oracle? Isaalang-alang ang mga kondisyon na madaling sabihin o ipataw sa isang bitstring ngunit hindi lamang pagsulat ng mga markadong bitstring.

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