Teorie Groverova vyhledávacího algoritmu

V tomto článku najdete podrobné teoretické vysvětlení matematických principů, díky kterým Groverův algoritmus funguje.

Praktickou implementaci Groverova algoritmu k řešení matematických problémů najdete v tématu Implementace Groverova vyhledávacího algoritmu.

Prohlášení o problému

Groverův algoritmus zrychluje řešení na nestrukturované vyhledávání dat (nebo problém hledání), které spouští hledání v menším počtu kroků, než by mohl jakýkoli klasický algoritmus. Libovolný vyhledávací úkol lze vyjádřit pomocí abstraktní funkce $f(x),$ která přijímá položky hledání $x$. Pokud je položka $x$ řešením pro úlohu hledání, pak $f(x)=1$. Pokud položka $x$ není řešením, pak $f(x)=0$. Problém hledání se skládá z vyhledání libovolné položky $x_0$ tak, aby $f(x_0)=1$.

Jakýkoliv problém, který vám umožní zkontrolovat, zda je daná hodnota $x$ platným řešením ( " Ano nebo žádný problém") lze formulovat z hlediska problému hledání. Tady je několik příkladů:

• Boolean satisfiability problem: Is the set of Boolean values $x$ an interpret (an assignment of values to variables), který splňuje daný logický vzorec?
• Problém cestovního prodejce: Popisuje $x$ nejkratší možnou smyčku, která spojuje všechna města?
• Problém s vyhledáváním v databázi: Obsahuje tabulka databáze záznam $x$?
• Problém celočíselného faktorizace: Je pevné číslo $N$ dělitelné číslem $x$?

Úloha, kterou Groverův algoritmus má vyřešit, se dá vyjádřit takto: při zadání klasické funkce $f(x):\{0,1\}^n \rightarrow\{0,1\}$, kde $n$ je bitová velikost vyhledávacího prostoru, najděte vstupní $x_0$ , pro který $f(x_0)=1$. Složitost algoritmu se měří počtem použití funkce $f(x).$ V nejhorším scénáři $musí být f(x)$ vyhodnoceno celkem N-1$ $krát, kde $N=2^n$ zkouší všechny možnosti. Za $N-1$ prvky musí být posledním prvkem. Groverův kvantový algoritmus dokáže tento problém vyřešit mnohem rychleji a poskytuje kvadratické zrychlení. Kvadratický zde znamená, že ve srovnání s N by se vyžadovalo pouze hodnocení $\sqrt{N$}$.$

Náčrt algoritmu

Předpokládejme, že pro úlohu vyhledávání existuje $počet opravňujících položek N=2^n$ a indexují se tak, že každé položce přiřadíte celé číslo od $0$ do $N-1$. Dále předpokládejme, že existují $různé platné vstupy M$ , což znamená, že existují $vstupy M$ , pro které $f(x)=1$. Kroky algoritmu jsou pak následující:

1. Začněte registrem $n$ qubitů inicializovaných ve stavu $\ket{0}$.
2. Připravte registr do jednotné superpozice použitím $H$ na každý qubit registru: $$|\text{zaregistrujte}\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x.\rangle$$
3. Pro registr $použijte následující operace N_{\text{optimální}}$ časy:
   1. Orákulum $fáze O_f$ , který pro položky řešení použije podmíněný posun $fáze -1$ .
   2. Použijte $H$ pro každý qubit v registru.
   3. Podmíněný posun $fáze -1$ do každého výpočetního základního stavu s výjimkou $\ket{0}$. To může reprezentovat jednotková operace $-O_0$, protože $O_0$ představuje podmíněný posun fáze pouze na $\ket{0}$ .
   4. Použijte $H$ pro každý qubit v registru.
4. Změřte registr, abyste získali index položky, která je řešením s velmi vysokou pravděpodobností.
5. Zkontrolujte, jestli se jedná o platné řešení. Pokud ne, začněte znovu.

