Wybór liczby iteracji

Ustaliliśmy, że wektor stanu rejestru $\mathsf{Q}$ w algorytmie Grovera pozostaje w dwuwymiarowej podprzestrzeni rozpiętej przez $\vert A_0\rangle$ i $\vert A_1\rangle$, gdy tylko wykonany zostanie krok inicjalizacji.

Celem jest znalezienie elementu $x\in A_1$, i cel ten zostanie osiągnięty, jeśli uda się nam uzyskać stan $\vert A_1\rangle$ — bowiem jeśli zmierzymy ten stan, mamy gwarancję uzyskania wyniku pomiaru $x\in A_1$. Ponieważ stan $\mathsf{Q}$ po $t$ iteracjach w kroku 2 wynosi

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

powinniśmy wybrać $t$ tak, aby

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

był jak najbliższy $1$ pod względem wartości bezwzględnej, aby zmaksymalizować prawdopodobieństwo uzyskania $x\in A_1$ z pomiaru. Dla dowolnego kąta $\theta \in (0,2\pi)$, wartość $\sin((2t + 1)\theta)$ oscyluje wraz ze wzrostem $t$, choć niekoniecznie w sposób okresowy — nie ma gwarancji, że kiedykolwiek uzyskamy tę samą wartość dwukrotnie.

Oczywiście, oprócz tego, że chcemy, aby prawdopodobieństwo uzyskania elementu $x\in A_1$ z pomiaru było duże, chcemy też wybrać $t$ tak małe, jak to możliwe, ponieważ $t$ zastosowań operacji $G$ wymaga $t$ zapytań (query) do funkcji $f$. Ponieważ chcemy, aby $\sin( (2t + 1) \theta)$ był bliski $1$ pod względem wartości bezwzględnej, naturalnym sposobem na to jest wybranie $t$ tak, aby

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

Rozwiązując ze względu na $t$ otrzymujemy

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

Oczywiście $t$ musi być liczbą całkowitą, więc niekoniecznie uda się nam trafić dokładnie w tę wartość — możemy jednak wziąć najbliższą liczbę całkowitą do tej wartości, czyli

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

To jest zalecana liczba iteracji algorytmu Grovera. W miarę postępu analizy zobaczymy, że bliskość tej liczby całkowitej do wartości docelowej naturalnie wpływa na wydajność algorytmu.

(Na marginesie: jeśli wartość docelowa $\pi/(4\theta) - 1/2$ wypada dokładnie w połowie między dwiema liczbami całkowitymi, to powyższy wzór na $t$ odpowiada zaokrągleniu w górę. Można alternatywnie zaokrąglić w dół, co ma sens, ponieważ oznacza o jedno zapytanie (query) mniej — ale to kwestia drugorzędna i nieistotna dla celów tej lekcji.)

Przypominając, że wartość kąta $\theta$ wyraża się wzorem

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

widzimy, że zalecana liczba iteracji $t$ zależy od liczby ciągów w $A_1$. Stanowi to wyzwanie, gdy nie wiemy, ile mamy rozwiązań, co omówimy później.

Unikatowe przeszukiwanie

Najpierw skupmy się na sytuacji, w której istnieje jeden ciąg $x$ taki, że $f(x)=1$. Inaczej mówiąc, rozważamy instancję problemu Unique search. W tym przypadku mamy

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

co można wygodnie przybliżyć jako

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

gdy $N$ jest duże. Jeśli podstawimy $\theta = 1/\sqrt{N}$ do wyrażenia

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

otrzymujemy

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

Przypominając, że $t$ jest nie tylko liczbą wykonań operacji $G$, lecz także liczbą zapytań (query) do funkcji $f$ wymaganych przez algorytm, widzimy, że jesteśmy na dobrej drodze do uzyskania algorytmu wymagającego $O(\sqrt{N})$ zapytań.

Teraz zbadamy, jak dobrze działa zalecany wybór $t$. Prawdopodobieństwo, że końcowy pomiar da unikatowe rozwiązanie, można wyrazić wprost jako

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

Pierwszy argument, $N,$ odnosi się do liczby elementów, po których przeszukujemy, a drugi argument, równy $1$ w tym przypadku, odnosi się do liczby rozwiązań. Nieco dalej użyjemy tego samego zapisu w sposób ogólniejszy, gdy istnieje wiele rozwiązań.

Oto tabela prawdopodobieństw sukcesu dla rosnących wartości $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}$$

