Algoritmul lui Grover

Pentru acest modul Qiskit în Classrooms, studenții trebuie să aibă un mediu Python funcțional cu următoarele pachete instalate:

• qiskit v2.1.0 sau mai nou
• qiskit-ibm-runtime v0.40.1 sau mai nou
• qiskit-aer v0.17.0 sau mai nou
• qiskit.visualization
• numpy
• pylatexenc

Pentru a configura și instala pachetele de mai sus, consultă ghidul Instalare Qiskit. Pentru a rula joburi pe calculatoare cuantice reale, studenții vor trebui să își creeze un cont IBM Quantum® urmând pașii din ghidul Configurează-ți contul IBM Cloud.

Acest modul a fost testat și a folosit 12 secunde de timp QPU. Aceasta este o estimare de bună-credință; utilizarea ta efectivă poate varia.

# 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'

Introducere

Algoritmul lui Grover este un algoritm cuantic fundamental care abordează problema căutării nestructurate: dat fiind un set de $N$ elemente și o modalitate de a verifica dacă un anumit element este cel căutat, cât de repede poți găsi elementul dorit? În calculul clasic, dacă datele nu sunt sortate și nu există nicio structură de exploatat, cea mai bună abordare este să verifici fiecare element unul câte unul, ceea ce duce la o complexitate a interogărilor de $O(N)$ — în medie, va trebui să verifici aproximativ jumătate dintre elemente înainte de a găsi ținta.

Algoritmul lui Grover, introdus de Lov Grover în 1996, demonstrează cum un calculator cuantic poate rezolva această problemă mult mai eficient, necesitând doar $O(\sqrt{N})$ pași pentru a găsi elementul marcat cu probabilitate ridicată. Aceasta reprezintă o accelerare pătratică față de metodele clasice, semnificativă pentru seturi mari de date.

Algoritmul operează în următorul context:

• Configurarea problemei: Ai o funcție $f(x)$ care returnează 1 dacă $x$ este elementul dorit și 0 în caz contrar. Această funcție este adesea numită oracol sau cutie neagră, deoarece poți afla informații despre date doar interogând $f(x)$.
• Utilitatea cuantică: În timp ce algoritmii clasici pentru această problemă necesită, în medie, $N/2$ interogări, algoritmul lui Grover poate găsi soluția în aproximativ $\pi\sqrt{N}/4$ interogări, ceea ce este mult mai rapid pentru $N$ mare.
• Cum funcționează (la nivel înalt):
  • Calculatorul cuantic creează mai întâi o superpozițe a tuturor stărilor posibile, reprezentând toate elementele posibile simultan.
  • Apoi aplică în mod repetat o secvență de operații cuantice (iterația Grover) care amplifică probabilitatea răspunsului corect și o diminuează pe cea a celorlalte.
  • După suficiente iterații, măsurarea stării cuantice produce răspunsul corect cu probabilitate ridicată.

Iată o diagramă foarte simplificată a algoritmului lui Grover, care omite multe detalii. Pentru o diagramă mai detaliată, consultă acest articol.

Câteva aspecte de reținut despre algoritmul lui Grover:

• Este optim pentru căutarea nestructurată: niciun algoritm cuantic nu poate rezolva problema cu mai puțin de $O(\sqrt{N})$ interogări.
• Oferă doar o accelerare pătratică, nu exponențială — spre deosebire de alți algoritmi cuantici (de exemplu, algoritmul lui Shor pentru factorizare).
• Are implicații practice, cum ar fi accelerarea potențială a atacurilor prin forță brută asupra sistemelor criptografice, deși accelerarea nu este suficientă pentru a sparge singură cea mai mare parte din criptografia modernă.

Pentru studenții din ciclul universitar familiarizați cu conceptele de bază ale calculului și cu modelele de interogare, algoritmul lui Grover oferă o ilustrare clară a modului în care calculul cuantic poate depăși abordările clasice pentru anumite probleme, chiar și atunci când îmbunătățirea este „doar" pătratică. Servește, de asemenea, ca poartă de intrare în înțelegerea algoritmilor cuantici mai avansați și a potențialului mai larg al calculului cuantic.

Amplificarea amplitudinii este un algoritm cuantic de uz general, sau subrutină, care poate fi folosit pentru a obține o accelerare pătratică față de o serie de algoritmi clasici. Algoritmul lui Grover a fost primul care a demonstrat această accelerare pe probleme de căutare nestructurată. Formularea unei probleme de căutare Grover necesită o funcție oracol care marchează una sau mai multe stări din baza computațională drept stările pe care dorim să le găsim, și un circuit de amplificare care crește amplitudinea stărilor marcate, suprimând în consecință stările rămase.

Aici demonstrăm cum să construiești oracoli Grover și să folosești GroverOperator din biblioteca de circuit-uri Qiskit pentru a configura cu ușurință o instanță de căutare Grover. Primitivul Sampler din runtime permite execuția fără probleme a Circuit-urilor Grover.

Teorie

Să presupunem că există o funcție $f$ care mapează șiruri binare la o singură variabilă binară, adică

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

Un exemplu definit pe $\Sigma^6$ este

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

Un alt exemplu definit pe $\Sigma^{2n}$ este

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

Ești solicitat să găsești stările cuantice corespunzătoare acelor argumente $x$ ale lui $f(x)$ care sunt mapate la 1. Cu alte cuvinte, găsește toți $\{x_1\}\in \Sigma^n$ astfel încât $f(x_1)=1$ (sau, dacă nu există soluție, raportează acest lucru). Vom denumi non-soluțiile $x_0$. Bineînțeles, vom face acest lucru pe un calculator cuantic, folosind stări cuantice, astfel că este util să exprimi aceste șiruri binare ca stări:

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

Folosind notația stărilor cuantice (Dirac), căutăm una sau mai multe stări speciale $\{|x_1\rangle\}$ într-un set de $N=2^n$ stări posibile, unde $n$ este numărul de Qubiți, iar non-soluțiile sunt notate cu $\{|x_0\rangle\}.$

