Analiză

Acum vom analiza algoritmul lui Grover pentru a înțelege cum funcționează. Vom începe cu ceea ce s-ar putea descrie ca o analiză simbolică, în care calculăm cum acționează operația Grover $G$ asupra anumitor stări, după care vom lega această analiză simbolică de o imagine geometrică ce ajută la vizualizarea modului în care funcționează algoritmul.

Soluții și non-soluții

Să începem prin definirea a două mulțimi de șiruri.

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

Mulțimea $A_1$ conține toate soluțiile problemei noastre de căutare, iar $A_0$ conține șirurile care nu sunt soluții (pe care le putem numi non-soluții atunci când este convenabil). Aceste două mulțimi satisfac $A_0 \cap A_1 = \varnothing$ și $A_0 \cup A_1 = \Sigma^n$, adică formează o bipartiție a lui $\Sigma^n$.

Vom defini în continuare doi vectori unitari care reprezintă superpozițiile uniforme peste mulțimile de soluții și non-soluții.

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

Formal vorbind, fiecare dintre acești vectori este definit doar când mulțimea corespunzătoare este nevidă, dar de acum înainte ne vom concentra pe cazul în care nici $A_0$ nici $A_1$ nu sunt vide. Cazurile $A_0 = \varnothing$ și $A_1 = \varnothing$ se tratează ușor separat, și le vom aborda mai târziu.

Ca notă, notația folosită aici este comună: ori de câte ori avem o mulțime finită și nevidă $S$, putem scrie $\vert S\rangle$ pentru a denota vectorul de stare cuantică uniform distribuit peste elementele lui $S$.

Să definim și $\vert u \rangle$ ca starea cuantică uniformă peste toate șirurile de $n$ biți:

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

Observă că

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

Avem de asemenea că $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle$, deci $\vert u\rangle$ reprezintă starea registrului $\mathsf{Q}$ după inițializarea din pasul 1 al algoritmului lui Grover.

Aceasta implică faptul că, chiar înainte ca iterațiile lui $G$ să aibă loc în pasul 2, starea lui $\mathsf{Q}$ este conținută în spațiul vectorial bidimensional generat de $\vert A_0\rangle$ și $\vert A_1\rangle$, iar coeficienții acestor vectori sunt numere reale. Așa cum vom vedea, starea lui $\mathsf{Q}$ va păstra întotdeauna aceste proprietăți — adică starea este o combinație liniară reală a lui $\vert A_0\rangle$ și $\vert A_1\rangle$ — după orice număr de iterații ale operației $G$ din pasul 2.

O observație despre operația Grover

Ne vom îndrepta acum atenția spre operația Grover

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

începând cu o observație interesantă despre aceasta.

Imaginează-ți pentru un moment că am înlocui funcția $f$ cu compoziția lui $f$ cu funcția NOT — sau, cu alte cuvinte, funcția obținută prin negarea bitului de ieșire al lui $f$. Vom numi această funcție nouă $g$ și o putem exprima în simboluri în câteva moduri alternative.

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

Observă că

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

pentru orice șir $x\in\Sigma^n$, și prin urmare

$$Z_g = - Z_f.$$

Aceasta înseamnă că, dacă am substitui funcția $f$ cu funcția $g$, algoritmul lui Grover nu ar funcționa diferit — deoarece stările obținute din algoritm în cele două cazuri sunt în mod necesar echivalente la o fază globală.

Aceasta nu este o problemă! Intuitiv vorbind, algoritmului nu îi pasă care șiruri sunt soluții și care nu — trebuie doar să poată distinge soluțiile de non-soluții pentru a funcționa corect.

Acțiunea operației Grover

Acum să analizăm acțiunea lui $G$ asupra vectorilor de stare cuantică $\vert A_0\rangle$ și $\vert A_1\rangle$.

Mai întâi, să observăm că operația $Z_f$ are o acțiune foarte simplă asupra lui $\vert A_0\rangle$ și $\vert A_1\rangle$.

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

În al doilea rând, avem operația $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$. Operația $Z_{\mathrm{OR}}$ este definită ca

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

din nou pentru orice șir $x\in\Sigma^n$, iar o modalitate alternativă convenabilă de a exprima această operație este următoarea:

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

O modalitate simplă de a verifica că această expresie este în concordanță cu definiția lui $Z_{\mathrm{OR}}$ este să evaluăm acțiunea sa asupra stărilor din baza standard.

Operația $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ poate fi astfel scrisă:

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

