Groverov algoritam

Groverov algoritam je kvantni algoritam za pretraživanje nesortirane baze podataka sa N unosa u O(N^1/2) vremenu koristeći O(log N) memorijskog prostora (videti veliko O). Lov Grover ga je formulisao 1996.

U modelima klasičnog izračunavanja, pretraživanje i sortiranje nesortirane baze podataka ne može biti ostvareno za manje od linearnog vremena (tako da je pretraživanje elemenata član - po - član skoro optimalno). Groverov algoritam ilustruje da u kvantnom modelu pretraga može biti izvršena brže od ovoga; to jest, njegova vremenska složenost O(N^1/2) je asimptotski najbrža moguća za pretraživanje nesortirane baze podataka u kvantnom modelu. Pruža kvadratno poboljšanje, za razliku od drugih kvantnih algoritama, koji pružaju eksponencijalno poboljšanje u odnosu na njihove klasične alternative. Ipak, čak je i kvadratno poboljšanje značajno kada je N veliko.

Kao i mnogi drugi kvantni algoritmi, Groverov algoritam je probabilistički u smislu da daje tačan rezultat sa visokim procentom verovatnoće. Verovatnoća pojave greške može biti smanjena ponavljanjem algoritma. (Primer determinističkog kvantnog algoritma je Deutsch-Jozsa algorithm, koji uvek daje tačan odgovor.)

Primene

Iako se svrha Groverovog algoritma najčeće opisuje kao "pretraživanje baze podataka", moće biti tačnije opisati je kao "inverzija funkcije". Grubo rečeno, ako imamo funkciju y=f(x) koja može biti evaluirana na kvantnom računaru, ovaj algoritam nam dozvoljava da izračunamo x kada je dato y. Inverzija funkcije je povezana sa pretragom baze podataka tako što bismo mogli doći do funkcije koja daje tačnu vrednost y ako se x poklapa sa željenim unosom u bazu, i još jednu vrednost y za ostale vrednosti x.

Groverov algoritam se takođe može koristiti za određivanje središta i medijane skupa brojeva, i za rešavanje problema kolizije. Algoritam se može dalje optimizovati ako postoji više od jednog traženog unosa i traženi broj unosa je unapred poznat.

Postavka

Uzmimo nesortiranu bazu podataka sa N unosa. Algoritmu je potreban N-dimenzionalni statusni prostor H, koji može biti obezbeđen sa n=log₂ N kjubita. Uzimajući u obzir problem određivanja indeksa unosa baze podataka koji zadovoljava neki postavljeni uslov. Neka je f funkcija koja označava unose baze podataka sa 0 ili 1, gde je f(ω)=1 ako i samo ako ω zadovoljava traženi uslov. Dostupan nam je (preko kvantne crne kutije) pristup ka podproblemu u obliku linearnog operatora, U_ω, koji se ponaša kao:

$U_{\omega }|\omega ⟩=-|\omega ⟩$

$U_{\omega }|x⟩=|x⟩\text{za svako}x\ne \omega$

Naš cilj je da identifikujemo indeks $|\omega ⟩$.

Koraci algoritma

Kvantno kolo Reprezentacija Groverovog algoritma

Koraci Groverovog algoritma su sledeći: Neka je $|s⟩$ uniformna superpozicija svih stanja

$|s⟩=\frac{1}{\sqrt{N}}\sum _{x=1}^N|x⟩$.

Tada je operator

$U_s=2|s⟩⟨s|-I$

poznat kao Groverov difuzioni operator.

Evo algoritma:

1. Inicijalizacija sistema u stanje

   $|s⟩=\frac{1}{\sqrt{N}}\sum _{x=1}^N|x⟩$

2. Primeniti sledeće "Groverove iteracije" r(N) puta. Funkcija r(N), koja je asimptotski O(N^½), opisana je dole.
   1. Primeniti operator $U_{\omega }$.
   2. Primeniti operator $U_s$.