Putem considera că funcția $f$ este furnizată de un oracol: o cutie neagră pe care o putem interoga pentru a-i determina efectul asupra unei stări $|x\rangle.$ În practică, vom cunoaște adesea funcția, dar poate fi foarte complicat de implementat, ceea ce înseamnă că reducerea numărului de interogări sau aplicații ale lui $f$ ar putea fi importantă. Alternativ, ne putem imagina o paradigmă în care o persoană interoghează un oracol controlat de o altă persoană, astfel încât nu cunoaștem funcția oracolului, ci cunoaștem doar acțiunea sa asupra anumitor stări prin interogare.

Aceasta este o problemă de căutare nestructurată, în sensul că nu există nimic special în $f$ care să ne ajute în căutare. Rezultatele nu sunt sortate și nici soluțiile nu sunt cunoscute a fi grupate și așa mai departe. Consideră cărțile de telefon vechi, tipărite, ca analogie. Această căutare nestructurată ar fi ca și cum ai parcurge cartea căutând un anumit număr, nu ca și cum ai căuta printr-o listă alfabetică de nume.

În cazul în care se caută o singură soluție, clasic, acest lucru necesită un număr de interogări liniar în $N$. Evident, ai putea găsi o soluție din prima încercare, sau s-ar putea să nu găsești nicio soluție în primele $N-1$ încercări, astfel că trebuie să interoghezi al $N$-lea input pentru a vedea dacă există vreo soluție. Deoarece funcțiile nu au nicio structură exploatabilă, vei necesita $N/2$ încercări în medie. Algoritmul lui Grover necesită un număr de interogări sau calcule ale lui $f$ care scalează ca $\sqrt{N}.$

Schiță a Circuit-urilor din algoritmul lui Grover

O parcurgere matematică completă a algoritmului lui Grover poate fi găsită, de exemplu, în Fundamentals of quantum algorithms, un curs susținut de John Watrous pe IBM Quantum Learning. O tratare condensată este furnizată într-o anexă la sfârșitul acestui modul. Dar deocamdată, vom trece în revistă doar structura generală a Circuit-ului cuantic care implementează algoritmul lui Grover.

Algoritmul lui Grover poate fi descompus în următoarele etape:

• Pregătirea unei superpozițe inițiale (aplicarea Gate-urilor Hadamard pe toți Qubiții)
• „Marcarea" stării(stărilor) țintă cu o inversare de fază
• O etapă de „difuzie" în care Gate-uri Hadamard și o inversare de fază sunt aplicate pe toți Qubiții.
• Posibile repetări ale etapelor de marcare și difuzie pentru a maximiza probabilitatea de a măsura starea țintă
• Măsurare

Adesea, Gate-ul de marcare $Z_f$ și straturile de difuzie formate din $H,$ $Z_{\text{OR}},$ și $H$ sunt denumite colectiv „operatorul Grover". În această diagramă, este reprezentată o singură repetiție a operatorului Grover.

Gate-urile Hadamard $H$ sunt bine cunoscute și folosite pe scară largă în calculul cuantic. Gate-ul Hadamard creează stări de superpozițe. Concret, este definit prin

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

Acțiunea sa asupra oricărei alte stări este definită prin liniaritate. În special, un strat de poartă-uri Hadamard ne permite să trecem de la starea inițială cu toți Qubiții în $|0\rangle$ (notată $|0\rangle^{\otimes n}$) la o stare în care fiecare qubit are o anumită probabilitate de a fi măsurat în $|0\rangle$ sau $|1\rangle;$ aceasta ne permite să explorăm spațiul tuturor stărilor posibile diferit față de calculul clasic.

O proprietate corolar importantă a Gate-ului Hadamard este că aplicarea sa a doua oară poate anula astfel de stări de superpozițe:

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

Acest lucru va fi important imediat.

Verifică-ți înțelegerea

Citește întrebarea de mai jos, gândește-te la răspunsul tău, apoi apasă pe triunghi pentru a dezvălui soluția.

Pornind de la definiția Gate-ului Hadamard, demonstrează că o a doua aplicare a Gate-ului Hadamard anulează astfel de superpozițe, conform afirmației de mai sus.

Răspuns:

Când aplicăm X la starea $|+\rangle$, obținem valoarea +1 și la starea $|-\rangle$ obținem -1, deci dacă am avea o distribuție 50-50, am obține o valoare de așteptare de 0.

Gate-ul $Z_\text{OR}$ este mai puțin comun și este definit conform

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

În final, Gate-ul $Z_f$ este definit prin

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

Observă că efectul acestuia este că $Z_f$ inversează semnul pe o stare țintă pentru care $f(x) = 1$ și lasă celelalte stări neafectate.

La un nivel foarte înalt și abstract, poți gândi pașii din Circuit în felul următor:

• Primul strat Hadamard: pune Qubiții într-o superpozițe a tuturor stărilor posibile.
• $Z_f$: marchează starea(stările) țintă adăugând un semn „-" în față. Acest lucru nu modifică imediat probabilitățile de măsurare, dar schimbă modul în care se va comporta starea țintă în pașii următori.
• Un alt strat Hadamard: semnul „-" introdus în pasul anterior va schimba semnul relativ dintre anumiți termeni. Deoarece Gate-urile Hadamard transformă un amestec de stări computaționale $(|0\rangle+|1\rangle)/\sqrt{2}$ într-o stare computațională, $|0\rangle,$ și transformă $(|0\rangle-|1\rangle)/\sqrt{2}$ în $|1\rangle,$ această diferență de semn relativ poate începe acum să joace un rol în ce stări sunt măsurate.
• Un ultim strat de poartă-uri Hadamard este aplicat, după care se efectuează măsurătorile. Vom vedea în mai mare detaliu cum funcționează acest lucru în secțiunea următoare.

Exemplu

Pentru a înțelege mai bine cum funcționează algoritmul lui Grover, să lucrăm printr-un exemplu mic, cu doi qubiți. Aceasta poate fi considerată opțională pentru cei care nu se concentrează pe mecanica cuantică și notația Dirac. Dar pentru cei care speră să lucreze substanțial cu calculatoare cuantice, este foarte recomandată.