folosind aceeași notație, $\vert u \rangle,$ pe care am folosit-o mai sus pentru superpozița uniformă peste toate șirurile de $n$ biți.

Acum avem tot ce ne trebuie pentru a calcula acțiunea lui $G$ asupra lui $\vert A_0\rangle$ și $\vert A_1\rangle$. Să calculăm mai întâi acțiunea lui $G$ asupra lui $\vert A_0\rangle$.

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

În al doilea rând, să calculăm acțiunea lui $G$ asupra lui $\vert A_1\rangle$.

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

În ambele cazuri folosim ecuația

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

împreună cu expresiile

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{și}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

care rezultă din aceasta.

Pe scurt, avem

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

Așa cum am notat deja, starea lui $\mathsf{Q}$ imediat înainte de pasul 2 este conținută în spațiul bidimensional generat de $\vert A_0\rangle$ și $\vert A_1\rangle$, și tocmai am stabilit că $G$ mapează orice vector din acest spațiu la un alt vector din același spațiu. Aceasta înseamnă că, în scopul analizei, ne putem concentra atenția exclusiv pe acest subspațiu.

Pentru a înțelege mai bine ce se întâmplă în cadrul acestui spațiu bidimensional, să exprimăm acțiunea lui $G$ pe acest spațiu ca o matrice,

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

ale cărei prime și a doua rânduri/coloane corespund respectiv lui $\vert A_0\rangle$ și $\vert A_1\rangle$. Până acum în această serie, am conectat întotdeauna rândurile și coloanele matricelor cu stările clasice ale unui sistem, dar matricele pot fi folosite și pentru a descrie acțiunile aplicațiilor liniare pe baze diferite, cum avem aici.

Deși nu este deloc evident la prima vedere, matricea $M$ este ceea ce obținem prin ridicarea la pătrat a unei matrice cu aspect mai simplu.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

Matricea

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

este o matrice de rotație, pe care o putem exprima alternativ ca

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

for

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr).$$

Acest unghi $\theta$ va juca un rol foarte important în analiza care urmează, deci merită subliniată importanța sa aici, când îl vedem pentru prima dată.

În lumina acestei exprimări a acestei matrice, observăm că

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

Acest lucru se întâmplă deoarece rotirea cu unghiul $\theta$ de două ori este echivalentă cu rotirea cu unghiul $2\theta$. O altă modalitate de a vedea acest lucru este să folosim expresia alternativă

$$\theta = \cos^{-1}\biggl(\sqrt{\frac{\vert A_0\vert}{N}}\biggr),$$

împreună cu formulele de unghi dublu din trigonometrie:

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

În concluzie, starea registrului $\mathsf{Q}$ la începutul pasului 2 este

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

iar efectul aplicării $G$ asupra acestei stări este de a o roti cu un unghi $2\theta$ în spațiul generat de $\vert A_0\rangle$ și $\vert A_1\rangle$. Astfel, de exemplu, avem

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

și în general

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle.$$

Imaginea geometrică

Acum să conectăm analiza prin care tocmai am trecut la o imagine geometrică. Ideea este că operația $G$ este produsul a două reflecții, $Z_f$ și $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ Iar efectul net al compunerii a două reflecții este de a efectua o rotație.

Să începem cu $Z_f$. Așa cum am observat deja anterior, avem

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

În spațiul vectorial bidimensional generat de $\vert A_0\rangle$ și $\vert A_1\rangle$, aceasta este o reflecție față de dreapta paralelă cu $\vert A_0\rangle$, pe care o vom numi $L_1$. Iată o figură care ilustrează acțiunea acestei reflecții asupra unui vector unitar ipotetic $\vert\psi\rangle$, pe care îl presupunem a fi o combinație liniară reală a lui $\vert A_0\rangle$ și $\vert A_1\rangle$.

În al doilea rând, avem operația $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$, pe care am văzut deja că o putem scrie ca

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

Aceasta este tot o reflecție, de data aceasta față de dreapta $L_2$ paralelă cu vectorul $\vert u\rangle$. Iată o figură care descrie acțiunea acestei reflecții asupra unui vector unitar $\vert\psi\rangle$.

Când compunem aceste două reflecții, obținem o rotație — cu dublul unghiului dintre dreptele de reflecție — după cum ilustrează această figură.

Aceasta explică, în termeni geometrici, de ce efectul operației Grover este de a roti combinațiile liniare ale lui $\vert A_0\rangle$ și $\vert A_1\rangle$ cu un unghi de $2\theta$.