Zauważ, że te prawdopodobieństwa nie są ściśle rosnące. W szczególności mamy ciekawą anomalię dla $N=4$, gdzie z pewnością uzyskujemy rozwiązanie. Można jednak udowodnić w ogólności, że

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

dla wszystkich $N$, a zatem prawdopodobieństwo sukcesu dąży do $1$ w granicy, gdy $N$ rośnie, co zdają się sugerować powyższe wartości. To dobra wiadomość!

Zauważ jednak, że nawet słabe ograniczenie $p(N,1) \geq 1/2$ dowodzi użyteczności algorytmu Grovera. Dla jakiegokolwiek wyniku pomiaru $x$ uzyskanego po uruchomieniu procedury zawsze możemy sprawdzić, czy $f(x) = 1$, używając jednego zapytania (query) do $f$. A jeśli nie uda nam się uzyskać unikatowego ciągu $x$, dla którego $f(x) = 1$, z prawdopodobieństwem co najwyżej $1/2$ przy jednokrotnym uruchomieniu procedury, to po $m$ niezależnych uruchomieniach nie uda nam się uzyskać tego unikatowego ciągu $x$ z prawdopodobieństwem co najwyżej $2^{-m}$. To znaczy, używając $O(m \sqrt{N})$ zapytań (query) do $f$, uzyskamy unikatowe rozwiązanie $x$ z prawdopodobieństwem co najmniej $1 - 2^{-m}$. Stosując lepsze ograniczenie $p(N,1) \geq 1 - 1/N$, okazuje się, że prawdopodobieństwo znalezienia $x\in A_1$ tą metodą wynosi faktycznie co najmniej $1 - N^{-m}$.

Wiele rozwiązań

Wraz ze zmianą liczby elementów w $A_1$ zmienia się też kąt $\theta$, co może mieć istotny wpływ na prawdopodobieństwo sukcesu algorytmu. Dla zwięzłości zapiszmy $s = \vert A_1 \vert$, oznaczając w ten sposób liczbę rozwiązań, i tak jak wcześniej założymy, że $s\geq 1$.

Jako motywujący przykład wyobraź sobie, że mamy $s = 4$ rozwiązania zamiast jednego, jak rozważaliśmy powyżej. Oznacza to, że

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

co jest w przybliżeniu dwukrotnie większym kątem niż w przypadku $\vert A_1 \vert = 1$ dla dużych $N.$ Załóżmy, że nie wiemy nic lepszego i wybieramy tę samą wartość $t$ co w przypadku jedynego rozwiązania:

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

Efekt będzie katastrofalny, jak pokazuje poniższa tabela prawdopodobieństw.

$$\begin{array}{ll} N & \text{Success probability}\\ \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}$$

Tym razem prawdopodobieństwo sukcesu dąży do $0$ gdy $N$ dąży do nieskończoności. Dzieje się tak dlatego, że efektywnie obracamy się dwa razy szybciej niż w przypadku jedynego rozwiązania, więc przelatujemy obok celu $\vert A_1\rangle$ i lądujemy w pobliżu $-\vert A_0\rangle$.

Jednak jeśli zamiast tego użyjemy zalecanego wyboru $t$, którym jest

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

dla

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

to wyniki będą lepsze. Mówiąc dokładniej, ten wybór $t$ prowadzi do sukcesu z wysokim prawdopodobieństwem.

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

Uogólniając to, co zostało stwierdzone wcześniej, można udowodnić, że

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

gdzie używamy wcześniej zasugerowanego oznaczenia: $p(N,s)$ oznacza prawdopodobieństwo, że algorytm Grovera wykonany przez $t$ iteracji ujawnia rozwiązanie, gdy łącznie jest $s$ rozwiązań spośród $N$ możliwości.

To dolne ograniczenie $1 - s/N$ na prawdopodobieństwo sukcesu jest nieco osobliwe — większa liczba rozwiązań implikuje gorsze dolne ograniczenie — ale przy założeniu, że $s$ jest znacząco mniejsze od $N$, mimo wszystko wnioskujemy, że prawdopodobieństwo sukcesu jest rozsądnie wysokie. Tak jak wcześniej, sam fakt, że $p(N,s)$ jest rozsądnie duże, implikuje użyteczność algorytmu.

Zachodzi też

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

To dolne ograniczenie opisuje prawdopodobieństwo, że losowo wybrany ciąg $x\in\Sigma^n$ jest rozwiązaniem — zatem algorytm Grovera zawsze radzi sobie co najmniej tak dobrze jak losowe zgadywanie. (W rzeczywistości, gdy $t=0$, algorytm Grovera jest losowym zgadywaniem.)