3. Primeniti merenje Ω. Rezultati merenja će biti λ_ω sa verovatnoćom koja se približava 1 za N≫1. Iz λ_ω, se može dobiti ω.

Prva iteracija

Preliminarna observacija, paralelna sa našom definicijom

$U_s=2|s⟩⟨s|-I$,

je da U_ω može biti izraženo na alternativni način:

$U_{\omega }=I-2|\omega ⟩⟨\omega |$.

Da bismo ovo dokazali dovoljno je proveriti kako se U_ω ponaša u baznim stanjima:

$(I-2|\omega ⟩⟨\omega |)|\omega ⟩=|\omega ⟩-2|\omega ⟩⟨\omega |\omega ⟩=-|\omega ⟩=U_{\omega }|\omega ⟩$.

$(I-2|\omega ⟩⟨\omega |)|x⟩=|x⟩-2|\omega ⟩⟨\omega |x⟩=|x⟩=U_{\omega }|x⟩$ za sve $x\ne \omega$.

Sledeća izračunavanja pokazuju šta se događa u prvoj iteraciji:

$⟨\omega |s⟩=⟨s|\omega ⟩=\frac{1}{\sqrt{N}}$.

$⟨s|s⟩=N\frac{1}{\sqrt{N}}\cdot \frac{1}{\sqrt{N}}=1$.

$U_{\omega }|s⟩=(I-2|\omega ⟩⟨\omega |)|s⟩=|s⟩-2|\omega ⟩⟨\omega |s⟩=|s⟩-\frac{2}{\sqrt{N}}|\omega ⟩$.

$U_s(|s⟩-\frac{2}{\sqrt{N}}|\omega ⟩)=(2|s⟩⟨s|-I)(|s⟩-\frac{2}{\sqrt{N}}|\omega ⟩)=2|s⟩⟨s|s⟩-|s⟩-\frac{4}{\sqrt{N}}|s⟩⟨s|\omega ⟩+\frac{2}{\sqrt{N}}|\omega ⟩=$

$=2|s⟩-|s⟩-\frac{4}{\sqrt{N}}\cdot \frac{1}{\sqrt{N}}|s⟩+\frac{2}{\sqrt{N}}|\omega ⟩=|s⟩-\frac{4}{N}|s⟩+\frac{2}{\sqrt{N}}|\omega ⟩=\frac{N-4}{N}|s⟩+\frac{2}{\sqrt{N}}|\omega ⟩$.

Posle primene dva operatora ($U_{\omega }$ and $U_s$ ), amplituda traženog elementa je opala od ${|⟨\omega |s⟩|}^2=1/N$ do ${|⟨\omega |U_s{U}_{\omega }s⟩|}^2\approx 9/N$.

Opis $U_{\omega }$

Groverovom algoritmu je potreban operator "kvantnog odlučivanja" $U_{\omega }$ Koji prepoznaje rešenja traženog problema i daje im negativan znak. Da bismo održali algoritam pretrage opštim, ostavićemo unutrašnja dešavanja odlučivanja kao crnu kutiju, ali ćemo objasniti kako je znak promenjen. Odlučivanje sadrži funkciju $f$ koja vraća $f(x)=1$ ako je $|x⟩$ rešenje traženog problema i $f(x)=0$ u suprotnom. Odlučivanje je linearni operator koji deluje na dva kjubita, indeks kjubit $|x⟩$ i kjubit odlučivanja $|q⟩$:

$|x⟩|q⟩\stackrel{U_{\omega }}{⟶}|x⟩|q\oplus f(x)⟩$

Kao i obično, $\oplus$ označava sabiranje po modulu 2. Operacija menja kjubit odlučivanja ako $f(x)=1$ ili ga u suprotnom ostavlja nepromenjenog. U Groverovom algoritmu želimo da promenimo znak stanja $|x⟩$ ako obeležava rešenje. Ovo je postignuto postavljanjem kjubita pretraživanja u stanje $(|0⟩-|1⟩)/\sqrt{2}$, koje je promenjeno na $(|1⟩-|0⟩)/\sqrt{2}$ ako je $|x⟩$ rešenje:

