Analýza

Nyní provedeme analýzu Groverova algoritmu, abychom pochopili, jak funguje. Začneme tím, co by se dalo popsat jako symbolická analýza, kde vypočítáme, jak Groverova operace $G$ působí na určité stavy, a poté tuto symbolickou analýzu propojíme s geometrickým obrázkem, který je užitečný pro vizualizaci fungování algoritmu.

Řešení a neřešení

Začněme definováním dvou množin řetězců.

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

Množina $A_1$ obsahuje všechna řešení našeho vyhledávacího problému, zatímco $A_0$ obsahuje řetězce, které nejsou řešeními (můžeme je označovat jako neřešení, když se to hodí). Tyto dvě množiny splňují $A_0 \cap A_1 = \varnothing$ a $A_0 \cup A_1 = \Sigma^n$, což znamená, že jde o bipartici množiny $\Sigma^n$.

Dále definujeme dva jednotkové vektory reprezentující rovnoměrné superpozice přes množiny řešení a neřešení.

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

Formálně vzato, každý z těchto vektorů je definován pouze tehdy, když odpovídající množina je neprázdná, ale dále se budeme soustředit na případ, kdy ani $A_0$ ani $A_1$ není prázdná. Případy $A_0 = \varnothing$ a $A_1 = \varnothing$ se dají snadno řešit zvlášť, a to uděláme později.

Mimochodem, zde používaná notace je běžná: kdykoli máme konečnou a neprázdnou množinu $S$, můžeme zapsat $\vert S\rangle$ pro označení kvantového stavového vektoru, který je rovnoměrný přes prvky $S$.

Definujme také $\vert u \rangle$ jako rovnoměrný kvantový stav přes všechny $n$-bitové řetězce:

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

Všimni si, ž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.$$

Také platí $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle$, takže $\vert u\rangle$ reprezentuje stav registru $\mathsf{Q}$ po inicializaci v kroku 1 Groverova algoritmu.

To znamená, že těsně před tím, než v kroku 2 proběhnou iterace $G$, je stav $\mathsf{Q}$ obsažen ve dvourozměrném vektorovém prostoru generovaném vektory $\vert A_0\rangle$ a $\vert A_1\rangle$, a navíc koeficienty těchto vektorů jsou reálná čísla. Jak uvidíme, stav $\mathsf{Q}$ bude mít tyto vlastnosti vždy — tedy že stav je reálnou lineární kombinací $\vert A_0\rangle$ a $\vert A_1\rangle$ — po libovolném počtu iterací operace $G$ v kroku 2.

Pozorování o Groverově operaci

Nyní obrátíme pozornost ke Groverově operaci

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

a začneme zajímavým pozorováním o ní.

Představ si na chvíli, že bychom funkci $f$ nahradili složením $f$ s funkcí NOT — jinými slovy funkcí, kterou dostaneme převrácením výstupního bitu $f$. Tuto novou funkci nazveme $g$ a můžeme ji zapsat pomocí symbolů několika alternativními způsoby.

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

Všimni si, že

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

pro každý řetězec $x\in\Sigma^n$, a proto

$$Z_g = - Z_f.$$

To znamená, že kdybychom funkci $f$ nahradili funkcí $g$, Groverův algoritmus by fungoval úplně stejně — protože stavy, které z algoritmu získáme v obou případech, jsou nutně ekvivalentní až na globální fázi.

To není problém! Intuitivně řečeno, algoritmu je jedno, které řetězce jsou řešení a které neřešení — potřebuje pouze umět rozlišit řešení od neřešení, aby fungoval správně.

Působení Groverovy operace

Nyní se podívejme na působení $G$ na kvantové stavové vektory $\vert A_0\rangle$ a $\vert A_1\rangle$.

Nejprve si všimni, že operace $Z_f$ působí na $\vert A_0\rangle$ a $\vert A_1\rangle$ velmi jednoduše.

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

Za druhé, máme operaci $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$. Operace $Z_{\mathrm{OR}}$ je definována 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}$$

opět pro každý řetězec $x\in\Sigma^n$, a pohodlný alternativní způsob, jak tuto operaci vyjádřit, je následující:

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

Jednoduchý způsob, jak ověřit, že tento výraz odpovídá definici $Z_{\mathrm{OR}}$, je vyhodnotit jeho působení na stavy standardní báze.