Iată diagrama circuitului cu stările cuantice etichetate în diferite poziții pe parcurs. Reține că, cu doar doi qubiți, există doar patru stări posibile care ar putea fi măsurate în orice circumstanțe: $|00\rangle$, $|01\rangle$, $|10\rangle$ și $|11\rangle$.

Să presupunem că oracolul ($Z_f$, necunoscut nouă) marchează starea $|01\rangle$. Vom parcurge acțiunile fiecărui set de poartă-uri cuantice, inclusiv oracolul, și vom vedea ce distribuție de stări posibile apare la momentul măsurătorii. La bun început, avem

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

Folosind definiția Gate-urilor Hadamard, avem

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

Acum oracolul marchează starea țintă:

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

Observă că în această stare, toate cele patru rezultate posibile au aceeași probabilitate de a fi măsurate. Toate au o pondere de magnitudine $1/2,$ ceea ce înseamnă că fiecare are o șansă de $|1/2|^2=1/4$ de a fi măsurată. Așadar, deși starea $|01\rangle$ este marcată prin faza „-", aceasta nu a dus încă la nicio creștere a probabilității de a măsura acea stare. Continuăm aplicând următorul strat de poartă-uri Hadamard.

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

Combinând termenii similari, obținem

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

Acum $Z_{\text{OR}}$ inversează semnul tuturor stărilor cu excepția lui $|00\rangle$:

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

Și în final, aplicăm ultimul strat de poartă-uri Hadamard:

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

Merită să parcurgi combinarea acestor termeni ca să te convingi că rezultatul este într-adevăr:

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

Adică, probabilitatea de a măsura $|01\rangle$ este de 100% (în absența zgomotului și a erorilor), iar probabilitatea de a măsura orice altă stare este zero.

Acest exemplu cu doi qubiți a fost un caz deosebit de curat; algoritmul lui Grover nu va produce întotdeauna o șansă de 100% de a măsura starea țintă. Mai degrabă, va amplifica probabilitatea de a măsura starea țintă. De asemenea, operatorul Grover poate fi necesar să fie repetat de mai multe ori.

În secțiunea următoare, vom pune acest algoritm în practică folosind calculatoare cuantice IBM® reale.

Imaginea geometrică

Exemplul cu doi qubiți de mai sus a arătat cum funcționează algebra pentru un caz mic, dar există un mod mult mai intuitiv de a înțelege algoritmul lui Grover: ca o secvență de reflecții geometrice într-un plan bidimensional. Mai jos descriem această imagine. Poți vedea, de asemenea, cursul lui John Watrous Fundamentals of Quantum Algorithms pentru mai multe detalii.

Construirea planului. Putem descompune starea inițială de superpozițe $|\psi\rangle$ în două componente. Starea corectă — cea pe care o căutăm — o numim $|A_1\rangle$. Orice altă stare, luate împreună, o numim $|A_0\rangle$. Prin definiție, $|A_1\rangle$ și $|A_0\rangle$ sunt ortogonale una față de cealaltă, deci le putem reprezenta ca axe perpendiculare într-un spațiu abstract, bidimensional. Deoarece $|\psi\rangle$ este o combinație liniară a acestor două componente, se află la un unghi mic $\theta$ față de axa $|A_0\rangle$ — aproape de $|A_0\rangle$, deoarece la început, doar o fracție mică din stare se află în componenta corectă $|A_1\rangle$.

Reflecții. Faptul matematic esențial de care avem nevoie este că un operator de forma

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

reflectă orice stare față de axa definită de $|v\rangle.$ Pentru a înțelege de ce, consideră două cazuri: o stare de-a lungul lui $|v\rangle$ rămâne nemodificată, iar o stare perpendiculară pe $|v\rangle$ își inversează semnul. Orice altă stare poate fi descompusă în aceste două componente, iar operatorul acționează asupra fiecăreia în consecință — ceea ce este exact o reflecție față de $|v\rangle$.

Se dovedește că atât pașii oracolului, cât și cei de difuzie din algoritmul lui Grover pot fi exprimați ca reflecții în această imagine geometrică.

Oracolul ca reflecție. Oracolul inversează semnul stării $|A_1\rangle$ și lasă totul altceva neschimbat. Aceasta este echivalentă cu o reflecție față de axa $|A_0\rangle$.

Difuzia ca reflecție. Este puțin mai dificil de văzut cum operatorul de difuzie este, de asemenea, o reflecție. Operatorul de difuzie este

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

$Z_{\text{OR}}$ în sine este o reflecție față de starea all-zero, deoarece inversează semnul oricărei stări care nu este $|0\rangle^{\otimes n}$. Aceasta poate fi scrisă ca $2|0\rangle\langle 0| - I$. Straturile Hadamard din jur efectuează efectiv o schimbare de bază, transformând axa de reflecție. Reamintește-ți că $H^{\otimes n}$ mapează $|0\rangle^{\otimes n}$ la superpozițea uniformă $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. Deoarece Hadamard este propriul său invers, expresia completă devine

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

care este o reflecție față de $|u\rangle$. Deoarece $|u\rangle$ este foarte aproape de $|\psi\rangle$ (ambele sunt aproape de-a lungul lui $|A_0\rangle$), această a doua reflecție trimite starea la un unghi $2\theta$ față de locul de unde a început.

Rotație cu $2\theta$. Efectul combinat al acestor două reflecții este o rotație cu $2\theta$ spre $|A_1\rangle$. Fiecare iterație succesivă a operatorului Grover rotește starea cu încă $2\theta.$

Numărul optim de iterații. Scopul nostru este să rotim starea cât mai aproape de $|A_1\rangle$ posibil, ceea ce înseamnă să rotim cu aproximativ $\pi/2$ radiani (un sfert de rotație). Dacă fiecare iterație contribuie cu $2\theta$, numărul optim de iterații $t$ satisface

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

Pentru o singură soluție printre $N$ stări, unghiul inițial este $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (pentru $N$ mare). Substituind,

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