$|x⟩(|0⟩-|1⟩)/\sqrt{2}\stackrel{U_{\omega }}{⟶}(-1{)}^{f(x)}|x⟩(|0⟩-|1⟩)/\sqrt{2}$

Razmatramo $|x⟩$ kao promenjeno, pošto kjubit odlučivanja nije promenjen, pa po konvenciji kjubiti odlučivanja obično nisu pomenuti u opisu Groverovog algoritma. Mada je operacija odlučivanja $U_{\omega }$ jednostavno napisana kao:

$|x⟩\stackrel{U_{\omega }}{⟶}(-1{)}^{f(x)}|x⟩$

Geometrijski dokaz korektnosti

Slika prikazuje geometrijsku reprezentaciju prve iteracije Groverovog algoritma. Vektor stanja $|s⟩$ je rotiran ka ciljnom vektoru $|\omega ⟩$ as shown.

Posmatrajmo ravan razapetu sa $|s^{\prime }⟩$ i $|\omega ⟩$, gde je $|s^{\prime }⟩$ ket u podprostoru normalan na $|\omega ⟩$. Posmatraćemo prvu iteraciju, koja ce ponaša kao inicijalni ket $|s⟩$. Pošto je $|\omega ⟩$ jedan od baznih vektora u $|s⟩$ preklapanje je

$⟨s^{\prime }|s⟩=\sqrt{\frac{N-1}{N}}$

Na geometrijskom jeziku, ugao $\theta /2$ između $|s⟩$ i $|s^{\prime }⟩$ je dat kao:

$\sin \theta /2=\frac{1}{\sqrt{N}}$

Operator $U_{\omega }$ je refleksija na hiperravan ortogonalnu na $|\omega ⟩$ za vektore u ravni razapete sa $|s^{\prime }⟩$ i $|\omega ⟩$; npr. ponaša se kao refleksija preko $|s^{\prime }⟩$. Operator $U_s$ je refleksija kroz $|s⟩$. Prema tome, vektor stanja ostaje u ravni razapetoj sa $|s^{\prime }⟩$ i $|\omega ⟩$ posle svake primene operatora $U_s$ i $U_{\omega }$, i jednostavno je proveriti da operator $U_s{U}_{\omega }$ svake Groverove iteracije rotira vektor stanja za ugao $\theta =2\arcsin \frac{1}{\sqrt{N}}$.

Potrebno je da stanemo kada vektor stanja prođe blizu $|\omega ⟩$; nakon ovoga, poditeracije rotiraju vektor stanja dalje od $|\omega ⟩$, umanjujući verovatnoću dobijanja tačnog odgovora. Tačna verovatnoća tačnosti odgovora je:

${\sin }^2\left((r+\frac{1}{2})\theta \right)$

gde jer (ceo) broj Groverovih iteracija. Najranije gde dobijamo meru blizu optimalne je prema tome $r\approx \pi \sqrt{N}/4$.

Algebarski dokaz korektnosti

Da bismo obavili algebarsku analizu potrebno je da otkrijemo šta se događa kada više puta primenimo $U_s{U}_{\omega }$. Prirodan način da se ovo učini je pomoću analize sopstvenih vrednosti matrice. Primetimo da tokom celokupnog izračunavanja, stanje algoritma je linearna kombinacija $s$ i $\omega$. Možemo napisati dejstvo od $U_s$ i $U_{\omega }$ u normalnom prostoru razapetom sa $\{|s⟩,|\omega ⟩\}$ kao:

$U_s:a|\omega ⟩+b|s⟩\mapsto (|\omega ⟩|s⟩)\left(\begin{array}{cc}-1& 0\\ 2/\sqrt{N}& 1\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right).$

$U_{\omega }:a|\omega ⟩+b|s⟩\mapsto (|\omega ⟩|s⟩)\left(\begin{array}{cc}-1& -2/\sqrt{N}\\ 0& 1\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right).$

