Volba počtu iterací

Zjistili jsme, že stavový vektor registru $\mathsf{Q}$ v Groverově algoritmu zůstává po provedení inicializačního kroku ve dvourozměrném podprostoru generovaném vektory $\vert A_0\rangle$ a $\vert A_1\rangle$.

Cílem je najít prvek $x\in A_1$, a tohoto cíle dosáhneme, pokud dokážeme získat stav $\vert A_1\rangle$ — protože pokud tento stav změříme, máme zaručeno, že dostaneme výsledek měření $x\in A_1$. Vzhledem k tomu, že stav $\mathsf{Q}$ po $t$ iteracích v kroku 2 je

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

měli bychom zvolit $t$ tak, aby

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

bylo co nejblíže $1$ v absolutní hodnotě, abychom maximalizovali pravděpodobnost získání $x\in A_1$ z měření. Pro libovolný úhel $\theta \in (0,2\pi)$ hodnota $\sin((2t + 1)\theta)$ osciluje s rostoucím $t$, i když nemusí být nutně periodická — není zaručeno, že někdy dostaneme stejnou hodnotu dvakrát.

Kromě toho, že chceme, aby pravděpodobnost získání prvku $x\in A_1$ z měření byla velká, bychom přirozeně chtěli zvolit $t$ co nejmenší, protože $t$ aplikací operace $G$ vyžaduje $t$ dotazů na funkci $f$. Protože se snažíme, aby $\sin( (2t + 1) \theta)$ bylo blízko $1$ v absolutní hodnotě, přirozeným způsobem je zvolit $t$ tak, aby

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

Řešením pro $t$ dostaneme

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

Samozřejmě $t$ musí být celé číslo, takže tuto hodnotu nemusíme nutně trefit přesně — ale co můžeme udělat, je vzít nejbližší celé číslo k této hodnotě, což je

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

Toto je doporučený počet iterací pro Groverův algoritmus. Jak budeme pokračovat v analýze, uvidíme, že blízkost tohoto celého čísla k cílové hodnotě přirozeně ovlivňuje výkon algoritmu.

(Jen na okraj — pokud se cílová hodnota $\pi/(4\theta) - 1/2$ nachází přesně uprostřed mezi dvěma celými čísly, tento výraz pro $t$ dostaneme zaokrouhlením nahoru. Alternativně bychom mohli zaokrouhlit dolů, což dává smysl, protože to znamená o jeden dotaz méně — ale to je vedlejší a pro účely této lekce nepodstatné.)

Připomeňme, že hodnota úhlu $\theta$ je dána vzorcem

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

takže doporučený počet iterací $t$ závisí na počtu řetězců v $A_1$. To představuje problém, pokud nevíme, kolik máme řešení, jak si probereme později.

Jednoznačné hledání

Nejprve se zaměřme na situaci, kdy existuje jediný řetězec $x$ takový, že $f(x)=1$. Jinak řečeno, uvažujeme instanci problému jednoznačného hledání (Unique search). V tomto případě máme

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

což se dá pohodlně aproximovat jako

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

pro velká $N.$ Pokud dosadíme $\theta = 1/\sqrt{N}$ do výrazu

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

dostaneme

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

Připomeňme, že $t$ je nejen počet provedení operace $G$, ale také počet dotazů na funkci $f$ vyžadovaných algoritmem, takže jsme na dobré cestě k algoritmu, který vyžaduje $O(\sqrt{N})$ dotazů.

Nyní prozkoumáme, jak dobře doporučená volba $t$ funguje. Pravděpodobnost, že závěrečné měření dá jedinečné řešení, lze explicitně vyjádřit jako

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

První argument, $N,$ označuje počet položek, přes které hledáme, a druhý argument, který je v tomto případě $1$, označuje počet řešení. O něco později použijeme stejnou notaci obecněji, kde bude více řešení.

Zde je tabulka pravděpodobností úspěchu pro rostoucí hodnoty $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}$$

