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.

Matematică

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 Gate-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 Gate-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 Gate-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 Gate-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 Gate-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.

Avertisment evident

Pentru a aplica algoritmul lui Grover, a trebuit să construim operatorul Grover, ceea ce înseamnă că trebuie să putem inversa faza stărilor care satisfac criteriile noastre de soluție. Acest lucru ridică întrebarea: dacă ne cunoaștem mulțimea soluțiilor atât de bine încât putem proiecta un Circuit cuantic să le eticheteze pe fiecare, ce mai căutăm?! Răspunsul este triplu, și vom reveni la el pe tot parcursul tutorialului:

(1) Aceste tipuri de algoritmi de interogare implică adesea două părți: una care deține oracolul ce stabilește criteriile de soluție, și alta care încearcă să ghicească/găsească o stare de soluție. Faptul că o persoană poate construi oracolul nu elimină necesitatea căutării.

(2) Există probleme pentru care este mai ușor să specifici un criteriu de soluție decât să găsești soluția. Cel mai cunoscut exemplu în acest sens este probabil identificarea factorilor primi ai numerelor mari. Algoritmul lui Grover nu este deosebit de eficient în rezolvarea acelei probleme specifice; am folosi algoritmul lui Shor pentru factorizarea primară. Acesta este doar un exemplu pentru a sublinia că a cunoaște criteriul privind comportamentul unei stări nu este întotdeauna același lucru cu a cunoaște starea.

(3) Algoritmul lui Grover nu returnează doar date clasice. Adevărat, dacă facem o măsurătoare a stării finale după $t$ repetări ale operatorului Grover, este probabil să obținem informații clasice care identifică starea de soluție. Dar ce se întâmplă dacă nu dorim informații clasice; ce se întâmplă dacă dorim o stare de soluție pregătită pe un calculator cuantic pentru utilizare ulterioară într-un alt algoritm? Algoritmul lui Grover produce de fapt o stare cuantică cu soluțiile puternic ponderate. Prin urmare, te poți aștepta să găsești algoritmul lui Grover ca subrutină în algoritmi cuantici mai complecși.

Având acestea în vedere, 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, și vom avansa spre exemple în care utilitatea algoritmului lui Grover devine mai clară.

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
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 Gate 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 Gate 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 argumentat mai sus, poate 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 poate fi obținut din această expresie:

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

Aici $A_1$ este numărul de soluții sau stări țintă. 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 Gate cu doi Qubiți ar produce numai zgomot dacă Qubiții nu ar fi extrem de performanți. Să vedem cum se comportă acestea.

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 Gate 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: Alt criteriu decât un șir de biți specific

Ca ilustrare finală a modului în care algoritmul lui Grover ar putea fi util în contextul unei subrutine, să ne imaginăm că avem nevoie de stări cuantice cu un anumit număr de 1-uri în reprezentarea prin șir de biți. Acest lucru este frecvent în situațiile în care sunt implicate legi de conservare. De exemplu, în contextul chimiei cuantice, se mapează adesea starea 1 a unui Qubit la ocuparea unui orbital electronic. Pentru ca sarcina să fie conservată, numărul total de 1-uri trebuie să rămână și el constant. Constrângerile de acest fel sunt atât de comune încât au un nume special: constrângeri de greutate Hamming, iar numărul de 1-uri din stare se numește greutate Hamming.

Pasul 1:

Să scriem mai întâi o funcție care marchează stările cu greutatea Hamming dorită. O vom scrie în mod general pentru un număr nespecificat de qubiți num_qubits și o greutate Hamming țintă 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']

De aici încolo, întregul proces este identic cu cel din activitățile anterioare. Pentru concizie, pașii din tiparele Qiskit sunt prezentați doar în comentariile codului.

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)

Algoritmul lui Grover a pregătit într-adevăr stările cu greutatea Hamming 2 astfel încât să fie mult mai probabil să fie măsurate decât orice alte stări — cu aproximativ un ordin de mărime mai probabile.

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.

Întrebări

Î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 condiții ai putea folosi într-un oracol cuantic? Gândește-te la condiții care sunt ușor de formulat sau de impus asupra unui șir de biți, dar care nu constau pur și simplu în enumerarea șirurilor de biți marcate.

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