Przyjrzyjmy się teraz liczbie iteracji (a co za tym idzie liczbie zapytań)

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

dla

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

Dla każdego $\alpha \in [0,1]$ zachodzi $\sin^{-1}(\alpha)\geq \alpha$, a zatem

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

Wynika z tego, że

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

Przekłada się to na oszczędność liczby zapytań wraz ze wzrostem $s.$ W szczególności wymagana liczba zapytań wynosi

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

Nieznana liczba rozwiązań

Jeśli liczba rozwiązań $s = \vert A_1 \vert$ jest nieznana, wymagane jest inne podejście — w tej sytuacji nie mamy wiedzy o $s$, która mogłaby pokierować wyborem $t$. Istnieje w rzeczywistości kilka różnych podejść.

Jedno proste podejście polega na wyborze

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

jednostajnie losowo. Wybór $t$ w ten sposób zawsze daje rozwiązanie (przy założeniu, że ono istnieje) z prawdopodobieństwem większym niż 40%, choć nie jest to oczywiste i wymaga analizy, której tutaj nie będziemy przeprowadzać. Ma to jednak sens, zwłaszcza gdy pomyślimy o geometrycznym obrazku: losowe obracanie stanu $\mathsf{Q}$ o pewną liczbę razy jest podobne do wyboru losowego wektora jednostkowego w przestrzeni rozpiętej przez $\vert A_0\rangle$ i $\vert A_1\rangle$, dla którego jest bardzo prawdopodobne, że współczynnik przy $\vert A_1\rangle$ będzie odpowiednio duży. Powtarzając tę procedurę i sprawdzając wynik w ten sam sposób, co opisano wcześniej, prawdopodobieństwo znalezienia rozwiązania można zbliżyć bardzo blisko do $1$.

Istnieje też bardziej wyrafinowana metoda, która — gdy rozwiązanie istnieje — znajdzie je, wykonując $O(\sqrt{N/s})$ zapytań, nawet gdy liczba rozwiązań $s$ nie jest znana, i wymaga $O(\sqrt{N})$ zapytań, aby stwierdzić brak rozwiązań w przypadku $s=0$.

Podstawowy pomysł polega na iteracyjnym wyborze $t$ jednostajnie losowo ze zbioru $\{1,\ldots,T\}$ dla rosnących wartości $T$. W szczególności możemy zacząć od $T = 1$ i zwiększać go wykładniczo, zawsze kończąc proces natychmiast po znalezieniu rozwiązania oraz ograniczając $T$ tak, by nie marnować zapytań, gdy rozwiązania nie ma. Proces ten wykorzystuje fakt, że im więcej rozwiązań istnieje, tym mniej zapytań jest potrzebnych. Konieczna jest jednak pewna ostrożność, aby zbalansować tempo wzrostu $T$ z prawdopodobieństwem sukcesu dla każdej iteracji. (Działające podejście to np$.T \leftarrow \lceil \frac{5}{4}T\rceil$, co potwierdza odpowiednia analiza. Podwajanie $T$ jednak nie działa — okazuje się, że to zbyt szybki wzrost.)

Przypadki trywialne

Przez całą przeprowadzoną właśnie analizę zakładaliśmy, że liczba rozwiązań jest niezerowa. Rzeczywiście, odwołując się do wektorów

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

milcząco zakładaliśmy, że $A_0$ i $A_1$ są oba niepuste. Poniżej krótko rozważymy, co się dzieje, gdy jeden z tych zbiorów jest pusty.

Zanim zagłębimy się w analizę, zauważmy to, co oczywiste: jeśli każdy ciąg $x\in\Sigma^n$ jest rozwiązaniem, to przy pomiarze zobaczymy rozwiązanie; a gdy nie ma żadnych rozwiązań, nie zobaczymy żadnego. W pewnym sensie nie ma potrzeby wchodzić głębiej.

Możemy jednak szybko zweryfikować matematykę dla tych trywialnych przypadków. Sytuacja, w której jeden ze zbiorów $A_0$ i $A_1$ jest pusty, zachodzi wtedy, gdy $f$ jest stałe; $A_1$ jest pusty, gdy $f(x) = 0$ dla każdego $x\in\Sigma^n,$ natomiast $A_0$ jest pusty, gdy $f(x) = 1$ dla każdego $x\in\Sigma^n.$ Oznacza to, że

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

a zatem

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

Zatem, niezależnie od liczby iteracji $t$, które wykonujemy w tych przypadkach, pomiary zawsze ujawnią losowy ciąg $x\in\Sigma^n$.