De aici provine celebra accelerare $\sqrt{N}$: avem nevoie de doar $O(\sqrt{N})$ iterații pentru a atinge ținta, în loc de verificările $O(N)$ pe care le-ar necesita o căutare clasică.

Mai general, dacă există $|A_1|$ stări soluție printre $N$ stări totale, numărul optim de iterații este

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

Reține că dacă aplici prea multe iterații, rotești dincolo de $|A_1\rangle$ și probabilitatea de a găsi starea țintă va începe să scadă din nou. Găsirea numărului corect de iterații este importantă, deși pe hardware-ul cuantic zgomotos numărul optim din punct de vedere experimental poate diferi față de această formulă ideală.

De ce este util algoritmul lui Grover?

La acest punct te-ai putea întreba: tocmai am construit un oracol care marchează o stare țintă — dar pentru a-l construi, a trebuit să cunoaștem starea țintă. Deci ce căutăm de fapt?

Aceasta este o întrebare legitimă, și există mai multe răspunsuri bune.

• Modelul de interogare este un instrument teoretic. Modelul de calcul bazat pe interogări nu a fost niciodată conceput pentru a fi direct practic. Scopul său este să ne ofere o modalitate curată de a analiza complexitatea algoritmică prin separarea unei probleme în două părți: oracolul și tot restul. Cât de dificilă este căutarea, dând că verificarea este gratuită? Cum scalează numărul de interogări cu dimensiunea intrării? Acestea sunt întrebări utile chiar dacă niciun sistem real nu funcționează exact în acest fel.

• Poți să te gândești la aceasta și ca la o activitate cu două părți: o persoană cunoaște starea țintă și construiește oracolul; sarcina celeilalte persoane este să găsească răspunsul folosind oracolul ca o cutie neagră, fără să privească înăuntru. În Activitatea 2 de mai jos, vei face exact acest lucru cu un partener.

• Amplificarea amplitudinii este o subrutină cu aplicabilitate largă. Chiar dacă această primă demonstrație pare circulară, mecanismul de bază — numit amplificarea amplitudinii — apare din nou și din nou în calculul cuantic. Ceea ce construim cu adevărat aici este o intuiție pentru un instrument care apare ca subrutină în mulți algoritmi cuantici mai complecși.

• Există probleme în care poți construi un oracol fără să cunoști răspunsul. Insight-ul cheie este că există o întreagă clasă de probleme pentru care este foarte greu să găsești o soluție, dar foarte ușor să verifici că o soluție dată este corectă. Factorizarea este un exemplu: dat un produs a doi numere prime mari, este extrem de dificil să determini care sunt acele numere prime, dar odată ce le ai, le poți înmulți ușor pentru a verifica. (Avem un algoritm mai bun decât Grover pentru factorizare specifică — algoritmul lui Shor — dar aceasta este departe de singura problemă cu această caracteristică.) Sudoku, satisfacerea constrângerilor și chiar clasicul joc Minesweeper sunt toate probleme dificil de rezolvat, dar ușor de verificat.

De ce este relevant? Înseamnă că putem cunoaște toate condițiile și cerințele pe care o soluție trebuie să le satisfacă, și putem codifica aceste cerințe într-un Circuit cuantic care servește drept oracol — chiar dacă nu cunoaștem soluția în sine. Algoritmul lui Grover o va găsi pentru noi.

Având aceste idei în minte, să parcurgem mai multe exemple. Vom începe cu un exemplu în care starea de soluție este clar specificată, astfel încât să putem urmări logica algoritmului. Vom trece apoi la o activitate cu două părți și, în final, la un exemplu în care oracolul este construit din constrângerile problemei, nu din cunoașterea răspunsului.

Import-uri generale și abordare

Începem prin a importa mai multe pachete necesare.

# 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

Pe tot parcursul acestui și al altor tutoriale, vom folosi un cadru pentru calculul cuantic cunoscut sub numele de „Qiskit patterns", care împarte fluxurile de lucru în următorii pași:

• Pasul 1: Maparea intrărilor clasice la o problemă cuantică
• Pasul 2: Optimizarea problemei pentru execuție cuantică
• Pasul 3: Execuția folosind Qiskit Runtime Primitives
• Pasul 4: Post-procesare și analiză clasică

În general, vom urma acești pași, deși nu îi vom eticheta întotdeauna explicit.

Activitatea 1: Găsește o singură stare țintă dată

Pasul 1: Mapează intrările clasice la o problemă cuantică

Avem nevoie ca poarta de interogare de fază să aplice o fază globală (-1) pe stările soluție și să lase stările non-soluție neafectate. Altfel spus, algoritmul lui Grover necesită un oracol care specifică una sau mai multe stări ale bazei de calcul marcate, unde „marcat" înseamnă o stare cu o fază de -1. Acest lucru se realizează folosind o poartă controlled-Z sau generalizarea sa multi-controlată pe $N$ Qubiți. Pentru a înțelege cum funcționează, considerăm un exemplu specific pentru șirul de biți {110}. Dorim un circuit care acționează asupra stării $|\psi\rangle = |q_2,q_1,q_0\rangle$ și aplică o fază dacă $|\psi\rangle = |011\rangle$ (unde am inversat ordinea șirului binar, din cauza notației din Qiskit, care plasează qubit-ul cel mai puțin semnificativ (de obicei 0) la dreapta).

Astfel, dorim un circuit $Z_f$ care realizează

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

Putem folosi poarta cu mai mulți controali și mai multe ținte (MCMTGate) pentru a aplica o poartă Z controlată de toți Qubiții (inversarea fazei dacă toți Qubiții sunt în starea $|1\rangle$). Desigur, unii dintre Qubiții din starea dorită pot fi $|0\rangle$. Prin urmare, pentru acei Qubiți trebuie mai întâi să aplicăm o poartă X, apoi să realizăm Gate Z multi-controlată, și apoi să aplicăm din nou Gate X pentru a anula modificarea. MCMTGate arată astfel:

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

