Popis Groverova algoritmu

V této sekci popíšeme Groverův algoritmus. Začneme diskusí o fázových dotazovacích Gate 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í Gate

Groverův algoritmus využívá operace známé jako fázové dotazovací Gate. Na rozdíl od běžného dotazovacího Gate $U_f,$ definovaného pro danou funkci $f$ obvyklým způsobem popsaným výše, je fázový dotazovací Gate pro funkci $f$ definován 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 Gate $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$ Gate) nebo jednoduše zahozen.

Kromě operace $Z_f$ budeme také používat fázový dotazovací Gate 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í Gate 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ý Circuit tak, že začneme s Booleovským obvodem pro funkci OR, poté sestrojíme operaci $U_{\mathrm{OR}}$ (tedy standardní dotazovací Gate 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 Circuit bez jakýchkoli dotazovacích Gate.

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ý Circuit 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ý Circuit pro $Z_f,$ můžeme rozumně očekávat, že výsledný kvantový Circuit bude větší a složitější než Circuit pro $Z_{\mathrm{OR}}.$

Zde je diagram kvantového Circuit 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í.