Všimni si, že tyto pravděpodobnosti nejsou striktně rostoucí. Zejména máme zajímavou anomálii pro $N=4$, kde získáme řešení s jistotou. Obecně však lze dokázat, že

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

pro všechna $N$, takže pravděpodobnost úspěchu jde k $1$ v limitě, když $N$ roste, jak naznačují hodnoty výše. To je skvělé!

Všimni si ale, že i slabý odhad jako $p(N,1) \geq 1/2$ potvrzuje užitečnost Groverova algoritmu. Ať už dostaneme jakýkoli výsledek měření $x$ z jednoho spuštění procedury, vždy můžeme ověřit, zda $f(x) = 1$ pomocí jediného dotazu na $f$. A pokud nezískáme jediný řetězec $x$, pro který $f(x) = 1$, s pravděpodobností nejvýše $1/2$ při jednom spuštění procedury, pak po $m$ nezávislých spuštěních procedury bude pravděpodobnost, že jsme tento jediný řetězec $x$ nezískali, nejvýše $2^{-m}$. To znamená, že pomocí $O(m \sqrt{N})$ dotazů na $f$ získáme jediné řešení $x$ s pravděpodobností alespoň $1 - 2^{-m}$. Použitím lepšího odhadu $p(N,1) \geq 1 - 1/N$ zjistíme, že pravděpodobnost nalezení $x\in A_1$ touto metodou je ve skutečnosti alespoň $1 - N^{-m}$.

Více řešení

Jak se mění počet prvků v $A_1$, mění se i úhel $\theta$, což může mít významný vliv na pravděpodobnost úspěchu algoritmu. Pro stručnost zapišme $s = \vert A_1 \vert$ pro počet řešení a stejně jako dříve budeme předpokládat, že $s\geq 1$.

Jako motivační příklad si představ, že máme $s = 4$ řešení místo jediného řešení, které jsme uvažovali výše. To znamená, že

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

což je přibližně dvojnásobek úhlu, který jsme měli v případě $\vert A_1 \vert = 1,$ když je $N$ velké. Předpokládej, že bychom nevěděli nic lepšího a zvolili stejnou hodnotu $t$ jako v případě s jediným řešením:

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

Efekt bude katastrofální, jak ukazuje následující tabulka pravděpodobností.

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

Tentokrát pravděpodobnost úspěchu jde k $0$, když $N$ jde k nekonečnu. To se děje proto, že efektivně rotujeme dvakrát rychleji než v případě s jediným řešením, takže přeletíme přes cíl $\vert A_1\rangle$ a skončíme blízko $-\vert A_0\rangle$.

Pokud však místo toho použijeme doporučenou volbu $t$, což je

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

pro

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

pak bude výkon lepší. Přesněji řečeno, s touto volbou $t$ dojde k úspěchu s vysokou pravděpodobností.

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

Zobecněním toho, co bylo tvrzeno dříve, lze dokázat, že

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

kde používáme notaci navrženou dříve: $p(N,s)$ označuje pravděpodobnost, že Groverův algoritmus spuštěný po $t$ iteracích odhalí řešení, když existuje celkem $s$ řešení z $N$ možností.

Tato dolní mez $1 - s/N$ pro pravděpodobnost úspěchu je poněkud zvláštní v tom, že více řešení znamená horší dolní mez — ale za předpokladu, že $s$ je výrazně menší než $N$, přesto usuzujeme, že pravděpodobnost úspěchu je poměrně vysoká. Jako dříve, pouhá skutečnost, že $p(N,s)$ je dostatečně velké, implikuje užitečnost algoritmu.

Také se stává, že

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

Tato dolní mez popisuje pravděpodobnost, že řetězec $x\in\Sigma^n$ vybraný rovnoměrně náhodně je řešením — takže Groverův algoritmus si vždy vede alespoň tak dobře jako náhodný odhad. (Ve skutečnosti, když $t=0$, Groverův algoritmus je náhodným odhadem.)

