Grover keresési algoritmusának elmélete

Ebben a cikkben részletes elméleti magyarázatot talál a Grover algoritmusát alkotó matematikai alapelvekről.

A Grover-algoritmus matematikai problémák megoldásához való gyakorlati megvalósításáért lásd : Grover keresési algoritmusának implementálása.

A probléma leírása

A Grover algoritmusa felgyorsítja a megoldást strukturálatlan adatkeresésekre (vagy keresési problémára), és kevesebb lépésben futtatja a keresést, mint bármely klasszikus algoritmus. Bármely keresési feladat kifejezhető egy f(x) absztrakt függvénnyel$, amely elfogadja az x$ keresési elemeket$.$ Ha az x$ elem $a keresési feladat megoldása, akkor $f(x)=1$. Ha az x$ elem $nem megoldás, akkor $f(x)=0$. A keresési probléma az f$(x_0)$1$ elem x_0=$kereséséből áll.

Minden olyan probléma, amely lehetővé teszi annak ellenőrzését, hogy egy adott érték $x$ érvényes megoldás-e (egy &'igen vagy nem probléma'&), keresési problémaként fogalmazható meg. Az alábbiakban néhány példát láthat:

• Logikai telítettségi probléma: Logikai értékek halmaza alapján megfelel-e a készlet egy adott logikai képletnek?
• Utazó értékesítő problémája: Mi a lehető legrövidebb hurok, amely összeköti az összes várost?
• Adatbázis-kereséssel kapcsolatos probléma: Egy adatbázistábla tartalmazza az x$$rekordot?
• Egész szám faktorizációs probléma: Az N$$szám osztható az x$$számmal?

A Grover algoritmusa által megoldani kívánt feladat a következőképpen fejezhető ki: egy klasszikus f(x):\0,1\^n $arrow\{0,1\} függvényt \righthasználva, ahol {n}$ a keresési terület bitmérete, keresse meg az f(x_0)$1$ bemeneti $x_0$$.=$ Az algoritmus összetettségét az f(x)$ függvény $használatainak száma méri. A legrosszabb esetben $az f(x)$ értékeket általában N-1-szer$$kell kiértékelni, ahol $az N=2^n$ az összes lehetőséget kipróbálja. Az N-1$ elemek után $az utolsó elemnek kell lennie. A Grover kvantum-algoritmusa sokkal gyorsabban meg tudja oldani ezt a problémát, ami kvadratikus felgyorsulást biztosít. A kvadratikus itt azt jelenti, hogy az N-hez$\sqrt{}$ képest csak az $N-értékelésekre$ lenne szükség.

Az algoritmus vázlata

Tegyük fel, hogy a $keresési tevékenységhez N=2^n$ jogosult elem tartozik, és az egyes elemek 0-tól $$$ N-1-ig$ egész számként vannak hozzárendelve. Tegyük fel továbbá, hogy m különböző érvényes bemenetek vannak$$, ami azt jelenti, hogy vannak $M$ bemenetek, amelyekhez $f(x)=1$. Az algoritmus lépései a következők:

1. Kezdje az állapotban $inicializált n$ qubitek regiszterével$\ket{0}$.
2. Készítse elő a regisztert egy egységes szuperpozícióba úgy, hogy H-t alkalmaz $a regiszter minden qubitére: $N$$|\text{}\rangle=\frac{1}{\sqrt{_}}x\sum0{^=N-1}x regiszter{}|\rangle$$
3. Alkalmazza a következő műveleteket a nyilvántartásra $N_{\text{optimális}}$ hányszor:
   1. A megoldáselemekhez a -1$ feltételes fáziseltolást $alkalmazó fázis oracle $O_f$.
   2. Alkalmazza $a H-t$ a regiszterben lévő összes qubitre.
   3. -1 feltételes fázisváltás $minden számítási alapállapotra, kivéve$.$\ket{0}$ Ezt a -O_0 egységművelet $jelölheti, mivel $O_0$ csak a feltételes fázisok eltolódását $ jelöli.$\ket{0}$
   4. Alkalmazza $a H-t$ a regiszterben lévő összes qubitre.
4. Mérje meg a regisztert egy nagyon nagy valószínűségű megoldásnak számító elem indexének lekéréséhez.
5. Ellenőrizze, hogy érvényes megoldás-e. Ha nem, kezdje újra.

