Analiza

Teraz przeanalizujemy algorytm Grovera, aby zrozumieć, jak działa. Zaczniemy od tego, co można określić jako analizę symboliczną, w której obliczamy, jak operacja Grovera $G$ działa na pewne stany, a następnie powiążemy tę analizę symboliczną z geometrycznym obrazem, który pomaga wizualizować działanie algorytmu.

Rozwiązania i nierozwiązania

Zacznijmy od zdefiniowania dwóch zbiorów ciągów.

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

Zbiór $A_1$ zawiera wszystkie rozwiązania naszego problemu wyszukiwania, natomiast $A_0$ zawiera ciągi, które rozwiązaniami nie są (które możemy dla wygody nazywać nierozwiązaniami). Te dwa zbiory spełniają warunki $A_0 \cap A_1 = \varnothing$ i $A_0 \cup A_1 = \Sigma^n,$ czyli tworzą bipartycję $\Sigma^n.$

Następnie zdefiniujemy dwa wektory jednostkowe reprezentujące jednorodne superpozycje nad zbiorami rozwiązań i nierozwiązań.

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

Formalnie rzecz biorąc, każdy z tych wektorów jest zdefiniowany wyłącznie wtedy, gdy odpowiadający mu zbiór jest niepusty, ale od tej chwili skupimy się na przypadku, gdy ani $A_0$, ani $A_1$ nie jest pusty. Przypadki $A_0 = \varnothing$ oraz $A_1 = \varnothing$ można łatwo obsłużyć oddzielnie i zrobimy to później.

Na marginesie: używana tu notacja jest powszechna — ilekroć mamy skończony i niepusty zbiór $S,$ możemy napisać $\vert S\rangle$, żeby oznaczyć wektor stanu kwantowego jednorodnego na elementach $S.$

Zdefiniujmy też $\vert u \rangle$ jako jednorodny stan kwantowy nad wszystkimi $n$-bitowymi ciągami:

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

Zauważ, że

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

Mamy również $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle,$ więc $\vert u\rangle$ reprezentuje stan rejestru $\mathsf{Q}$ po inicjalizacji w kroku 1 algorytmu Grovera.

Wynika z tego, że tuż przed iteracjami $G$ w kroku 2 stan rejestru $\mathsf{Q}$ należy do dwuwymiarowej przestrzeni wektorowej rozpiętej przez $\vert A_0\rangle$ i $\vert A_1\rangle$, przy czym współczynniki przy tych wektorach są liczbami rzeczywistymi. Jak zobaczymy, stan rejestru $\mathsf{Q}$ będzie zawsze miał te właściwości — tzn. będzie rzeczywistą kombinacją liniową $\vert A_0\rangle$ i $\vert A_1\rangle$ — po dowolnej liczbie iteracji operacji $G$ w kroku 2.

An observation about the Grover operation

Teraz skupimy się na operacji Grovera

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

zaczynając od ciekawej obserwacji na jej temat.

Wyobraź sobie na chwilę, że zastąpiliśmy funkcję $f$ złożeniem $f$ z funkcją NOT — czyli innymi słowy, funkcją otrzymaną przez odwrócenie bitu wyjściowego $f.$ Nazwiemy tę nową funkcję $g,$ i możemy ją wyrazić symbolicznie na kilka równoważnych sposobów.

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

Zauważmy, że

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

dla każdego ciągu $x\in\Sigma^n,$ a zatem

$$Z_g = - Z_f.$$

Oznacza to, że gdybyśmy podstawili funkcję $g$ w miejsce funkcji $f,$ algorytm Grovera działałby dokładnie tak samo — ponieważ stany uzyskiwane przez algorytm w obu przypadkach są z konieczności równoważne z dokładnością do globalnej fazy.

To nie jest problem! Intuicyjnie rzecz ujmując, algorytm nie dba o to, które ciągi są rozwiązaniami, a które nie — wystarczy mu jedynie umieć odróżniać rozwiązania od nierozwiązań, aby działać poprawnie.

Działanie operacji Grover

Rozważmy teraz działanie $G$ na wektorach stanu kwantowego $\vert A_0\rangle$ i $\vert A_1\rangle.$

Zacznijmy od obserwacji, że operacja $Z_f$ działa bardzo prosto na $\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}$$

Po drugie, mamy operację $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ Operacja $Z_{\mathrm{OR}}$ jest zdefiniowana jako

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

ponownie dla każdego ciągu $x\in\Sigma^n,$ a wygodny alternatywny sposób wyrażenia tej operacji wygląda następująco:

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