Nyní se podívejme na počet iterací (a tedy počet dotazů)

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

pro

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

Pro každé $\alpha \in [0,1]$ platí, že $\sin^{-1}(\alpha)\geq \alpha$, a tedy

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

To implikuje, že

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

To se projeví jako úspora v počtu dotazů s rostoucím $s$. Konkrétně, počet potřebných dotazů je

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

Neznámý počet řešení

Pokud je počet řešení $s = \vert A_1 \vert$ neznámý, je potřeba jiný přístup, protože v této situaci nemáme žádnou znalost $s$, která by nám pomohla při volbě $t$. Existuje ve skutečnosti více přístupů.

Jeden jednoduchý přístup je zvolit

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

rovnoměrně náhodně. Volba $t$ tímto způsobem vždy najde řešení (za předpokladu, že existuje) s pravděpodobností větší než 40 %, i když to není zřejmé a vyžaduje analýzu, která zde nebude zahrnuta. Dává to však smysl, zvláště když uvažujeme geometrický obrázek: rotace stavu $\mathsf{Q}$ náhodným počtem opakování je podobná volbě náhodného jednotkového vektoru v prostoru generovaném $\vert A_0\rangle$ a $\vert A_1\rangle$, u kterého je pravděpodobné, že koeficient u $\vert A_1\rangle$ je přiměřeně velký. Opakováním této procedury a kontrolou výsledku stejným způsobem jako dříve lze pravděpodobnost nalezení řešení přiblížit velmi blízko k $1$.

Existuje vylepšená metoda, která najde řešení, pokud existuje, pomocí $O(\sqrt{N/s})$ dotazů, i když počet řešení $s$ není znám, a vyžaduje $O(\sqrt{N})$ dotazů k určení, že neexistují žádná řešení, když $s=0$.

Základní myšlenka je volit $t$ rovnoměrně náhodně z množiny $\{1,\ldots,T\}$ iterativně, pro rostoucí hodnoty $T$. Konkrétně můžeme začít s $T = 1$ a zvyšovat ho exponenciálně, přičemž proces vždy ukončíme, jakmile je nalezeno řešení, a omezíme $T$ shora, abychom neplýtvali dotazy, když řešení neexistuje. Tento proces využívá skutečnosti, že méně dotazů je potřeba, když existuje více řešení. Je však třeba dát pozor na vyvážení rychlosti růstu $T$ s pravděpodobností úspěchu pro každou iteraci. (Volba $T \leftarrow \lceil \frac{5}{4}T\rceil$ funguje, jak ukazuje analýza. Zdvojnásobení $T$ však ne — to se ukazuje jako příliš rychlý nárůst.)

Triviální případy

V celé analýze, kterou jsme právě prošli, jsme předpokládali, že počet řešení je nenulový. Odkazováním na vektory

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

jsme implicitně předpokládali, že $A_0$ i $A_1$ jsou neprázdné. Zde stručně zvážíme, co se stane, když jedna z těchto množin je prázdná.

Než se pustíme do analýzy, uvědomme si zřejmou věc: pokud je každý řetězec $x\in\Sigma^n$ řešením, pak uvidíme řešení při měření; a pokud žádná řešení neexistují, neuvidíme žádné. V jistém smyslu není potřeba jít hlouběji.

Můžeme však rychle ověřit matematiku pro tyto triviální případy. Situace, kdy jedna z množin $A_0$ a $A_1$ je prázdná, nastane, když je $f$ konstantní; $A_1$ je prázdná, když $f(x) = 0$ pro každé $x\in\Sigma^n,$ a $A_0$ je prázdná, když $f(x) = 1$ pro každé $x\in\Sigma^n.$ To znamená, že

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

a proto

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

Takže bez ohledu na počet iterací $t$, které v těchto případech provedeme, měření vždy odhalí rovnoměrně náhodný řetězec $x\in\Sigma^n$.