$\text{N_optimal=}\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-{2}\frac{1}{\right\rfloor$ je optimální počet iterací, které maximalizují pravděpodobnost získání správné položky měřením registru.

Poznámka:

Společné použití kroků 3.b, 3.c a 3.d se obvykle v literaturě označuje jako Groverův operátor difuzní.

Celková jednotková operace použitá na registr je:

$$(-H^{\otimes n}O_0H^{\otimes n}O_f)^{N_{\text{optimální}}}H^{\otimes n}$$

Krok za krokem podle stavu registru

Pro ilustraci tohoto procesu se podíváme na matematické transformace stavu registru pro jednoduchý případ, ve kterém jsou pouze dva qubity a platným prvkem je $\ket{01}.$

1. Registrace začíná ve stavu: $$|\text{zaregistrovat}\rangle=|00\rangle$$

2. Po použití $H u každého qubitu se stav registru transformuje na: $$|\text{register}\rangle{1}{\sqrt{=\frac{\sum{4}}_{i \in \{0,1\}^2}|i\rangle=\frac12(\ket{00}+\ket{01}+\ket{10}+)\ket{11}$$$

3. Pak se použije orákulum fáze pro získání: $$|\text{registrace\frac}\rangle=12(\ket{{00}-\ket{{01}+\ket{{10}+)\ket{{11}$$

4. Pak $H$ na každém qubitu znovu působí, aby dal: $$|\text{zaregistrovat}\rangle\frac=12(\ket{{00}+\ket{{01}-{10}\ket{+)\ket{{11}$$

5. Nyní se podmíněný posun fáze použije u každého stavu s výjimkou $\ket{00}$: $$|\text{register\frac}\rangle=12(\ket{{00}-\ket{{01}+\ket{{10}-)\ket{{11}$$

6. Nakonec se první iterace Groveru ukončí opětovným použitím $H$ pro získání: registrace: $$|\text{}\rangle=\ket{{01}$$

   Podle výše uvedených kroků se platná položka nachází v jedné iteraci. Jak uvidíte později, je to proto, že pro N=4 a jednu platnou položku, $N_\text{optimální}=1$.

Geometrické vysvětlení

Abychom zjistili, proč Groverův algoritmus funguje, podívejme se na algoritmus z geometrické perspektivy. Nechejte $\ket{\text{špatně}}$ superpozici všech stavů, které nejsou řešením problému hledání. Za předpokladu, že existují $platná řešení M$ :

$$\ket{\text{bad}}=\frac{{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$

Dobrý stav $\ket{\text{}}$ je definován jako superpozice všech stavů, které jsou řešením problému hledání:

$$\ket{\text{good}}=\frac{{1}{\sqrt{M}}\sum_{x:f(x)=1}\ket{x}$$

Vzhledem k tomu, že dobré a špatné jsou vzájemně se vylučující sady, protože položka nemůže být platná a není platná, jsou stavy $\ket{\text{dobré}}$ a $\ket{\text{špatné}}$ jsou orthogonální. Oba stavy tvoří orthogonální základ roviny ve vektorovém prostoru. Tuto rovinu můžete použít k vizualizaci algoritmu.

Předpokládejme, že $\ket{\psi}$ je libovolný stav, který žije v letadle rozložený $\ket{\text{podle dobrého}}$ a $\ket{\text{špatného}}$. Jakýkoli stav žijící v této rovině lze vyjádřit takto:

$$\ket{\psi}=\alpha\ket{\text{dobrý}} + \beta\ket{\text{špatný}}$$

kde $\alpha$ a $\beta$ jsou reálná čísla. Teď si představíme operátor $reflexe R_{\ket{\psi}}$, kde $\ket{\psi}$ se nachází jakýkoli stav qubitu žijícího v rovině. Operátor je definován takto:

$${\ket{\psi}}=R_2\ket{\psi}\bra{\psi}-\mathcal{I}$$

Označuje se jako operátor reflexe, $\ket{\psi}$ protože jej lze geometricky interpretovat jako odraz o směru $\ket{\psi}$. Chcete-li to vidět, vezměte orthogonální základ roviny vytvořené $\ket{\psi}$ a jeho orthogonální doplněk $\ket{\psi^{\perp}}$. Jakýkoliv stav $\ket{\xi}$ roviny lze na takové bázi rozložit:

$$\ket{\xi}=\mu \ket{\psi} + \nu {\ket{\psi^{\perp}}}$$

Pokud jeden použije operátor $R_{\ket{\psi}}$ na $\ket{\xi}$:

$${\ket{\psi}}\ket{R_\xi}=\mu \ket{\psi} - \nu {\ket{\psi^{\perp}}}$$

Operátor $R_\ket{\psi}$ invertuje komponentu orthogonal na $\ket{\psi}$ komponentu $\ket{\psi}$ , ale ponechá ji beze změny. $Proto R_\ket{\psi}$ je odrazem o $\ket{\psi}$.

Groverův algoritmus po prvním použití $H$ na každý qubit začíná jednotným superpozicí všech stavů. Může to být napsané takto:

$$\ket{\text{všechny}}\sqrt{\frac{=M}{N}}\ket{\text{dobré}} + \sqrt{\frac{N-M}{N špatné}}\ket{\text{}}$$

A tak stát žije v letadle. Všimněte si, že pravděpodobnost získání správného výsledku při měření ze stejné superpozice je pouze $|\braket{\text{dobrá}|{\text{^}}}|2=M/N$, což je to, co byste očekávali od náhodného odhadu.

Orákulum $O_f$ přidá zápornou fázi k jakémukoli řešení problému hledání. Proto může být napsán jako odraz o $\ket{\text{špatné}}$ ose:

$$= O_f R_{\ket{\text{bad=}}} 2\ket{\text{špatné}}\bra{\text{}} - \mathcal{I}$$

Podobně, podmíněný posun $fáze O_0$ je jen invertovaný odraz o stavu $\ket{0}$:

$$O_0 R_{\ket{0}}= -2\ket{{0}\bra{0} + \mathcal{I =}$$

Když znáte tuto skutečnost, je snadné zkontrolovat, že operace $Grover difúze -H^{\otimes n} O_0 H^{\otimes n}$ je také odrazem o stavu $\ket{všech}$. Stačí:

$$-H^{\otimes n} O_0 H^{\otimes n}=2H^{\otimes n}\ket{0}\bra{{0}H^ n} -H^{\otimes{\otimes n}\mathcal{I}H^{\otimes n=} 2\ket{\text{all}}}}\bra{\text{ - \mathcal{I}= R_all{\ket{\text{}}}$$

Ukázalo se, že každá iterace Groverova algoritmu představuje složení dvou odrazů $R_\ket{\text{bad}}$ a $R_\ket{\text{all}}$.

Kombinovaný efekt každé iterace Groveru je otočení proti směru hodinových ručiček úhlu $2\teta$. Naštěstí je úhel $\theta$ snadno najít. Vzhledem k tomu $, že \theta$ je jen úhel mezi $\ket{\text{všemi}}$ a $\ket{\text{špatnými}}$, můžete k nalezení úhlu použít skalární součin. Je známo, že $\cos{\theta}=\braket{\text{všechny}|\text{špatné}}$, takže jeden musí vypočítat $\braket{\text{všechny}|\text{špatné}}$. Z rozkladu $\ket{\text{všech}}$ z hlediska špatného}}$ a $\ket{\text{dobrého $\ket{\text{}}$se to týká:

$$\theta = \arccos{\left(\braket{\text{vše}|\text{špatné}}\right)}= \arccos{\left(\sqrt{\frac{N-M}{N}}\right)}$$

Úhel mezi stavem registru a $\ket{\text{dobrým}}$ stavem se snižuje s každou iterací, což vede k vyšší pravděpodobnosti měření platného výsledku. K výpočtu této pravděpodobnosti stačí vypočítat $|\braket{\text{dobrý}|\text{registr}}|^2$. Označení úhlu mezi dobrým a registrem}}$$\gamma (k)$, kde $k$ je počet iterací:$\ket{\text{}}$ $\ket{\text{

$$\gamma (k) =\frac{\pi}{2}-\theta -k2\theta =\frac{\pi}{{2} -(2k + 1) \theta $$

Pravděpodobnost úspěchu je proto:

$$P(\text{success}) = \cos^2((\gammak)) = \sin^2\left[(2k +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)\right]$$

Optimální počet iterací

Protože pravděpodobnost úspěchu může být napsána jako funkce počtu iterací, optimální počet iterací $N_{\text{optimalitu}}$ lze najít pomocí výpočtu nejmenšího kladného celého čísla, které (přibližně) maximalizuje funkci pravděpodobnosti úspěchu.

Je známo, že $\sin^2{x}$ dosáhne svého prvního maxima pro $x=\frac{\pi}{2}$, takže:

$$\frac{\pi}{{2}=(2k_{\text{optimal}} +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)$$

To dává:

$${\text{k_optimal}}=\frac{\pi}{4\arccos\left(\sqrt{1-M/N}\right)}-1/2\frac{= \pi}{{4}\sqrt{\frac{N}{M}}-\frac{1}{2}-O\left(\sqrt\frac{M}{N)}\right$$

Kde v posledním kroku $\arccos \sqrt{1-x x=}\sqrt{+} O(x^{3/2})$.

Proto můžete vybrat $N_optimální}$, aby se $N_\text{optimal}\left=\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\right\frac{{1}{2}\rfloor$\text{.

Analýza složitosti

Z předchozí analýzy $jsou potřeba dotazy O\left(\sqrt{\frac{N}{M}}\right)$ oracle $O_f$ k vyhledání platné položky. Je však možné algoritmus efektivně implementovat z hlediska složitosti času? $$ O_0 je založená na výpočetních logických operacích na $n$ bitech a je známo, že je možné implementovat pomocí $bran O(n$). Existují také dvě vrstvy $n$ Hadamardových bran. Obě tyto komponenty proto vyžadují pouze $brány O(n)$ pro každou iteraci. Protože $N=2^n$, následuje $O(n)=O(log(N))$. Proto pokud $jsou potřeba iterace O\left(\sqrt{\frac{N}{M}}\right)$ a $brány O(log(N))$ na iteraci, celková složitost času (bez zohlednění implementace orákula) je $O\left(\sqrt{\frac{N}{M}}log(N))\right).$

Celková složitost algoritmu nakonec závisí na složitosti implementace orákulum $O_f$. Pokud je vyhodnocení funkce na kvantovém počítači mnohem složitější než v klasickém počítači, bude celkové runtime algoritmu v kvantovém případě delší, i když technicky vzato používá méně dotazů.

Reference

Pokud chcete pokračovat ve učení o Groverově algoritmu, můžete zkontrolovat některý z následujících zdrojů:

• Originální papír od Lov K. Grover
• Oddíl kvantových vyhledávacích algoritmů nielsen, M. A. &zesilovač; Chuang, I. L. (2010). Kvantové výpočty a kvantové informace.
• Groverův algoritmus na Arxiv.org

Související obsah

• Propletení v kvantových výpočtech
• Vektory a matice
• Brány T a továrny T
• Více qubitů