Observă că mulți Qubiți pot fi implicați în procesul de control (aici sunt trei), dar niciun qubit individual nu este desemnat drept țintă. Aceasta deoarece întreaga stare primește un semn global „-" (inversare de fază); Gate afectează toți Qubiții în mod echivalent. Aceasta este diferit de multe alte Gate cu mai mulți Qubiți, precum Gate CX, care are un singur qubit de control și un singur qubit țintă.

În codul următor, definim o poartă de interogare de fază (sau oracol) care face exact ce am descris mai sus: marchează una sau mai multe stări ale bazei de intrare definite prin reprezentarea lor ca șir de biți. Gate MCMT este utilizată pentru a implementa Gate Z multi-controlată.

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

Acum alegem o stare „marcată" specifică ca țintă și aplicăm funcția pe care tocmai am definit-o. Să vedem ce fel de circuit a creat.

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

Dacă Qubiții 1-3 sunt în starea $|1\rangle$, iar qubit 0 este inițial în starea $|0\rangle$, prima Gate X va întoarce qubit 0 la $|1\rangle$ și toți Qubiții vor fi în $|1\rangle.$ Aceasta înseamnă că Gate MCMT va aplica o schimbare de semn globală sau inversare de fază, după cum dorim. În orice alt caz, fie Qubiții 1-3 sunt în starea $|0\rangle$, fie qubit 0 este întors la $|0\rangle$, și inversarea de fază nu va fi aplicată. Vedem că acest circuit marchează într-adevăr starea dorită $|0111\rangle,$ adică șirul de biți {1110}. Operatorul Grover complet constă din poarta de interogare de fază (oracolul), straturile Hadamard și operatorul $Z_\text{OR}$. Putem folosi funcția built-in grover_operator pentru a construi aceasta din oracolul pe care l-am definit mai sus.

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

Așa cum am discutat în imaginea geometrică de mai sus, ar putea fi necesar să aplicăm operatorul Grover de mai multe ori. Numărul optim de iterații $t$ pentru a maximiza amplitudinea stării țintă în absența zgomotului este

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

unde $|A_1|$ este numărul de stări soluție și $N=2^n$ este numărul total de stări. Pe calculatoarele cuantice moderne cu zgomot, numărul optim de iterații din punct de vedere experimental poate fi diferit — dar aici calculăm și folosim acest număr optim teoretic folosind $|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

Să construim acum un circuit care include Gate Hadamard inițiale pentru a crea o superpozițe a tuturor stărilor posibile și să aplicăm operatorul Grover numărul optim de ori.

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

Am construit Circuit-ul nostru Grover!

Pasul 2: Optimizează problema pentru execuția pe hardware cuantic

Am definit Circuit-ul nostru cuantic abstract, dar trebuie să îl rescriem în termenii Gate-urilor native ale calculatorului cuantic pe care dorim efectiv să îl folosim. De asemenea, trebuie să specificăm care Qubiți de pe calculatorul cuantic ar trebui utilizați. Din aceste motive și altele, trebuie acum să transpilăm Circuit-ul nostru. Mai întâi, să specificăm calculatorul cuantic pe care dorim să îl folosim.

Mai jos există cod pentru salvarea credențialelor la prima utilizare. Asigură-te că ștergi aceste informații din notebook după salvarea lor în mediul tău, astfel încât credențialele să nu fie partajate accidental când distribui notebook-ul. Consultă Configurează-ți contul IBM Cloud și Inițializează serviciul într-un mediu neîncrezător pentru mai multe îndrumări.

# 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'

Acum folosim un manager de pași preset pentru a optimiza Circuit-ul nostru cuantic pentru Backend-ul selectat.

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

Merită menționat în acest moment că adâncimea Circuit-ului cuantic transpilat este substanțială.

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

Acestea sunt numere destul de mari, chiar și pentru acest caz simplu. Deoarece toate Gate-urile cuantice (și în special Gate-urile cu doi Qubiți) sunt supuse erorilor și zgomotului, o serie de peste 100 de poartă cu doi Qubiți ar produce numai zgomot dacă Qubiții nu ar fi extrem de performanți. Să vedem cum se comportă acestea.

Pasul 3: Execută folosind primitivele Qiskit

Dorim să facem multe măsurători și să vedem care stare este cea mai probabilă. O astfel de amplificare de amplitudine este o problemă de eșantionare potrivită pentru execuție cu primitiva Qiskit Runtime Sampler.

Observă că metoda run() a Qiskit Runtime SamplerV2 acceptă un iterabil de blocuri unificate primitive (PUB-uri). Pentru Sampler, fiecare PUB este un iterabil în formatul (circuit, valori_parametri). Cu toate acestea, la minimum, acceptă o listă de circuit(e) cuantice.

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

Pentru a profita la maximum de această experiență, îți recomandăm cu tărie să rulezi experimentele pe calculatoarele cuantice reale disponibile de la IBM Quantum. Cu toate acestea, dacă ai epuizat timpul de QPU, poți decomenta liniile de mai jos pentru a finaliza această activitate folosind un 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()

Pasul 4: Post-procesare și returnarea rezultatului în formatul clasic dorit

Acum putem reprezenta grafic rezultatele eșantionării noastre într-o histogramă.

plot_distribution(dist)

Observăm că algoritmul lui Grover a returnat starea dorită cu cea mai mare probabilitate, cu cel puțin un ordin de mărime mai mare decât celelalte opțiuni. În activitatea următoare, vom folosi algoritmul într-un mod mai consistent cu fluxul de lucru în două etape al unui algoritm de interogare.

Verifică-ți înțelegerea

Citește întrebările de mai jos, gândește-te la răspuns, apoi apasă pe triunghi pentru a dezvălui soluția.

Tocmai am căutat o singură soluție într-un set de $2^4=16$ stări posibile. Am determinat că numărul optim de repetări ale operatorului Grover este $t=3$. Ar fi crescut sau scăzut acest număr optim dacă am fi căutat (a) oricare dintre mai multe soluții sau (b) o singură soluție într-un spațiu cu mai multe stări posibile?