$N_{\text{}}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}–\frac{{1}{{2}\right\rpadló$ az optimális számú iteráció, amely a regiszter mérésével maximalizálja a megfelelő tétel beszerzésének valószínűségét.

A nyilvántartásra alkalmazott általános egységes művelet a következő:

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

A regisztráció állapotának követése lépésről lépésre

A folyamat szemléltetéséhez vizsgáljuk meg a regiszter állapotának matematikai transzformációit egy egyszerű esethez, amelyben csak két qubit van, és az érvényes elem az $\ket{01}.$

1. A regisztráció a következő állapotban kezdődik:

   $$\ket{\text{ }}=\ket{ {00}$$ regisztrálása

2. A $H$ minden qubitre való alkalmazása után a regiszter állapota a következőre alakul:

   $$\ket{\text{register}}=\frac{{1}{\sqrt{4}}\sum_{i \in \lbrace 0,1 \rbrace}^2\ket{i}=\frac12(\ket{00}+\ket{01}+\ket{{10}+\ket{11})$$

3. Ezután a fázisorákulumot alkalmazza a rendszer a következő lekéréshez:

   $$\ket{\text{register}}=\frac12(\ket{{00}-\ket{{01}+\ket{{10}+\ket{{11})$$

4. Ezután $H$ ismét minden qubiten a következőt adja:

   $$\ket{\text{12(\ket{{00}+\ket{{01}-\ket{{10}+\ket{{11})}}=\frac$$

5. Most a feltételes fázisváltás minden állapotra alkalmazva lesz, kivéve $\ket{00}$:

   $$\ket{\text{regisztrálása}}=\frac12(\ket{{00}-\ket{{01}+\ket{{10}-\ket{{11})$$

6. Végül az első Grover iteráció a következő $H$ ismételt alkalmazásával fejeződik be:

   $$\ket{\text{regiszter}}=\ket{{01}$$

A fenti lépések végrehajtásával az érvényes elem egyetlen iterációban található. Mint később látni fogja, ez azért van, mert az N=4 és egyetlen érvényes elem esetében az optimális számú alkalommal $N_{\text{optimális}}=1$.

Geometriai magyarázat

Annak érdekében, hogy lássuk, miért működik Grover algoritmusa, vizsgáljuk meg az algoritmust geometriai szempontból. Tegyük fel, hogy vannak $M$ érvényes megoldások, az összes kvantumállapot szuperpozíciója, amely nem megoldást a keresési problémára:

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

Az összes olyan állapot szuperpozíciója, amely megoldás a keresési problémára:

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

Mivel jó és rossz kölcsönösen kizáró készletek, mert egy elem nem lehet érvényes és nem érvényes, az állapotok ortogonálisak. Mindkét állapot alkotja a sík ortogonális alapját a vektortérben. Ez a sík az algoritmus vizualizációjára használható.

Tegyük fel, hogy $\ket{\psi}$ egy tetszőleges állapot, amely a jó$\ket{\text{ és }}$a rossz$\ket{\text{ síkon }}$él. A síkban élő bármely állapot a következőképpen fejezhető ki:

$$\ket{\psi} = \alpha \ket{\text{jó}} + \beta\ket{\text{rossz}}$$

ahol $\alpha$ és $\beta$ valós számok. Most mutatjuk be a tükrözési operátort $R_{\ket{\psi}}$, ahol $\ket{\psi}$ a síkban élő qubitállapotok találhatók. Az operátor a következőképpen van definiálva:

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

Azért nevezik visszaverődési operátornak $\ket{\psi}$ , mert geometriailag értelmezhető tükröződésként az irányát $\ket{\psi}$illetően. Ennek megtekintéséhez vegye figyelembe a sík orgonális alapját, amelyet $\ket{\psi}$ a(z) ^$\ket{\psi\perp{ ortogonális komplementerje }}$alkot. A sík bármely \xi$\ket{ állapota }$ilyen alapon bontható fel:

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

Ha egy R_ operátort ${\ket{\psi}}$ alkalmaz a következőre$\ket{: \xi}$:

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

Az operátor $R_{\ket{\psi}}$ átalakítja az összetevő ortogonálisát, $\ket{\psi}$ de változatlanul hagyja az összetevőt $\ket{\psi}$ . $Ezért R_{\ket{\psi}}$ tükrözi a $\ket{\psi}$.

Grover algoritmusa a H$ minden qubitre való $első alkalmazása után az összes állapot egységes szuperpozíciójával kezdődik. Ez a következőképpen írható:

$$\ket{\text{minden}}=\sqrt{\frac{M}{N}}\ket{\text{jó}} + \sqrt{\frac{N-M}{N}}\ket{\text{rossz}}$$

És így az állam a repülőn él. Vegye figyelembe, hogy az egyenlő szuperpozícióból való mérés esetén a helyes eredmény elérésének valószínűsége csak $|\bra{\text{jó}}\ket{\text{mind}}|^2=M/N$, ami egy véletlenszerű becsléstől elvárható.

Az oracle $O_f$ negatív fázist ad hozzá a keresési probléma megoldásához. Ezért a rossz$\ket{\text{ tengely tükröződéseként }}$írható:

$$O_f = R_{\ket{\text{rossz}}}= 2\ket{\text{rossz}}\bra{\text{rossz}} - \mathbb{}$$

Hasonlóképpen, a feltételes fázisváltás $O_0$ csak egy fordított tükröződés az állapotról $\ket{0}$:

$$O_{0}= R_{\ket{0}}= -2\ket{{0}\bra{{0} + \mathbb{}$$

Ennek ismeretében könnyen ellenőrizhető, hogy a Grover diffúziós művelet $-H^{\otimes n} O_{0} H^{\otimes n}$ is egy tükrözés az}$mind $\ket{állapotról. Csak tegye:

$$-H^{\otimes n} O_{{0} H^{\otimes n}=2H^{\otimes n}\ket{0}\bra{{0}H^{\otimes n} -H^{\otimes n}\mathbb{}H^{\otimes n}= 2\ket{\text{az összes}}\bra{\text{}} - \mathbb{}= R_{\ket{\text{az összes}}}$$

Bebizonyosodott, hogy a Grover-algoritmus minden iterációja két tükröződésből $áll, R_{\ket{\text{bad}}}$ és $R_{\ket{\text{all}}}$.

Az egyes Grover iterációk együttes hatása a 2\theta$ szög $óramutató járásával ellentétes irányban történő elforgatása. Szerencsére a szög $\theta$ könnyen megtalálható. Mivel $a \theta$ csak az összes$\ket{\text{ és }}$a rossz$\ket{\text{ közötti }}$szög, a skaláris termék használatával megtalálhatja a szöget. Ismert, hogy $a \cos{\theta}=\braket{\text{mind}|\text{rossz}}$, ezért minden$\braket{\text{rosszat}|\text{ ki kell számítani}}$. A rossz$\ket{\text{ és }}$a jó$\ket{\text{ szempontjából }}$az összes$\ket{\text{ felbontásából }}$a következő következik:

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

A regiszter állapota és a $\ket{\text{jó}}$ állapot közötti szög minden iterációval csökken, így nagyobb a valószínűsége az érvényes eredmény mérésének. Ennek a valószínűségnek a kiszámításához egyszerűen ki kell számítania $|\braket{\text{a helyes}|\text{^2}}| regisztert$. A $\ket{\text{jó}}$ és $\ket{\text{regiszter közötti szög}}$$\gamma (k)$, ahol $k$ az iterációk száma:

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

Ezért a siker valószínűsége a következő:

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

Az iterációk optimális száma

Mivel a siker valószínűsége az iterációk számának függvényeként írható, az iterációk $optimális száma N_{\text{optimális}}$ a legkisebb pozitív egész szám számításával, amely (körülbelül) maximalizálja a siker valószínűségi függvényét.

Ismert, hogy $a\sin^2{x}$ eléri az első$ x\pi=\frac{ maximális értékét}{2}$, így:

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

Ez a következőt nyújtja:

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

Ahol az utolsó lépésben $a \arccos \sqrt{1-x}=\sqrt{x} + O(x^{3/2}).$

Ezért választhat $N_{\text{optimális}}=\left\lfloor \frac{\pi}{{4}\sqrt{\frac{N}{M}}-\frac{{1}{{2}\right\r\floor$.

Összetettségi elemzés

Az előző elemzésből $az oracle \leftO_f\sqrt{\frac{ O}{(}}\rightN$M$)$ lekérdezéseire van szükség egy érvényes elem megtalálásához. Az algoritmus azonban hatékonyan implementálható az idő összetettsége szempontjából? $ $ O_0 n biten alapuló logikai műveletek számításán $$ alapul, és O(n)$ kapukkal $implementálható. A Hadamard kapuknak két rétege $$ is van. Mindkét összetevőnek ezért iterációnként csak $O(n)$ kapura van szüksége. Mivel $az N=2^n$, az O(n)O(log(N)$)= függvényt követi$. Ezért ha $az O\left(\sqrt{\frac{N}{M}}\right)$ iterációkra és $az O(log(N))$ kapukra van szükség iterációnként, a teljes idő összetettsége (az oracle implementációjának figyelembe vétele nélkül) $az O\left(\sqrt{\frac{N}{M}}log(N)\right)$.

Az algoritmus általános összetettsége végső soron az oracle $O_f$ implementálásának összetettségétől függ. Ha a függvények kiértékelése sokkal bonyolultabb egy kvantumszámítógépen, mint egy klasszikuson, akkor az általános algoritmus-futtatókörnyezet hosszabb lesz a kvantumesetben, bár technikailag kevesebb lekérdezést használ.

Hivatkozások

Ha folytatni szeretné a Grover-algoritmus megismerését, az alábbi források bármelyikét ellenőrizheti:

• Eredeti papír: Lov K. Grover
• Kvantumkeresési algoritmusok szakasza Nielsen, M. A. &Amp; Chuang, I. L. (2010). Kvantumszámítás és kvantuminformációk.
• Grover algoritmusa a Arxiv.org

Kapcsolódó tartalom

• Összefonódás a kvantum-számítástechnikában
• Vektorok és mátrixok
• T kapuk és T-gyárak
• Több qubit