Operaci $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ lze proto zapsat takto:

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

přičemž používáme stejné označení $\vert u \rangle$ jako výše pro rovnoměrnou superpozici přes všechny $n$-bitové řetězce.

A nyní máme vše potřebné k výpočtu působení $G$ na $\vert A_0\rangle$ a $\vert A_1\rangle$. Nejprve vypočítejme působení $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 za druhé vypočítejme působení $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}$$

V obou případech používáme rovnici

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

spolu s výrazy

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

které z ní vyplývají.

Shrnutí:

$$\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 jsme si již všimli, stav $\mathsf{Q}$ těsně před krokem 2 leží v dvourozměrném prostoru generovaném vektory $\vert A_0\rangle$ a $\vert A_1\rangle$, a právě jsme ukázali, že $G$ zobrazuje libovolný vektor v tomto prostoru na jiný vektor ve stejném prostoru. To znamená, že pro účely analýzy se můžeme soustředit výhradně na tento podprostor.

Abychom lépe porozuměli tomu, co se v tomto dvourozměrném prostoru děje, vyjádřeme působení $G$ na tento prostor jako matici:

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

jejíž první a druhý řádek/sloupec odpovídají $\vert A_0\rangle$, respektive $\vert A_1\rangle$. Dosud jsme v této sérii vždy spojovali řádky a sloupce matic s klasickými stavy systému, ale matice lze použít i k popisu působení lineárních zobrazení v různých bázích, jak to děláme zde.

I když to na první pohled vůbec není zřejmé, matice $M$ vznikne umocněním na druhou jednodušeji vypadající matice.

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

Matice

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

je rotační matice, kterou můžeme alternativně vyjádřit 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}$$

pro

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

Tento úhel $\theta$ bude hrát velmi důležitou roli v následující analýze, takže stojí za to zdůraznit jeho význam zde, když ho vidíme poprvé.

Ve světle tohoto vyjádření matice pozorujeme, ž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}.$$

Je to proto, že provedení rotace o úhel $\theta$ dvakrát je ekvivalentní rotaci o úhel $2\theta$. Jiný způsob, jak to nahlédnout, je využít alternativní vyjádření

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

spolu se vzorci pro dvojnásobný úhel z trigonometrie:

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

Shrnutí: stav registru $\mathsf{Q}$ na začátku kroku 2 je

$$\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 aplikace $G$ tento stav otočí o úhel $2\theta$ v prostoru generovaném vektory $\vert A_0\rangle$ a $\vert A_1\rangle$. Takže například máme

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

a obecně

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

Geometrický obraz

Nyní propojme analýzu, kterou jsme právě provedli, s geometrickým obrazem. Myšlenka spočívá v tom, že operace $G$ je součinem dvou zrcadlení (reflexí), $Z_f$ a $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ A výsledný efekt provedení dvou zrcadlení je provedení rotace.

Začněme s $Z_f$. Jak jsme si již dříve všimli, platí

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

V dvourozměrném vektorovém prostoru generovaném vektory $\vert A_0\rangle$ a $\vert A_1\rangle$ se jedná o zrcadlení kolem přímky rovnoběžné s $\vert A_0\rangle$, kterou nazveme $L_1$. Zde je obrázek znázorňující působení tohoto zrcadlení na hypotetický jednotkový vektor $\vert\psi\rangle$, u kterého předpokládáme, že je reálnou lineární kombinací $\vert A_0\rangle$ a $\vert A_1\rangle$.

Za druhé máme operaci $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$, o které jsme již viděli, že ji lze zapsat jako

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

Toto je rovněž zrcadlení, tentokrát kolem přímky $L_2$ rovnoběžné s vektorem $\vert u\rangle$. Zde je obrázek znázorňující působení tohoto zrcadlení na jednotkový vektor $\vert\psi\rangle$.

Když tato dvě zrcadlení složíme, získáme rotaci — o dvojnásobek úhlu mezi osami zrcadlení — jak znázorňuje tento obrázek.

Toto geometricky vysvětluje, proč je efektem Groverovy operace otočení lineárních kombinací $\vert A_0\rangle$ a $\vert A_1\rangle$ o úhel $2\theta$.