Tako da u bazi $\{|\omega ⟩,|s⟩\}$ (koja nije ni ortogonalna niti baza celokupnog prostora) dejstvo $U_s{U}_{\omega }$ primene $U_{\omega }$ praćeno sa $U_s$ dato je matricom

$U_s{U}_{\omega }=\left(\begin{array}{cc}-1& 0\\ 2/\sqrt{N}& 1\end{array}\right)\left(\begin{array}{cc}-1& -2/\sqrt{N}\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}1& 2/\sqrt{N}\\ -2/\sqrt{N}& 1-4/N\end{array}\right).$

Ispada da je ova matrica veoma zgodna Žordanova forma. Ako orijentišemo $t=\arcsin (1/\sqrt{N})$, to je

$U_s{U}_{\omega }=M\left(\begin{array}{cc}\exp (2it)& 0\\ 0& \exp (-2it)\end{array}\right)M^{-1}$ gde je $M=\left(\begin{array}{cc}-i& i\\ \exp (it)& \exp (-it)\end{array}\right).$

Ispostavlja se da je r-ti stepen matrice (U odnosu na r iteracija)

$(U_s{U}_{\omega }{)}^r=M\left(\begin{array}{cc}\exp (2rit)& 0\\ 0& \exp (-2rit)\end{array}\right)M^{-1}$

Korišćenjem ove forme možemo koristiti trigonometrijske identitete kako bismo izračunali verovatnoću posmatrajući ω nakon r iteracija pomenutih u prethodnom odeljku,

${|\left(\begin{array}{cc}⟨\omega |\omega ⟩& ⟨\omega |s⟩\end{array}\right)(U_s{U}_{\omega }{)}^r\left(\begin{array}{c}0\\ 1\end{array}\right)|}^2={\sin }^2((2r+1)t)$.

Alternativno, neko sa pravom može pomisliti da bi vreme blizu optimalnog za razlikovanje bilo kada su uglovi 2rt and -2rt udaljeni najdalje moguće, što je u vezi sa $2rt\approx \pi /2$ or $r=\pi /4t=\pi /4\arcsin (1/\sqrt{N})\approx \pi \sqrt{N}/4$. Tada je sistem u stanju

$(|\omega ⟩|s⟩)(U_s{U}_{\omega }{)}^r\left(\begin{array}{c}0\\ 1\end{array}\right)\approx (|\omega ⟩|s⟩)M\left(\begin{array}{cc}i& 0\\ 0& -i\end{array}\right)M^{-1}\left(\begin{array}{c}0\\ 1\end{array}\right)=|w⟩\frac{1}{\cos (t)}-|s⟩\frac{\sin (t)}{\cos (t)}.$

Sada kratko izračunavanje pokazuje da observacija doprinosi tačnom odgovoru ω sa greškom O(1/N).

Proširenje prostora za višestruke pogotke

Ako, umesto jednog traženog unosa, postoji k unosa koji odgovaraju, isti algoritam važi, ali broj iteracija mora biti π(N/k)^1/2/4 umesto πN^1/2/4. Postoji nekoliko načina da se suočimo sa slučajem kada je k nepoznato. Na primer, jedan može primeniti Groverov algoritam nekoliko puta, sa

$\pi \frac{N^{1/2}}{4},\pi \frac{(N/2{)}^{1/2}}{4},\pi \frac{(N/4{)}^{1/2}}{4},\dots$

iteracija. Za proizvoljno k, jedna od iteracija će pronaći traženi unos sa dovoljno visokom verovatnoćom. Ukupan broj iteracija je najviše

$\pi \frac{N^{1/2}}{4}(1+\frac{1}{\sqrt{2}}+\frac{1}{2}+\cdots )$

što je i dalje O(N^1/2). Može se pokazati da ovo može biti unapređeno. Ako je broj označenih pojmova k, gde je k nepoznato, postoji algoritam koji nalazi rešenje za $\sqrt{N/k}$ upita. Ova činjenica se može iskoristiti za rešavanje problema kolizija.,

Parcijalna kvantna pretraga

