Theorie van het zoekalgoritmen van Grover

In dit artikel vindt u een gedetailleerde theoretische uitleg van de wiskundige principes die het algoritme van Grover laten werken.

Zie Het zoekalgoritmen van Grover implementeren voor een praktische implementatie van het algoritme van Grover om wiskundige problemen op te lossen.

Verklaring van het probleem

Elke zoektaak kan worden uitgedrukt met een abstracte functie $f(x)$ die zoekitems $x$ accepteert. Als het item $x$ een oplossing is voor de zoektaak, dan $f(x)=1$. Als het item $x$ geen oplossing is, dan $f(x)=0$. Het zoekprobleem bestaat uit het vinden van een item $x_0$ zodanig dat $f(x_0)=1$.

De taak die het algoritme van Grover probeert op te lossen, kan als volgt worden uitgedrukt: met een klassieke functie $f(x):\{0,1\}^n \rightpijl\{0,1\}$, waarbij $n$ de bitgrootte van de zoekruimte is, zoekt u een invoer $x_0$ waarvoor $f(x_0)=1$. De complexiteit van het algoritme wordt gemeten door het aantal toepassingen van de functie $f(x).$ In het ergste geval moet f(x)$ in het ergste geval $in totaal $N-1$ keer worden geëvalueerd, waarbij $N=2^n$ alle mogelijkheden uit proberen. Na $N-1-elementen$ moet dit het laatste element zijn. Het kwantumalgoritmen van Grover kunnen dit probleem veel sneller oplossen door een kwadratische snelheid te bieden. Kwadratisch betekent hier dat slechts ongeveer $\sqrt{N}$ evaluaties nodig zouden zijn, vergeleken met $N$.

Overzicht van het algoritme

Stel dat er $N=2^n$ in aanmerking komende items zijn voor de zoektaak en dat deze indexen zijn door aan elk item een geheel getal van $0$ tot N-1$ toe te $wijzen. Stel verder dat er verschillende geldige M-invoerwaarden zijn$, wat betekent dat er M-ingangen$ zijn $waarvoor $f(x)=1$.$ De stappen van het algoritme zijn dan als volgt:

1. Begin met een register van $n$ qubits die zijn geïnitialiseerd in de status $\ket{0}$.
2. Bereid het register voor in een uniforme superpositie door H$ toe te passen op $elke qubit van het register: $$|\text{register}\rangle=\frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$$
3. Pas de volgende bewerkingen toe op het register $N_{\text{optimale}}$ tijden:
   1. De faseorakel $O_f$ die een voorwaardelijke faseverschuiving van $-1$ toepast voor de oplossingsitems.
   2. Pas H$ toe $op elke qubit in het register.
   3. Een voorwaardelijke faseverschuiving van -1$ naar elke rekenkundige basisstatus, met uitzondering van .$$\ket{0}$ Dit kan worden vertegenwoordigd door de eenheidsbewerking $-O_0$, omdat $O_0$ de voorwaardelijke faseverschuiving naar $\ket{0}$ alleen vertegenwoordigt.
   4. Pas H$ toe $op elke qubit in het register.
4. Meet het register om de index te verkrijgen van een item dat een oplossing met zeer hoge waarschijnlijkheid is.
5. Controleer of het een geldige oplossing is. Zo niet, dan start u opnieuw.