Răspuns:

Reamintește-ți că, atât timp cât numărul de soluții este mic față de întregul spațiu al soluțiilor, putem extinde funcția sinus în jurul unghiurilor mici și să folosim

$$(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) Din expresia de mai sus observăm că mărirea numărului de stări soluție ar reduce numărul de iterații. Cu condiția că fracția $\frac{|\mathcal{A}_1|}{N}$ rămâne mică, putem descrie cum scade $t$: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(b) Pe măsură ce spațiul soluțiilor posibile ($N$) crește, numărul de iterații necesar crește, dar doar ca $t~\sqrt{N}$.

Să presupunem că am putea mări dimensiunea bitstring-ului țintă la orice lungime și că rezultatul ar fi în continuare că starea țintă are o amplitudine de probabilitate cel puțin cu un ordin de mărime mai mare decât orice altă stare. Înseamnă că am putea folosi algoritmul lui Grover pentru a găsi starea țintă în mod fiabil?

Răspuns:

Nu. Să presupunem că am repeta prima activitate cu 20 de qubiți și că rulăm circuitul cuantic de un număr de ori num_shots = 10,000. O distribuție uniformă de probabilitate ar însemna că fiecare stare are o probabilitate de $10,000/2^{20}=0.00954$ de a fi măsurată chiar și o singură dată. Dacă probabilitatea de a măsura starea țintă ar fi de 10 ori mai mare decât a non-soluțiilor (și probabilitatea fiecărei non-soluții ar fi corespunzător ușor diminuată), ar exista doar aproximativ 10% șanse de a măsura starea țintă chiar și o singură dată. Ar fi extrem de puțin probabil să măsori starea țintă de mai multe ori, ceea ce ar face-o imposibil de distins față de multele stări non-soluție obținute aleatoriu. Vestea bună este că putem obține rezultate cu fidelitate și mai mare folosind supresia și mitigarea erorilor.

Activitatea 2: Un flux de lucru precis pentru algoritmul de interogare

Vom începe această activitate exact ca pe prima, cu deosebirea că acum vei lucra în pereche cu un alt entuziast Qiskit. Tu vei alege un bitstring secret, iar partenerul tău va alege un bitstring (în general) diferit. Fiecare dintre voi va genera un circuit cuantic care funcționează ca un oracol, iar apoi le veți schimba. Vei folosi apoi algoritmul lui Grover cu acel oracol pentru a determina bitstring-ul secret al partenerului tău.

Pasul 1: Maparea intrărilor clasice la o problemă cuantică

Folosind funcția grover_oracle definită mai sus, construiește un circuit oracol pentru una sau mai multe stări marcate. Asigură-te că îi spui partenerului tău câte stări ai marcat, astfel încât să poată aplica operatorul Grover de numărul optim de ori. Nu face bitstring-ul prea lung. 3-5 biți ar trebui să funcționeze fără dificultăți majore. Bitstring-urile mai lungi ar duce la circuite adânci care necesită tehnici mai avansate, cum ar fi mitigarea erorilor.

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

Acum ai creat un circuit cuantic care inversează faza stării tale țintă. Poți salva acest circuit ca my_circuit.qpy folosind sintaxa de mai jos.

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)

Trimite acum acest fișier partenerului tău (prin email, serviciu de mesagerie, un repo partajat etc.). Cere-i și partenerului să îți trimită circuitul său. Asigură-te că salvezi fișierul undeva ușor de găsit. Odată ce ai primit circuitul partenerului tău, l-ai putea vizualiza – dar asta ar încălca modelul de interogare. Adică modelăm o situație în care poți interoga oracolul (folosi circuitul oracol), dar nu îl poți examina pentru a determina ce stare vizează.

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

Întreabă-l pe partenerul tău câte stări țintă a codificat și introdu numărul mai jos.

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

Aceasta este folosită în expresia următoare pentru a determina numărul optim de iterații Grover.

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

Pasul 2: Optimizarea problemei pentru execuția pe hardware cuantic

Aceasta decurge exact ca înainte.

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

Pasul 3: Executarea folosind primitivele Qiskit

Aceasta este, de asemenea, identică cu procesul din prima activitate.

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

Pasul 4: Post-procesare și returnarea rezultatului în formatul clasic dorit

Afișează acum o histogramă a rezultatelor eșantionării tale. Una sau mai multe stări ar trebui să aibă o probabilitate de măsurare mult mai mare decât celelalte. Raportează-le partenerului tău și verifică dacă ai determinat corect stările țintă. În mod implicit, histograma afișată este pentru același Circuit din prima activitate. Ar trebui să obții rezultate diferite de la circuitul partenerului tău.

plot_distribution(dist)

Verifică-ți înțelegerea

Citește întrebările sau indicațiile de mai jos, gândește-te la răspuns sau discută procesul cu partenerul tău. Apasă pe triunghi pentru indicii sau sugestii.

Ar fi trebuit să obții corect starea (stările) țintă ale partenerului tău. Dacă nu ai reușit, lucrează cu partenerul tău pentru a identifica ce a mers greșit. Apasă mai jos pentru câteva idei.

Indicii:

• Vizualizează/desenează Circuit-ul partenerului tău și asigură-te că s-a încărcat corect.
• Compară Circuit-urile folosite și compară rezultatul așteptat cu cel obținut.
• Verifică adâncimea Circuit-urilor folosite pentru a te asigura că șirul de biți nu a fost prea lung sau că numărul de iterații Grover nu a fost prohibitiv de mare.

Dacă nu ai făcut-o deja, desenează Circuit-ul oracolului pe care ți l-a trimis partenerul. Încearcă să explici efectul fiecărui Gate și să argumentezi care a trebuit să fie starea țintă. Acest lucru va fi mult mai ușor în cazul unei singure stări marcate decât în cazul mai multor stări.

Indicii:

