Groverov algoritam

Из Википедије, слободне енциклопедије
Иди на навигацију Иди на претрагу

Groverov algoritam je kvantni algoritam za pretraživanje nesortirane baze podataka sa N unosa u O(N1/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(N1/2) je asimptotski najbrža moguća za pretraživanje nesortirane baze podataka u kvantnom modelu.[1] 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=log2 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:

Naš cilj je da identifikujemo indeks .

Koraci algoritma[уреди]

Kvantno kolo Reprezentacija Groverovog algoritma

Koraci Groverovog algoritma su sledeći: Neka je uniformna superpozicija svih stanja

.

Tada je operator

poznat kao Groverov difuzioni operator.

Evo algoritma:

  1. Inicijalizacija sistema u stanje
  2. Primeniti sledeće "Groverove iteracije" r(N) puta. Funkcija r(N), koja je asimptotski O(N½), opisana je dole.
    1. Primeniti operator .
    2. Primeniti operator .
  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

,

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

.

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

.
za sve .

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

.
.
.
.

Posle primene dva operatora ( and ), amplituda traženog elementa je opala od do .

Opis [уреди]

Groverovom algoritmu je potreban operator "kvantnog odlučivanja" 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 koja vraća ako je rešenje traženog problema i u suprotnom. Odlučivanje je linearni operator koji deluje na dva kjubita, indeks kjubit i kjubit odlučivanja :

Kao i obično, označava sabiranje po modulu 2. Operacija menja kjubit odlučivanja ako ili ga u suprotnom ostavlja nepromenjenog. U Groverovom algoritmu želimo da promenimo znak stanja ako obeležava rešenje. Ovo je postignuto postavljanjem kjubita pretraživanja u stanje , koje je promenjeno na ako je rešenje:

Razmatramo 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 jednostavno napisana kao:

Geometrijski dokaz korektnosti[уреди]

Slika prikazuje geometrijsku reprezentaciju prve iteracije Groverovog algoritma. Vektor stanja je rotiran ka ciljnom vektoru as shown.

Posmatrajmo ravan razapetu sa i , gde je ket u podprostoru normalan na . Posmatraćemo prvu iteraciju, koja ce ponaša kao inicijalni ket . Pošto je jedan od baznih vektora u preklapanje je

Na geometrijskom jeziku, ugao između i je dat kao:

Operator je refleksija na hiperravan ortogonalnu na za vektore u ravni razapete sa i ; npr. ponaša se kao refleksija preko . Operator je refleksija kroz . Prema tome, vektor stanja ostaje u ravni razapetoj sa i posle svake primene operatora i , i jednostavno je proveriti da operator svake Groverove iteracije rotira vektor stanja za ugao .

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

gde jer (ceo) broj Groverovih iteracija. Najranije gde dobijamo meru blizu optimalne je prema tome .

Algebarski dokaz korektnosti[уреди]

Da bismo obavili algebarsku analizu potrebno je da otkrijemo šta se događa kada više puta primenimo . 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 i . Možemo napisati dejstvo od i u normalnom prostoru razapetom sa kao:

Tako da u bazi (koja nije ni ortogonalna niti baza celokupnog prostora) dejstvo primene praćeno sa dato je matricom

Ispada da je ova matrica veoma zgodna Žordanova forma. Ako orijentišemo , to je

gde je

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

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

.

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 or . Tada je sistem u stanju

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 πN1/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

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

što je i dalje O(N1/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 upita. Ova činjenica se može iskoristiti za rešavanje problema kolizija.,[2][3]

Parcijalna kvantna pretraga[уреди]

Modifikaciju Groverovog algoritm,a nazvanu parcijalna kvantna pretraga, Opisali su Grover i Radhakrišnan 2004. godine[4] 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 blokova, od kojih je svaki veličine . 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 do .

Groverovom algoritmu je potrebno iteracija. Parcijalna pretraga će biti brža za numerički faktor koji zavisi od broja blokova . Parcijalna pretraga koristi globalnih iteracija lokalnih iteracija. Globalni Groverov operator je označen sa dok je lokalni Groverov operator označen sa .

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

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

Optimalne vrednosti i 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.[1] Ovaj rezultat je bitan za razumevanje ograničenja kvantnog izračunavanja. Da je problem Groverove pretrage rešiv za logc 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.[2]

Reference[уреди]

  1. 1,0 1,1 Bennett C.H., Bernstein E., Brassard G., Vazirani U., The strengths and weaknesses of quantum computation. SIAM Journal on Computing 26(5): 1510-1523 (1997). Shows the optimality of Grover's algorithm.
  2. 2,0 2,1 Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp (1998), Fortsch. Phys., 46: 493—506, arXiv:quant-ph/9605034Слободан приступ  Недостаје или је празан параметар |title= (помоћ)
  3. ^ Andris Ambainis (2004), „Quantum search algorithms”, SIGACT News, 35 (2): 22—35, arXiv:quant-ph/0504012Слободан приступ 
  4. ^ L.K. Grover and J. Radhakrishnan,Is partial quantum search of a database any easier?. quant-ph/0407122

Literatura[уреди]

Spoljašnje veze[уреди]