Alegerea numărului de iterații

Am stabilit că vectorul de stare al registrului $\mathsf{Q}$ în algoritmul lui Grover rămâne în subspațiul bidimensional generat de $\vert A_0\rangle$ și $\vert A_1\rangle$ după ce pasul de inițializare a fost efectuat.

Scopul este de a găsi un element $x\in A_1$, și acest scop va fi atins dacă putem obține starea $\vert A_1\rangle$ — căci dacă măsurăm această stare, garantat obținem un rezultat al măsurătorii $x\in A_1$. Dat fiind că starea lui $\mathsf{Q}$ după $t$ iterații la pasul 2 este

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

ar trebui să alegem $t$ astfel încât

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

să fie cât mai aproape de $1$ în valoare absolută, pentru a maximiza probabilitatea de a obține $x\in A_1$ din măsurătoare. Pentru orice unghi $\theta \in (0,2\pi)$, valoarea $\sin((2t + 1)\theta)$ oscilează pe măsură ce $t$ crește, deși nu este neapărat periodică — nu există nicio garanție că vom obține vreodată aceeași valoare de două ori.

Desigur, pe lângă faptul că dorim ca probabilitatea de a obține un element $x\in A_1$ din măsurătoare să fie mare, am dori și ca $t$ să fie cât mai mic posibil, deoarece $t$ aplicări ale operației $G$ necesită $t$ interogări ale funcției $f$. Deoarece urmărim ca $\sin( (2t + 1) \theta)$ să fie aproape de $1$ în valoare absolută, o modalitate naturală de a face acest lucru este să alegem $t$ astfel încât

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

Rezolvând pentru $t$ obținem

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

Desigur, $t$ trebuie să fie un număr întreg, deci nu vom putea neapărat atinge exact această valoare — dar ceea ce putem face este să luăm cel mai apropiat număr întreg față de această valoare, care este

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

Acesta este numărul recomandat de iterații pentru algoritmul lui Grover. Pe măsură ce continuăm analiza, vom vedea că apropierea acestui număr întreg față de valoarea țintă afectează în mod natural performanța algoritmului.

(Ca o paranteză, dacă valoarea țintă $\pi/(4\theta) - 1/2$ se află exact la jumătatea distanței dintre două numere întregi, această expresie a lui $t$ este ceea ce obținem prin rotunjire în sus. Am putea, alternativ, să rotunjim în jos, ceea ce are sens deoarece înseamnă o interogare mai puțin — dar acest lucru este secundar și neimportant în scopul lecției.)

Amintind că valoarea unghiului $\theta$ este dată de formula

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

vedem că numărul recomandat de iterații $t$ depinde de numărul de șiruri din $A_1$. Aceasta prezintă o provocare dacă nu știm câte soluții avem, așa cum vom discuta mai târziu.

Căutare unică

Mai întâi, să ne concentrăm pe situația în care există un singur șir $x$ astfel încât $f(x)=1$. O altă modalitate de a spune acest lucru este că analizăm o instanță a problemei de căutare unică. În acest caz avem

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

care poate fi aproximat convenabil ca

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

când $N$ devine mare. Dacă substituim $\theta = 1/\sqrt{N}$ în expresia

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

obținem

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

Reamintindu-ne că $t$ nu este doar numărul de ori în care operația $G$ este efectuată, ci și numărul de interogări ale funcției $f$ necesare algoritmului, vedem că suntem pe cale să obținem un algoritm care necesită $O(\sqrt{N})$ interogări.

Acum vom investiga cât de bine funcționează alegerea recomandată a lui $t$. Probabilitatea ca măsurătoarea finală să rezulte în soluția unică poate fi exprimată explicit ca

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

Primul argument, $N,$ se referă la numărul de elemente peste care căutăm, iar al doilea argument, care este $1$ în acest caz, se referă la numărul de soluții. Puțin mai târziu vom folosi aceeași notație mai general, unde există mai multe soluții.

Iată un tabel al probabilităților de succes pentru valori crescătoare ale lui $N = 2^n$.

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