• Reamintește-ți că rolul oracolului este de a inversa semnul stării țintă.
• Reamintește-ți că MCMTGate inversează semnul unei stări dacă și numai dacă toți qubit-urile implicate în control sunt în starea $|1\rangle$.
• Dacă starea ta țintă are deja un $|1\rangle$ pe un anumit qubit, nu trebuie să faci nimic cu acel qubit. Dacă ținta ta are un $|0\rangle$ pe un anumit qubit și vrei ca MCMTGate să inverseze semnul, trebuie să aplici un poartă X acelui qubit în oracolul tău (și apoi să anulezi Gate-ul X după MCMTGate).

Repetă experimentul cu o iterație mai puțin a operatorului Grover. Mai obții răspunsul corect? De ce sau de ce nu?

Îndrumare:

Probabil că da, deși poate depinde de numărul de soluții codificate. Acest lucru evidențiază o subtilitate: numărul „optim" de iterații Grover este cel care face ca probabilitatea de a măsura starea marcată să fie cât mai mare posibil. Dar un număr mai mic de iterații decât acesta ar putea face în continuare starea marcată substanțial mai probabilă decât celelalte stări. Prin urmare, s-ar putea să te descurci cu mai puține iterații decât numărul optim. Aceasta reduce adâncimea Circuit-ului și, astfel, reduce ratele de eroare.

De ce ar putea cineva să vrea să folosească mai puține iterații Grover decât „numărul optim" identificat aici?

Răspuns:

Numărul „optim" de iterații Grover este cel care face ca probabilitatea de a măsura starea marcată să fie cât mai mare posibil în absența zgomotului. Dar un număr mai mic de iterații decât acesta ar putea face în continuare starea marcată substanțial mai probabilă decât celelalte stări. Astfel, s-ar putea să te descurci cu mai puține iterații decât numărul optim. Aceasta reduce adâncimea Circuit-ului și, astfel, reduce ratele de eroare.

Activitatea 3: Rezolvă o grilă Minesweeper cu algoritmul lui Grover

În secțiunea anterioară, am observat că algoritmul lui Grover devine cu adevărat util atunci când putem construi un oracol din constrângerile unei probleme, mai degrabă decât din cunoașterea răspunsului. Minesweeper este un exemplu perfect: celulele numerotate ne spun câte mine sunt adiacente, iar aceste constrângeri determină complet unde trebuie să se afle minele — dar găsirea configurației necesită căutare.

S-a dovedit că Minesweeper este NP-complet: este greu de rezolvat, dar ușor de verificat. Aceasta îl face un candidat natural pentru algoritmul lui Grover. Bineînțeles, nu putem rezolva încă o grilă completă 9$\times$9 pe un calculator cuantic zgomotos — circuitele ar fi mult prea adânci. În schimb, vom folosi o grilă mică ca demonstrație de tip toy a modului în care s-ar aborda o tablă mai mare pe o mașină tolerantă la erori din viitor.

Câteva avertismente importante. Algoritmul lui Grover oferă doar o accelerare pătratică față de căutarea clasică nestructurată. Minesweeper aproape sigur are o structură exploatabilă pe care un algoritm clasic inteligent ar putea-o folosi. Și pentru un spațiu de căutare care crește exponențial, chiar și îmbunătățirea $\sqrt{N}$ are limite. Dar să lăsăm aceste preocupări deoparte și să folosim această problemă toy pentru a ilustra cum se codifică constrângerile problemei într-un oracol cuantic.

Grila

Iată grila noastră de minesweeper simplificată:

Fiecare celulă goală poate fi reprezentată printr-o variabilă binară care indică dacă conține o mină. Le etichetăm $x_0$, $x_1$ și $x_2$, unde $x_i = 1$ înseamnă că există o mină pe acea celulă și $x_i = 0$ înseamnă că nu există:

Am putea rezolva aceasta mental în aproximativ jumătate de secundă, dar folosim această problemă toy pentru a ilustra cum ar putea fi abordată o tablă mult mai dificilă cu un calculator cuantic.

Codificarea constrângerilor

Fiecare celulă numerotată impune o condiție asupra celulelor goale adiacente. Trebuie să exprimăm aceste condiții ca expresii booleene care pot fi codificate într-un Circuit cuantic.

Celula „1" adiacentă lui $x_0$ și $x_1$ spune că exact una dintre ele conține o mină. Aceasta este exact operația sau-exclusiv (XOR), $\oplus$, care returnează adevărat când exact una dintre intrările sale este adevărată:

$$(x_0 \oplus x_1)$$

Similar, cealaltă celulă „1" (adiacentă lui $x_1$ și $x_2$) ne dă:

$$(x_1 \oplus x_2)$$

Celula „2" spune că două dintre cele trei celule goale trebuie să conțină mine. Deoarece XOR este o operație de paritate, $x_0 \oplus x_1 \oplus x_2$ returnează adevărat când un număr impar de variabile sunt adevărate. Dorim un număr par (mai precis doi) să fie adevărat, deci negăm cu $\lnot$:

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

În sine, această expresie ar fi satisfăcută fie de zero, fie de doi qubiți în starea $|1\rangle$, deoarece este o afirmație despre paritate. Dar combinată cu celelalte două clauze, care fiecare necesită cel puțin o mină, singura atribuire satisfăcătoare are exact două mine.

Toate trei condițiile trebuie satisfăcute simultan, deci le unim cu simboluri $\land$:

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

Pasul 1: Mapează intrările clasice la o problemă cuantică

Acum trebuie să codificăm această expresie booleană într-un Circuit cuantic care servește drept oracol. Versiunea cuantică a XOR poate fi realizată cu gate-uri CX (CNOT): aplicarea a două gate-uri CX de la qubiții de date la un qubit de lucru (ansilă) calculează efectiv XOR-ul lor și stochează rezultatul în ancilă.

Introducem trei qubiți de lucru — unul pentru fiecare clauză. Stocăm rezultatul fiecărei expresii booleene în qubit-ul de lucru corespunzător, apoi folosim un gate Z multi-controlat pentru a inversa faza stării cu trei qubiți care face ca toți trei qubiții de lucru să fie $|1\rangle$ (adică toate clauzele sunt satisfăcute simultan).