$\text{N_optimal=}\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-{2}\frac{1}{\right\rfloor$ is het optimale aantal iteraties waarmee de kans op het verkrijgen van het juiste item wordt gemaximaliseerd door het register te meten.

Notitie

De gezamenlijke toepassing van de stappen 3.b, 3.c en 3.d is in de literatuur meestal bekend als de diffusieoperator van Grover.

De algemene eenheidsbewerking die op het register wordt toegepast, is:

$$(-H^{\otimes n}O_0H^{\otimes n}O_f)^{N_{\text{optimale}}}H^{\otimes n}$$

De status van het register stap voor stap volgen

Ter illustratie van het proces volgen we de wiskundige transformaties van de status van het register voor een eenvoudig geval waarin er slechts twee qubits zijn en het geldige element is $\ket{01}.$

1. Het register begint in de status: $$|\text{register}\rangle=|00\rangle$$

2. Na het toepassen van $H op elke qubit transformeert de status van het register naar: $$|\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. Vervolgens wordt de fase oracle toegepast om het volgende te krijgen: $$|\text{register}\rangle\frac=12(\ket{{00}-\ket{{01}+{10}\ket{+)\ket{{11}$$

4. Vervolgens $handelt H$ weer op elke qubit om te geven: $$|\text{register\frac=}\rangle12(\ket{{00}+\ket{{01}-\ket{{10}+)\ket{{11}$$

5. De voorwaardelijke faseverschuiving wordt nu toegepast op elke status behalve $\ket{00}$: $$|\text{register}\rangle=\frac12(\ket{{00}-\ket{{01}+{10}\ket{-)\ket{{11}$$

6. Ten slotte eindigt de eerste Grover-iteratie met het opnieuw toepassen van $H$ om te krijgen: $$|\text{registreren}\rangle=\ket{{01}$$

   Door de bovenstaande stappen te volgen, wordt het geldige item in één iteratie gevonden. Zoals u later zult zien, komt dit omdat voor N=4 en één geldig item $N_\text{optimaal}=1$.

Geometrische uitleg

Om te zien waarom het algoritme van Grover werkt, gaan we het algoritme vanuit een geometrisch perspectief bestuderen. Laat $\ket{\text{de}}$ superpositie zijn van alle statussen die geen oplossing voor het zoekprobleem zijn. Stel dat er M$ geldige oplossingen zijn$:

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

De statuswaarde $\ket{\text{}}$ wordt gedefinieerd als de superpositie van alle statussen die een oplossing vormen voor het zoekprobleem:

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

Aangezien goede en slechte sets elkaar uitsluiten omdat een item niet geldig en niet geldig kan zijn, zijn de statussen $\ket{\text{goed}}$ en $\ket{\text{slecht}}$ orthogonaal. Beide toestanden vormen de orthogonale basis van een vlak in de vectorruimte. U kunt dit vlak gebruiken om het algoritme te visualiseren.

Stel dat $\ket{\psi}$ het een willekeurige toestand is die zich in het vliegtuig bevindt, omspannen door $\ket{\text{goed}}$ en $\ket{\text{slecht}}$. Elke toestand die zich in dat vlak bevindt, kan worden uitgedrukt als:

$$\ket{\psi}=\alpha\ket{\text{goed}} + \beta\ket{\text{slecht}}$$

waarbij $\alpha$ en $\beta$ reële getallen zijn. Laten we nu de weerspiegelingsoperator $R_{\ket{\psi}}$ introduceren, waarbij $\ket{\psi}$ een qubitstatus zich in het vlak bevindt. De operator wordt gedefinieerd als:

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

Het wordt de weerspiegelingsoperator over $\ket{\psi}$ genoemd omdat deze geometrisch kan worden geïnterpreteerd als weerspiegeling van de richting van $\ket{\psi}$. Om het te zien, neemt u de orthogonale basis van het vlak gevormd door $\ket{\psi}$ en zijn orthogonale complement $\ket{\psi^{\perp}}$. Elke toestand $\ket{\xi}$ van het vlak kan op deze basis worden ontbonden:

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

Als de operator $R_{\ket{\psi}}$ wordt toegepast op $\ket{\xi}$:

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

De operator $R_\ket{\psi}$ keert het onderdeel orthogonaal om, $\ket{\psi}$ maar laat het $\ket{\psi}$ onderdeel ongewijzigd. $Daarom is R_\ket{\psi}$ een reflectie over $\ket{\psi}$.

Het algoritme van Grover begint na de eerste toepassing van $H$ op elke qubit met een uniforme superpositie van alle toestanden. Dit kan worden geschreven als:

$$\ket{\text{alle}}\sqrt{\frac{=M}{N}}\ket{\text{goed}} + \sqrt{\frac{N-M}{N}}\ket{\text{slecht}}$$

En zo leeft de staat in het vliegtuig. Houd er rekening mee dat de kans op het verkrijgen van een juist resultaat bij het meten van de gelijke superpositie gewoon $|\braket{\text{goed}|{\text{is voor alle}}}|^2=M/N$, wat u zou verwachten van een willekeurige schatting.

Het oracle $O_f$ voegt een negatieve fase toe aan elke oplossing voor het zoekprobleem. Daarom kan het worden geschreven als een reflectie over de $\ket{\text{slechte}}$ as:

$$= O_f R_{\ket{\text{bad=}}} 2\ket{\text{slecht}}\bra{\text{}} - \mathcal{I}$$

Analoog is de voorwaardelijke faseverschuiving $O_0$ gewoon een omgekeerde reflectie over de status $\ket{0}$:

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

Als u dit weet, is het gemakkelijk om te controleren of de Grover-diffusiebewerking $-H^{\otimes n} O_0 H^{\otimes n}$ ook een weerspiegeling is van de toestand $\ket{allemaal}$. Doe het volgende:

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

Het is aangetoond dat elke iteratie van het algoritme van Grover een samenstelling is van twee reflecties $R_\ket{\text{bad}}$ en $R_\ket{\text{alle}}$.

Het gecombineerde effect van elke Grover-iteratie is een draaiing tegen de klok in van een hoek $2\theta$. Gelukkig is de hoek $theta$ gemakkelijk te vinden. Omdat $\theta$ slechts de hoek is tussen $\ket{\text{alles}}$ en $\ket{\text{slecht}}$, kan men het scalaire product gebruiken om de hoek te vinden. Het is bekend dat $\cos{\theta}=\braket{\text{allemaal}|\text{slecht}}$ is, dus men moet alle}|\text{slechte}}$ berekenen$\braket{\text{. Van de ontleding van $\ket{\text{alles}}$ in termen van $\ket{\text{slecht}}$ en $\ket{\text{goed}}$, volgt:

$$\theta = \arccos{\left(\braket{\text{all}|\text{bad}}\right)}= \arccos{\left(\sqrt{\frac{N-M}{N}}\right)}$$

De hoek tussen de toestand van het register en de $\ket{\text{goede}}$ toestand neemt af met elke iteratie, wat resulteert in een grotere kans op het meten van een geldig resultaat. Als u deze kans wilt berekenen, hoeft u alleen een goed}|\text{register}}|^2$ te berekenen$|\braket{\text{. De hoek tussen $\ket{\text{goed}}$ en $\ket{\text{register}}$$\gamma (k),$ waarbij $k$ het aantal iteraties is:

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

Daarom is de kans op succes:

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

Optimaal aantal iteraties

Aangezien de kans op succes kan worden geschreven als een functie van het aantal iteraties, kan het optimale aantal iteraties $N_{\text{optimaal}}$ worden gevonden door het kleinste positieve gehele getal te berekenen dat (ongeveer) de succeskansfunctie maximaliseert.

Het is bekend dat $\sin^2{x}$ het eerste maximum voor $x=\frac{\pi}{2}$ bereikt, dus:

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

Dit geeft het volgende:

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

Waarbij in de laatste stap $\arccos \sqrt{1-x\sqrt{=}x +} O(x^{3/2})$.

Daarom kunt u N_optimal kiezen om N_\text{optimal\left}=\lfloor \frac{\pi{4}\sqrt{\frac{}{N}{M}}-{1}{2}\frac{\right\rfloor$ te zijn.$$}$\text{

Complexiteitsanalyse

Uit de vorige analyse $zijn O\left(\sqrt{\frac{N}{M}}\right)$-query's van de oracle-O_f$$nodig om een geldig item te vinden. Kan het algoritme echter efficiënt worden geïmplementeerd in termen van tijdscomplexiteit? $$ O_0 is gebaseerd op het berekenen van Booleaanse bewerkingen op $n$ bits en is bekend dat deze kan worden geïmplementeerd met behulp van $O(n)$-poorten. Er zijn ook twee lagen van $n$ Hadamard poorten. Beide componenten vereisen dus alleen $O(n)$ poorten per iteratie. Omdat $N=2^n$, volgt hieruit dat $O(n)=O(log(N))$. $Als er dus O\left(\sqrt{\frac{N}{M}}\right)$-iteraties en $O(log(N)))-$poorten per iteratie nodig zijn, is $de totale tijdcomplexiteit (zonder rekening te houden met de oracle-implementatie) O\left(\sqrt{\frac{N}{M-logboek}}(N))\right).$

De algehele complexiteit van het algoritme is uiteindelijk afhankelijk van de complexiteit van de implementatie van het oracle $O_f$. Als een functie-evaluatie veel ingewikkelder is op een kwantumcomputer dan op een klassieke computer, is de algehele runtime van het algoritme langer in het geval van kwantum, ook al worden er technisch gezien minder query's gebruikt.

Referenties

Als u meer wilt weten over het algoritme van Grover, kunt u een van de volgende bronnen raadplegen:

• Origineel papier van Lov K. Grover
• Sectie Kwantumzoekalgoritmen van Nielsen, M. A. &Amp; Chuang, I. L. (2010). Kwantumberekening en kwantuminformatie.
• Algoritme van Grover op Arxiv.org

Volgende stappen

• Tussenliggende kwantumweergave
• Vectoren en matrices
• T-poorten en T-fabrieken
• Meerdere qubits