Observă că aceste probabilități nu sunt strict crescătoare. În special, avem o anomalie interesantă când $N=4$, unde obținem o soluție cu certitudine. Cu toate acestea, se poate demonstra în general că

$$p(N,1) \geq 1 - \frac{1}{N}$$

pentru toți $N$, deci probabilitatea de succes tinde spre $1$ în limită pe măsură ce $N$ devine mare, așa cum par să sugereze valorile de mai sus. Lucru bun!

Dar observă, totuși, că chiar și o margine slabă precum $p(N,1) \geq 1/2$ stabilește utilitatea algoritmului lui Grover. Oricare ar fi rezultatul măsurătorii $x$ obținut din rularea procedurii, putem verifica întotdeauna dacă $f(x) = 1$ folosind o singură interogare la $f$. Și dacă nu reușim să obținem șirul unic $x$ pentru care $f(x) = 1$ cu probabilitate de cel mult $1/2$ rulând procedura o singură dată, atunci după $m$ rulări independente ale procedurii nu vom fi reușit să obținem acest șir unic $x$ cu probabilitate de cel mult $2^{-m}$. Adică, folosind $O(m \sqrt{N})$ interogări la $f$, vom obține soluția unică $x$ cu probabilitate cel puțin $1 - 2^{-m}$. Folosind marginea mai bună $p(N,1) \geq 1 - 1/N$ se dezvăluie că probabilitatea de a găsi $x\in A_1$ folosind această metodă este de fapt cel puțin $1 - N^{-m}$.

Soluții multiple

Pe măsură ce numărul de elemente din $A_1$ variază, variază și unghiul $\theta$, ceea ce poate influența semnificativ probabilitatea de succes a algoritmului. Pentru simplitate, vom scrie $s = \vert A_1 \vert$ pentru a denota numărul de soluții, și, ca și înainte, vom presupune că $s\geq 1$.

Ca exemplu motivator, să ne imaginăm că avem $s = 4$ soluții în loc de o soluție unică, așa cum am considerat mai sus. Asta înseamnă că

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

care este aproximativ dublul unghiului pe care îl aveam în cazul $\vert A_1 \vert = 1$ când $N$ este mare. Să presupunem că nu știm mai bine și alegem aceeași valoare pentru $t$ ca în situația cu o soluție unică:

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

Efectul va fi catastrofal, după cum arată următorul tabel de probabilități.

$$\begin{array}{ll} N & \text{Probabilitate de succes}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

De data aceasta, probabilitatea de succes tinde la $0$ pe măsură ce $N$ tinde la infinit. Asta se întâmplă deoarece rotim efectiv de două ori mai repede decât am făcut-o când exista o soluție unică, astfel că ajungem să depășim ținta $\vert A_1\rangle$ și aterizăm lângă $-\vert A_0\rangle$.

Totuși, dacă folosim în schimb alegerea recomandată pentru $t$, care este

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

pentru

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

atunci performanța va fi mai bună. Mai precis, folosirea acestei alegeri pentru $t$ duce la succes cu probabilitate ridicată.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

Generalizând ce s-a afirmat anterior, se poate demonstra că

$$p(N,s) \geq 1 - \frac{s}{N},$$

unde folosim notația sugerată anterior: $p(N,s)$ denotă probabilitatea ca algoritmul lui Grover rulat pentru $t$ iterații să dezvăluie o soluție când există $s$ soluții în total din $N$ posibilități.

Această margine inferioară $1 - s/N$ a probabilității de succes este oarecum ciudată în sensul că mai multe soluții implică o margine inferioară mai slabă — dar în ipoteza că $s$ este semnificativ mai mic decât $N$, concluzionăm totuși că probabilitatea de succes este rezonabil de ridicată. Ca și înainte, simplul fapt că $p(N,s)$ este rezonabil de mare implică utilitatea algoritmului.

Se întâmplă, de asemenea, că

$$p(N,s) \geq \frac{s}{N}.$$

Această margine inferioară descrie probabilitatea ca un șir $x\in\Sigma^n$ selectat uniform aleator să fie o soluție — deci algoritmul lui Grover se descurcă întotdeauna cel puțin la fel de bine ca ghicitul aleator. (De fapt, când $t=0$, algoritmul lui Grover este ghicit aleator.)