Prosty sposób na zweryfikowanie, że to wyrażenie zgadza się z definicją $Z_{\mathrm{OR}},$ to obliczenie jego działania na stanach bazy standardowej.

Operację $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ można zatem zapisać w następujący sposób:

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

używając tej samej notacji $\vert u \rangle,$ której użyliśmy powyżej dla jednolitej superpozycji po wszystkich $n$-bitowych ciągach.

Mamy teraz wszystko, czego potrzebujemy, by obliczyć działanie $G$ na $\vert A_0\rangle$ i $\vert A_1\rangle.$ Obliczmy najpierw działanie $G$ na $\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}$$

A po drugie, obliczmy działanie $G$ na $\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}$$

W obu przypadkach korzystamy z równania

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

oraz wynikających z niego wyrażeń

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

Podsumowując, mamy

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

Jak już zauważyliśmy, stan $\mathsf{Q}$ tuż przed krokiem 2 zawiera się w dwuwymiarowej przestrzeni rozpiętej przez $\vert A_0\rangle$ i $\vert A_1\rangle,$ a właśnie wykazaliśmy, że $G$ odwzorowuje każdy wektor z tej przestrzeni na inny wektor w tej samej przestrzeni. Oznacza to, że na potrzeby analizy możemy skupić uwagę wyłącznie na tej podprzestrzeni.

Aby lepiej zrozumieć, co dzieje się w tej dwuwymiarowej przestrzeni, wyrażmy działanie $G$ na tej przestrzeni jako macierz,

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

której pierwszy i drugi wiersz/kolumna odpowiadają odpowiednio $\vert A_0\rangle$ i $\vert A_1\rangle.$ Do tej pory w tej serii zawsze łączyliśmy wiersze i kolumny macierzy ze stanami klasycznymi układu, ale macierzy można też używać do opisywania działań odwzorowań liniowych na różnych bazach — tak jak tutaj.

Choć na pierwszy rzut oka wcale nie jest to oczywiste, macierz $M$ otrzymujemy, podnosząc do kwadratu prostszą macierz.

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

Macierz

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

jest macierzą obrotu, którą możemy alternatywnie zapisać jako

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

dla

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

Ten kąt $\theta$ odegra bardzo ważną rolę w dalszej analizie, dlatego warto podkreślić jego znaczenie już teraz, gdy widzimy go po raz pierwszy.

Mając to wyrażenie macierzy przed oczami, obserwujemy, że

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

Wynika to z faktu, że dwukrotne obrócenie o kąt $\theta$ jest równoważne obrotowi o kąt $2\theta.$ Innym sposobem, by to zobaczyć, jest skorzystanie z alternatywnego wyrażenia

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

wraz z formułami na kąt podwojony z trygonometrii:

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

Podsumowując, stan rejestru $\mathsf{Q}$ na początku kroku 2 wynosi

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

a efekt zastosowania $G$ do tego stanu polega na obróceniu go o kąt $2\theta$ w przestrzeni rozpiętej przez $\vert A_0\rangle$ i $\vert A_1\rangle.$ Mamy więc na przykład

$$\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 ogólnie

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

Geometric picture

Teraz połączmy analizę, którą właśnie przeprowadziliśmy, z obrazem geometrycznym. Chodzi o to, że operacja $G$ jest iloczynem dwóch odbić, $Z_f$ i $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ A efektem złożenia dwóch odbić jest wykonanie obrotu.

Zacznijmy od $Z_f.$ Jak już wcześniej zauważyliśmy, mamy

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

W dwuwymiarowej przestrzeni wektorowej rozpiętej przez $\vert A_0\rangle$ i $\vert A_1\rangle,$ jest to odbicie względem prostej równoległej do $\vert A_0\rangle,$ którą nazwiemy $L_1.$ Oto rysunek ilustrujący działanie tego odbicia na hipotetyczny wektor jednostkowy $\vert\psi\rangle,$ który zakładamy jest rzeczywistą kombinacją liniową $\vert A_0\rangle$ i $\vert A_1\rangle.$

Następnie mamy operację $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$ którą już widzieliśmy i którą można zapisać jako

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

Jest to również odbicie, tym razem względem prostej $L_2$ równoległej do wektora $\vert u\rangle.$ Oto rysunek przedstawiający działanie tego odbicia na wektor jednostkowy $\vert\psi\rangle.$

Gdy złożymy te dwa odbicia, otrzymamy obrót — o dwukrotność kąta między prostymi odbicia — co ilustruje ten rysunek.