În prima celulă de cod de mai jos, construim jumătatea de „calcul" a oracolului — partea care evaluează fiecare clauză și scrie rezultatul în qubiții de lucru.

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

La acest punct, rezultatul fiecărei clauze este stocat în qubit-ul de lucru corespunzător. Acum avem nevoie ca starea cu trei qubiți de date care face ca toți trei qubiții de lucru să fie $|1\rangle$ să primească un semn minus. Facem aceasta cu un gate Z multi-controlat (implementat ca un gate MCX flancat de gate-uri Hadamard pe țintă).

După aplicarea inversării de fază, trebuie să dezcomputăm — să anulăm toți pașii de evaluare a clauzelor în ordine inversă — pentru a reseta qubiții de lucru la $|0\rangle.$ Acest lucru este esențial pentru ca qubiții de lucru să fie curați pentru iterațiile ulterioare ale operatorului Grover.

# 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")

Acest circuit este oracolul nostru: inversează faza stării qubiților de date care satisface toate trei constrângerile Minesweeper și lasă qubiții de lucru înapoi în $|0\rangle.$

Acum construim operatorul Grover complet din acest oracol. Observă argumentul reflection_qubits: transmitem doar qubiții de date x, deoarece qubiții de lucru nu fac parte din spațiul de căutare. Rolul lor este îndeplinit odată ce oracolul a fost aplicat.

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

Cu trei qubiți de date și o stare soluție, numărul optim de iterații Grover este $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, deci folosim două iterații. Aplicăm gate-uri Hadamard pe qubiții de date pentru a crea superpozițea inițială, compunem operatorul Grover de două ori și măsurăm doar qubiții de date.

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

Pasul 2: Optimizează problema pentru execuția pe hardware cuantic

Ca înainte, transpilăm circuitul pentru backend-ul țintă.

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)

Acum putem verifica adâncimea circuitului transpilat. Deoarece oracolul Minesweeper folosește qubiți de lucru și mai multe gate-uri CX, circuitul transpilat va fi mai adânc decât cele din activitățile anterioare.

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

Pasul 3: Execută folosind primitivele Qiskit

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

Pasul 4: Post-procesare și returnarea rezultatului în formatul clasic dorit

plot_distribution(dist)

Starea 101 ar trebui să apară cu o probabilitate mult mai mare decât orice altă stare, indicând că minele se află la $x_0$ și $x_2$. Am folosit un calculator cuantic pentru a rezolva un joc miniatural de Minesweeper!

Desigur, cei mai buni algoritmi clasici pentru minesweeper sunt mai buni decât o căutare prin forță brută prin toate configurațiile posibile de mine — ei exploatează structura grilei. Algoritmul lui Grover ar oferi un avantaj doar pe tablele extrem de dificile, concepute pentru a fi maxim ambigue, și chiar și atunci, accelerarea pătratică înseamnă că nu poate ține pasul cu creșterea exponențială la infinit. Dar adevărata concluzie este tehnica: codificarea constrângerilor problemei într-un oracol cuantic este un tipar puternic care se extinde la satisfacerea constrângerilor, optimizarea combinatorică și multe alte domenii.

Întrebări și concepte esențiale:

Concepte esențiale:

În acest modul, am învățat câteva caracteristici cheie ale algoritmului lui Grover:

• În timp ce algoritmii clasici de căutare nestructurată necesită un număr de interogări care crește liniar cu dimensiunea spațiului, $N,$ algoritmul lui Grover necesită un număr de interogări care crește ca $\sqrt{N}.$
• Algoritmul lui Grover presupune repetarea unei serii de operații (numite în mod obișnuit „operatorul Grover") de un număr de ori $t,$ ales astfel încât stările țintă să fie cât mai probabil de măsurat.
• Algoritmul lui Grover poate fi rulat cu mai puțin de $t$ iterații și tot amplifică stările țintă.
• Algoritmul lui Grover se încadrează în modelul de calcul bazat pe interogări și are cel mai mult sens atunci când o persoană controlează căutarea, iar alta controlează/construiește oracolul. Poate fi util și ca subrutină în alte calcule cuantice.
• Un oracol poate fi construit din constrângerile problemei mai degrabă decât din cunoașterea soluției, așa cum s-a demonstrat cu exemplul Minesweeper.

Întrebări A/F:

1. A/F Algoritmul lui Grover oferă o îmbunătățire exponențială față de algoritmii clasici în ceea ce privește numărul de interogări necesare pentru a găsi o singură stare marcată în căutarea nestructurată.

2. A/F Algoritmul lui Grover funcționează prin creșterea iterativă a probabilității ca o stare soluție să fie măsurată.

3. A/F Cu cât iterezi operatorul Grover de mai multe ori, cu atât probabilitatea de a măsura o stare soluție este mai mare.

Întrebări cu răspuns multiplu:

1. Selectează cea mai bună opțiune pentru a completa propoziția. Cea mai bună strategie pentru a folosi cu succes algoritmul lui Grover pe calculatoarele cuantice moderne este să iterezi operatorul Grover...

• a. O singură dată.
• b. Întotdeauna de $t$ ori, pentru a maximiza amplitudinea de probabilitate a stării (stărilor) soluție.
• c. Până la $t$ ori, deși un număr mai mic poate fi suficient pentru ca stările soluție să iasă în evidență.
• d. Niciodată mai puțin de 10 ori.

2. Mai jos este prezentat un circuit de interogare de fază care funcționează ca oracol pentru a marca o anumită stare cu o inversare de fază. Care dintre următoarele stări sunt marcate de acest circuit?

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

3. Presupune că vrei să cauți trei stări marcate dintr-un set de 128. Care este numărul optim de iterații ale operatorului Grover pentru a maximiza amplitudinile stărilor marcate?

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

Întrebări pentru discuție:

1. Ce alte probleme ai putea formula ca o căutare Grover? Gândește-te la probleme în care este dificil să găsești o soluție, dar ușor să o verifici.

2. Poți identifica probleme legate de scalarea algoritmului lui Grover pe calculatoarele cuantice moderne?