Acum să aruncăm o privire la numărul de iterații (și deci numărul de interogări)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

pentru

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

Pentru orice $\alpha \in [0,1]$, este adevărat că $\sin^{-1}(\alpha)\geq \alpha$, și deci

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

Asta implică că

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

Asta se traduce printr-o economie la numărul de interogări pe măsură ce $s$ crește. În particular, numărul de interogări necesar este

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

Număr necunoscut de soluții

Dacă numărul de soluții $s = \vert A_1 \vert$ este necunoscut, atunci este necesară o abordare diferită, deoarece în această situație nu avem nicio informație despre $s$ pentru a ne ghida alegerea lui $t$. Există, de fapt, mai multe abordări.

O abordare simplă este să alegem

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

uniform aleator. Alegând $t$ în acest mod, se găsește întotdeauna o soluție (presupunând că există una) cu probabilitate mai mare de 40%, deși acest lucru nu este evident și necesită o analiză care nu va fi inclusă aici. Are, totuși, sens, mai ales când ne gândim la imaginea geometrică: rotirea stării lui $\mathsf{Q}$ de un număr aleator de ori în acest fel nu este diferită de alegerea unui vector unitar aleator în spațiul generat de $\vert A_0\rangle$ și $\vert A_1\rangle$, pentru care este probabil ca coeficientul lui $\vert A_1\rangle$ să fie rezonabil de mare. Repetând această procedură și verificând rezultatul în același mod ca cel descris anterior, probabilitatea de a găsi o soluție poate fi adusă foarte aproape de $1$.

Există o metodă rafinată care găsește o soluție când una există folosind $O(\sqrt{N/s})$ interogări, chiar și atunci când numărul de soluții $s$ nu este cunoscut, și necesită $O(\sqrt{N})$ interogări pentru a determina că nu există soluții când $s=0$.

Ideea de bază este de a alege $t$ uniform aleator din mulțimea $\{1,\ldots,T\}$ în mod iterativ, pentru valori crescătoare ale lui $T$. În particular, putem începe cu $T = 1$ și îl creștem exponențial, terminând întotdeauna procesul imediat ce se găsește o soluție și limitând $T$ pentru a nu irosi interogări când nu există o soluție. Procesul valorifică faptul că sunt necesare mai puține interogări când există mai multe soluții. Este necesară totuși o oarecare atenție pentru a echilibra rata de creștere a lui $T$ cu probabilitatea de succes pentru fiecare iterație. (De exemplu, $T \leftarrow \lceil \frac{5}{4}T\rceil$ funcționează, după cum arată o analiză. Dublarea lui $T$, însă, nu funcționează — aceasta se dovedește a fi o creștere prea rapidă.)

Cazurile triviale

Pe parcursul analizei prin care tocmai am trecut, am presupus că numărul de soluții este nenul. Într-adevăr, referindu-ne la vectorii

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

am presupus implicit că $A_0$ și $A_1$ sunt ambele nevide. Aici vom analiza pe scurt ce se întâmplă când una dintre aceste mulțimi este vidă.

Înainte de a ne apuca de analiză, să observăm evidentul: dacă fiecare șir $x\in\Sigma^n$ este o soluție, atunci vom vedea o soluție când măsurăm; și când nu există nicio soluție, nu vom vedea una. Într-un anume sens, nu este nevoie să mergem mai adânc de atât.

Putem, totuși, să verificăm rapid matematica pentru aceste cazuri triviale. Situația în care una dintre $A_0$ și $A_1$ este vidă apare când $f$ este constantă; $A_1$ este vidă când $f(x) = 0$ pentru orice $x\in\Sigma^n,$ și $A_0$ este vidă când $f(x) = 1$ pentru orice $x\in\Sigma^n.$ Asta înseamnă că

$$Z_f \vert u\rangle = \pm \vert u\rangle,$$

și deci

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

Deci, indiferent de numărul de iterații $t$ pe care le efectuăm în aceste cazuri, măsurătorile vor dezvălui întotdeauna un șir uniform aleator $x\in\Sigma^n$.