Popis Groverova algoritmu

V této sekci popíšeme Groverův algoritmus. Začneme diskusí o fázových dotazovacích hradlech a o tom, jak je sestrojit, poté přejdeme k popisu samotného Groverova algoritmu. Na závěr stručně probereme, jak se tento algoritmus přirozeně aplikuje na vyhledávání.

Fázová dotazovací hradla

Groverův algoritmus využívá operace známé jako fázová dotazovací hradla. Na rozdíl od běžného dotazovacího hradla $U_f$, definovaného pro danou funkci $f$ obvyklým způsobem popsaným výše, je fázové dotazovací hradlo pro funkci $f$ definováno jako

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

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

Operaci $Z_f$ lze implementovat pomocí jednoho dotazovacího hradla $U_f,$ jak naznačuje tento diagram:

Tato implementace využívá jev fázového zpětného rázu (phase kickback) a vyžaduje, aby byl k dispozici jeden pracovní qubit inicializovaný do stavu $\vert -\rangle$. Tento qubit zůstane ve stavu $\vert - \rangle$ i po dokončení implementace a může být znovu použit (například pro implementaci dalších $Z_f$ hradel) nebo jednoduše zahozen.

Kromě operace $Z_f$ budeme také používat fázové dotazovací hradlo pro $n$-bitovou funkci OR, která je definována následovně pro každý řetězec $x\in\Sigma^n$.

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

Explicitně, fázové dotazovací hradlo pro $n$-bitovou funkci OR funguje takto:

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

Pro upřesnění, takto $Z_{\mathrm{OR}}$ funguje na stavech standardní báze; jeho chování na libovolných stavech je z tohoto výrazu určeno linearitou.

Operaci $Z_{\mathrm{OR}}$ lze implementovat jako kvantový obvod tak, že začneme s Booleovským obvodem pro funkci OR, poté sestrojíme operaci $U_{\mathrm{OR}}$ (tedy standardní dotazovací hradlo pro $n$-bitovou funkci OR) pomocí postupu popsaného v lekci Základy kvantových algoritmů a nakonec operaci $Z_{\mathrm{OR}}$ pomocí jevu fázového zpětného rázu popsaného výše. Všimni si, že operace $Z_{\mathrm{OR}}$ nezávisí na funkci $f,$ a proto ji lze implementovat kvantovým obvodem bez jakýchkoli dotazovacích hradel.

Popis algoritmu

Nyní, když máme dvě operace $Z_f$ a $Z_{\mathrm{OR}}$, můžeme popsat Groverův algoritmus.

Algoritmus odkazuje na číslo $t$, které je počtem iterací, které provádí (a tedy počtem dotazů na funkci $f$, které vyžaduje). Toto číslo $t$ není v Groverově algoritmu, jak ho popisujeme, specifikováno, a později v lekci probereme, jak ho lze zvolit.

Grover's algorithm

1. Inicializuj $n$-qubitový registr $\mathsf{Q}$ do stavu samých nul $\vert 0^n \rangle$ a poté aplikuj Hadamardovu operaci na každý qubit registru $\mathsf{Q}$.
2. Aplikuj $t$-krát unitární operaci $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ na registr $\mathsf{Q}$
3. Změř qubity registru $\mathsf{Q}$ měřením ve standardní bázi a vypiš výsledný řetězec.

Operace $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ iterovaná v kroku 2 bude po zbytek této lekce nazývána Groverova operace. Zde je reprezentace Groverovy operace jako kvantový obvod pro $n=7\!:$

V tomto diagramu je operace $Z_f$ zobrazena jako větší než $Z_{\mathrm{OR}},$ což slouží jako neformální vizuální nápověda naznačující, že se pravděpodobně jedná o nákladnější operaci. Konkrétně, když pracujeme v rámci dotazovacího modelu, $Z_f$ vyžaduje jeden dotaz, zatímco $Z_{\mathrm{OR}}$ nevyžaduje žádné dotazy. Pokud místo toho máme Booleovský obvod pro funkci $f$ a převedeme ho na kvantový obvod pro $Z_f,$ můžeme rozumně očekávat, že výsledný kvantový obvod bude větší a složitější než obvod pro $Z_{\mathrm{OR}}.$

Zde je diagram kvantového obvodu pro celý algoritmus při $n=7$ a $t=3$. Pro větší hodnoty $t$ stačí přidat další instance Groverovy operace bezprostředně před měření.

Aplikace na vyhledávání

Groverův algoritmus lze na problém Search aplikovat následovně:

• Zvol číslo $t$ v kroku 2. (Toto je probráno později v lekci.)

• Spusť Groverův algoritmus na funkci $f$ s jakoukoli zvolenou hodnotou $t$, čímž získáš řetězec $x\in\Sigma^n$.

• Dotázej se funkce $f$ na řetězec $x,$ abys zjistil, zda je platným řešením:

  • Pokud $f(x) = 1$, pak jsme nalezli řešení, takže můžeme skončit a vypsat $x$.

  • V opačném případě, pokud $f(x) = 0$, můžeme buď spustit proceduru znovu, případně s jinou volbou $t$, nebo se můžeme rozhodnout vzdát a vypsat „žádné řešení."

Jakmile zanalyzujeme, jak Groverův algoritmus funguje, uvidíme, že při volbě $t = O(\sqrt{N})$ získáme řešení našeho vyhledávacího problému (pokud existuje) s vysokou pravděpodobností.