Descrierea algoritmului lui Grover

În această secțiune, vom descrie algoritmul lui Grover. Vom începe prin a discuta despre porțile de interogare în fază și cum se construiesc, urmate de descrierea algoritmului lui Grover în sine. În final, vom discuta pe scurt cum acest algoritm se aplică în mod natural la căutare.

Porți de interogare în fază

Algoritmul lui Grover utilizează operații cunoscute sub numele de porți de interogare în fază. Spre deosebire de o poartă de interogare obișnuită $U_f,$ definită pentru o funcție dată $f$ în modul uzual descris anterior, o poartă de interogare în fază pentru funcția $f$ este definită ca

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

pentru orice șir $x\in\Sigma^n.$

Operația $Z_f$ poate fi implementată folosind o singură poartă de interogare $U_f$, așa cum sugerează această diagramă:

Această implementare utilizează fenomenul de retroacțiune de fază și necesită ca un qubit de spațiu de lucru, inițializat în starea $\vert -\rangle$, să fie disponibil. Acest qubit rămâne în starea $\vert - \rangle$ după finalizarea implementării și poate fi reutilizat (de exemplu, pentru a implementa porți $Z_f$ ulterioare) sau pur și simplu ignorat.

Pe lângă operația $Z_f,$ vom folosi și o poartă de interogare în fază pentru funcția OR pe $n$ biți, definită astfel pentru fiecare șir $x\in\Sigma^n.$

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

Explicit, poarta de interogare în fază pentru funcția OR pe $n$ biți operează astfel:

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

Spre a fi clar, acesta este modul în care $Z_{\mathrm{OR}}$ operează pe stările bazei standard; comportamentul său pe stări arbitrare este determinat din această expresie prin liniaritate.

Operația $Z_{\mathrm{OR}}$ poate fi implementată ca un Circuit cuantic începând cu un circuit boolean pentru funcția OR, construind apoi o operație $U_{\mathrm{OR}}$ (adică o poartă de interogare standard pentru funcția OR pe $n$ biți) folosind procedura descrisă în lecția Fundamente algoritmice cuantice, și în final o operație $Z_{\mathrm{OR}}$ folosind fenomenul de retroacțiune de fază descris mai sus. Observă că operația $Z_{\mathrm{OR}}$ nu depinde de funcția $f$ și, prin urmare, poate fi implementată printr-un Circuit cuantic fără nicio poartă de interogare.

Descrierea algoritmului

Acum că avem cele două operații $Z_f$ și $Z_{\mathrm{OR}},$ putem descrie algoritmul lui Grover.

Algoritmul se referă la un număr $t,$ care reprezintă numărul de iterații pe care le efectuează (și, prin urmare, numărul de interogări ale funcției $f$ pe care le necesită). Acest număr $t$ nu este specificat de algoritmul lui Grover, așa cum îl descriem, și vom discuta mai târziu în lecție cum poate fi ales.

Algoritmul lui Grover

1. Inițializează un registru de $n$ qubiți $\mathsf{Q}$ în starea all-zero $\vert 0^n \rangle$ și aplică apoi o operație Hadamard fiecărui qubit din $\mathsf{Q}.$
2. Aplică de $t$ ori operația unitară $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ registrului $\mathsf{Q}$
3. Măsoară qubiții din $\mathsf{Q}$ în raport cu măsurători ale bazei standard și returnează șirul rezultat.

Operația $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ iterată în pasul 2 va fi numită operația Grover pe parcursul restului acestei lecții. Iată o reprezentare ca Circuit cuantic a operației Grover când $n=7\!:$

În această diagramă, operația $Z_f$ este reprezentată ca fiind mai mare decât $Z_{\mathrm{OR}}$ ca indiciu vizual informal, sugerând că este probabil operația mai costisitoare. În special, atunci când lucrăm în modelul de interogare, $Z_f$ necesită o interogare, în timp ce $Z_{\mathrm{OR}}$ nu necesită nicio interogare. Dacă în schimb avem un circuit boolean pentru funcția $f$ și îl convertim într-un Circuit cuantic pentru $Z_f,$ ne putem aștepta în mod rezonabil că Circuitul cuantic rezultat va fi mai mare și mai complex decât unul pentru $Z_{\mathrm{OR}}.$

Iată o diagramă a unui Circuit cuantic pentru întregul algoritm când $n=7$ și $t=3.$ Pentru valori mai mari ale lui $t$ putem insera pur și simplu instanțe suplimentare ale operației Grover imediat înaintea măsurătorilor.

Aplicare la căutare

Algoritmul lui Grover poate fi aplicat problemei de Căutare astfel:

• Alege numărul $t$ în pasul 2. (Acest lucru este discutat mai târziu în lecție.)
• Rulează algoritmul lui Grover pe funcția $f,$ folosind orice alegere am făcut pentru $t,$ pentru a obține un șir $x\in\Sigma^n.$
• Interoghează funcția $f$ pe șirul $x$ pentru a vedea dacă este o soluție validă:
  • Dacă $f(x) = 1,$ atunci am găsit o soluție, deci putem opri și returna $x.$
  • Altfel, dacă $f(x) = 0,$ putem fie să rulăm procedura din nou, posibil cu o altă alegere pentru $t,$ fie să decidem să renunțăm și să returnăm „nicio soluție."

Odată ce am analizat cum funcționează algoritmul lui Grover, vom vedea că luând $t = O(\sqrt{N}),$ obținem o soluție la problema noastră de căutare (dacă există una) cu probabilitate mare.