Nestrukturované vyhledávání

Shrnutí

Začneme popisem problému, který Groverův algoritmus řeší. Jako obvykle budeme v celé této diskusi označovat $\Sigma = \{0,1\}$ binární abecedu.

Předpokládejme, že

$$f:\Sigma^n \rightarrow \Sigma$$

je funkce z binárních řetězců délky $n$ do bitů. Budeme předpokládat, že tuto funkci umíme efektivně vyhodnotit, ale jinak je libovolná a nemůžeme se spoléhat na to, že má nějakou speciální strukturu nebo konkrétní implementaci, která by vyhovovala našim potřebám.

Groverův algoritmus hledá řetězec $x\in\Sigma^n$, pro který $f(x) = 1$. Řetězce tohoto druhu budeme označovat jako řešení daného vyhledávacího problému. Pokud existuje více řešení, pak je kterékoliv z nich považováno za správný výstup, a pokud žádné řešení neexistuje, správná odpověď vyžaduje, abychom oznámili, že řešení neexistují.

Tento úkol je popisován jako problém nestrukturovaného vyhledávání, protože se nemůžeme spoléhat na to, že $f$ má nějakou konkrétní strukturu, která by ho usnadnila. Nehledáme v uspořádaném seznamu ani v datové struktuře speciálně navržené pro usnadnění vyhledávání – v podstatě hledáme jehlu v kupce sena.

Intuitivně si můžeme představit, že máme extrémně složitý Booleovský obvod, který počítá $f$, a snadno ho můžeme spustit na zvoleném vstupním řetězci. Ale protože je tento obvod tak složitý, nemáme žádnou naději porozumět mu jeho zkoumáním (kromě schopnosti vyhodnotit ho na zvolených vstupních řetězcích).

Jeden způsob, jak tento vyhledávací úkol provést klasicky, je jednoduše projít všechny řetězce $x\in\Sigma^n$ a vyhodnotit $f$ na každém z nich, abychom zkontrolovali, zda je či není řešením. Dále budeme pro pohodlí psát

$$N = 2^n$$

V $\Sigma^n$ je $N$ řetězců, takže procházení všech vyžaduje $N$ vyhodnocení $f$. Za předpokladu, že jsme omezeni na vyhodnocování $f$ na zvolených vstupech, je to to nejlepší, co můžeme deterministickým algoritmem dosáhnout, pokud chceme zaručit úspěch. S pravděpodobnostním algoritmem bychom mohli doufat v úsporu času náhodným výběrem vstupních řetězců pro $f$, ale stále budeme potřebovat $O(N)$ vyhodnocení $f$, pokud chceme, aby tato metoda uspěla s vysokou pravděpodobností.

Groverův algoritmus řeší tento vyhledávací problém s vysokou pravděpodobností pomocí pouhých $O(\sqrt{N})$ vyhodnocení $f$. Aby bylo jasno, tato vyhodnocení funkce musí probíhat v superpozici, podobně jako dotazovací algoritmy diskutované v lekci Kvantové dotazovací algoritmy, včetně Deutschova algoritmu, Deutsch-Jozsova algoritmu a Simonova algoritmu. Na rozdíl od těchto algoritmů používá Groverův algoritmus iterativní přístup: vyhodnocuje $f$ na superpozicích vstupních řetězců a prokládá tato vyhodnocení dalšími operacemi, které mají za následek vytvoření interferenčních vzorů, vedoucích k řešení s vysokou pravděpodobností (pokud existuje) po $O(\sqrt{N})$ iteracích.

Formální formulace problému

Problém, který Groverův algoritmus řeší, formalizujeme pomocí dotazovacího modelu výpočtu. To znamená, že předpokládáme přístup k funkci $f:\Sigma^n\rightarrow\Sigma$ prostřednictvím dotazovacího hradla definovaného obvyklým způsobem:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

pro každé $x\in\Sigma^n$ a $a\in\Sigma$. Toto je akce $U_f$ na stavech standardní báze a její obecná akce je určena linearitou.

Jak bylo diskutováno v lekci Základy kvantových algoritmů, pokud máme Booleovský obvod pro výpočet $f$, můžeme tento popis Booleovského obvodu transformovat na kvantový obvod implementující $U_f$ (za použití určitého počtu pracovních qubitů, které začínají a končí výpočet ve stavu $\vert 0\rangle$). Takže ačkoli používáme dotazovací model k formalizaci problému, který Groverův algoritmus řeší, není omezen na tento model; Groverův algoritmus můžeme spustit na libovolné funkci $f$, pro kterou máme Booleovský obvod.

Zde je přesná formulace problému, který se jmenuje Search, protože hledáme řešení, tedy řetězec $x$, který způsobí, že se $f$ vyhodnotí na $1$.

Search

Vstup: funkce $f:\Sigma^n\rightarrow\Sigma$
Výstup: řetězec $x\in\Sigma^n$ splňující $f(x) = 1$, nebo „žádné řešení", pokud takový řetězec $x$ neexistuje

Všimni si, že toto není problém se slibem — funkce $f$ je libovolná. Bude však užitečné zvážit následující slibovou variantu problému, kde máme zaručeno, že existuje právě jedno řešení. Tento problém se objevil jako příklad slibového problému v lekci Kvantové dotazovací algoritmy.

Unique search

Vstup: funkce tvaru $f:\Sigma^n \rightarrow \Sigma$
Slib: existuje právě jeden řetězec $z\in\Sigma^n$, pro který $f(z) = 1$, přičemž $f(x) = 0$ pro všechny řetězce $x\neq z$
Výstup: řetězec $z$

Také si všimni, že problém Or zmíněný ve stejné lekci úzce souvisí s problémem Search. U tohoto problému je cílem jednoduše určit, zda řešení existuje či nikoli, na rozdíl od jeho skutečného nalezení.