Modifikaciju Groverovog algoritm,a nazvanu parcijalna kvantna pretraga, opisali su Grover i Radhakrišnan 2004. godine I parcijalnoj pretrazi, nismo zainteresovani za pronalaženje tačne adrese traženog pojma, samo nekoliko prvih cifara adrese. Ekvivalentno, možemo to posmatrati kao "seckanje" prostora obuhvaćenog pretragom u blokove, i onda pitati "u kom bloku se nalazi traženi pojam?". U mnogim primenama, ovakva pretraga doprinosi dovoljno informacija ako ciljna adresa sadrži traženu informaciju. Kako bismo to pokazali, koristićemo primer dat od strane L.K. Grovera, ako imamo listu studenata uređenu po proseku ocena, možemo biti zainteresovani samo da li je student u donjem 25%, 25-50%, 50-70% ili 75-100% procentu.

Da bismo opisali parcijalnu pretragu, koristićemo bazu podataka podeljenu na $K$ blokova, od kojih je svaki veličine $b=N/K$. Očigledno, problem parcijalne pretrage je jednostavniji. Razmotrimo klasičan pristup - odaberemo nasumično jedan blok, pa zatim primenimo uobičajenu pretragu kroz ostatak blokova (na jeziku teorije skupova language, komplement). Ukoliko ne pronađemo traženi pojam, znaćemo da nije u bloku u kome smo tražili. Prosečan broj iteracija kreće se od $N/2$ do $(N-b)/2$.

Groverovom algoritmu je potrebno $\pi /4\sqrt{N}$ iteracija. Parcijalna pretraga će biti brža za numerički faktor koji zavisi od broja blokova $K$. Parcijalna pretraga koristi $n_1$ globalnih iteracija $n_2$ lokalnih iteracija. Globalni Groverov operator je označen sa $G_1$ dok je lokalni Groverov operator označen sa $G_2$.

Globalni Groverov operator deluje na blokove. Specijalno, dat je kao:

1. Primeniti $j_1$ standardnih Groverovih iteracija na celokupnu bazu.
2. Primeniti $j_2$ lokalnih Groverovih iteracija. Lokalna Groverova iteracija je direktna suma Groverovih iteracija i svakog bloka.
3. Primeniti jednu standatdnu Groverovu iteraciju

Optimalne vrednosti $j_1$ i $j_2$ su razmotrene u članku Grovera i Radhakrišnana. Neko se može zapitati šta se dešava ako se primeni uzastopna parcijalna pretraga na različitim nivoima "rezolucije". Ova ideja je detaljno proučena od strane Korepina and Ksua, koji su je nazvali kvantno binarno stablo pretrage. Dokazali su da da nije brža u odnosu na primenu jedne parcijalne pretrage.

Optimalnost

Poznato je da je Groverov algoritam optimalan. Što će reći, bilo koji algoritam koji pristupa bazi podataka korišćenjem samo operatora U_ω mora primeniti U_ω najmanje onoliko puta koliko i Groverov algoritam. Ovaj rezultat je bitan za razumevanje ograničenja kvantnog izračunavanja. Da je problem Groverove pretrage rešiv za log^c N primenom U_ω, iz toga bi sledilo da je klasa NP sadržana u BQP, svođenjem problema iz NP na probleme tipa Groverove pretrage. Optimalnost Groverovog algoritma nalaže (ali ne dokazuje) da klasa NP nije sadržana u BQP.

Broj iteracija za k pronađenih pogodaka, π(N/k)^1/2/4, je takođe optimalan.

Literatura

• Шаблон:Cite journal
• Шаблон:Cite journal
• Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
• What's a Quantum Phone Book?, Lov Grover, Lucent Technologies
• Шаблон:Cite journal
• Grover's algorithm on arxiv.org

Spoljašnje veze

• -{Grover's Algorithm Шаблон:Wayback simulation and circuit diagram.}-
• -{Grover’s Quantum Search Algorithm Шаблон:Wayback animated explanation.}-
• -{Simulation and circuit diagram with cats}-