Algoritmul lui Grover

Algoritmul lui Grover (de asemenea GSA din engleză.  Algoritmul de căutare Grover ) este un algoritm cuantic pentru rezolvarea problemei de enumerare, adică găsirea unei soluții la ecuație

unde este o funcție booleană a n variabile. [1] A fost propus de matematicianul american Lov Grover în 1996 .

Se presupune că funcția este dată sub forma unei cutii negre sau a unui oracol , adică în cursul rezolvării, puteți adresa oracolului doar o întrebare de genul: „cu ce este egal pe aceasta ?” , și folosiți răspunsul în calcule ulterioare. Adică, sarcina de a rezolva ecuația (1) este o formă generală a problemei forței brute: aici este necesar să se găsească „parola pentru dispozitiv ”, care necesită în mod clasic o enumerare completă a tuturor opțiunilor.

Algoritmul lui Grover găsește o rădăcină a unei ecuații folosind apeluri de funcții folosind qubiți . [2]

Scopul algoritmului lui Grover este de a „ crește amplitudinea ” a stării țintă prin scăderea amplitudinii tuturor celorlalte stări. Geometric, algoritmul lui Grover constă în rotirea vectorului de stare curentă al computerului cuantic în direcția exactă către starea țintă (deplasarea pe calea cea mai scurtă asigură optimitatea algoritmului lui Grover). Fiecare pas dă o rotație cu un unghi , unde unghiul dintre și este . Continuarea ulterioară a iterațiilor operatorului G va da o continuare a circumnavigării cercului în planul real generat de acești vectori.

„Amplificarea amplitudinii” lui Grover pare a fi un fenomen fizic fundamental în teoria cuantică a mai multor corpuri. De exemplu, este necesar să se țină seama de el pentru a estima probabilitățile unor evenimente care par „rare”. Procesul care implementează schema algoritmului Grover duce la o creștere explozivă de o amplitudine inițial neglijabilă, care o poate aduce rapid la valori cu adevărat observabile.

Algoritmul lui Grover poate fi folosit și pentru a găsi mediana și media aritmetică a unei serii de numere. În plus, poate fi folosit pentru a rezolva probleme NP-complete prin căutarea exhaustivă printre setul de soluții posibile. Acest lucru poate duce la câștiguri semnificative de viteză față de algoritmii clasici, deși fără a oferi o „ soluție polinomială ” în termeni generali.

Descriere

Să existe un operator unitar care oglindește spațiul Hilbert față de hiperplanul perpendicular pe vectorul , este starea corespunzătoare rădăcinii ecuației (1), este o suprapunere uniformă a tuturor stărilor.

Algoritmul lui Grover constă în aplicarea operatorului stării de un număr de ori egal cu partea întreagă a lui . Rezultatul aproape se va potrivi cu statul . Măsurând starea obținută, obținem un răspuns cu o probabilitate apropiată de unu.

Note

Să presupunem că ecuația (1) are rădăcini. Algoritmul clasic pentru rezolvarea unei astfel de probleme ( căutare liniară ) necesită evident apeluri la pentru a rezolva problema cu probabilitate . Algoritmul lui Grover vă permite să rezolvați problema de căutare în timp , adică ordinea rădăcinii pătrate a celei clasice, care este o accelerare uriașă. Se dovedește că algoritmul lui Grover este optim în următoarele privințe:

• Constanta nu poate fi îmbunătățită [3] .
• Nu se poate obține o accelerație cuantică mai mare decât cea pătratică [4] .

Algoritmul lui Grover este un exemplu de problemă de masă dependentă de oracol . Pentru probleme mai particulare, este posibil să se obțină o accelerație cuantică mai mare. De exemplu, algoritmul de factorizare Shor oferă un câștig exponențial în comparație cu algoritmii clasici corespunzători.

Faptul că f este dat ca o cutie neagră nu afectează complexitatea atât a algoritmilor cuantici, cât și a celor clasici în cazul general. Cunoașterea „dispozitivului” funcției f (de exemplu, cunoașterea circuitului care îl definește din elemente funcționale) în cazul general nu poate ajuta la rezolvarea ecuației (1). Căutarea într-o bază de date se referă la apelarea unei funcții care ia o anumită valoare dacă argumentul x se potrivește cu intrarea căutată în baza de date.

Algoritmi care folosesc schema lui Grover

• Algoritm pentru căutarea extremului unei funcții întregi (P. Hoyer și alții). Se caută cea mai mare valoare a funcției . Algoritmul cuantic găsește maximul în f .
• Algoritmul de căutare structurală (Farhi, Gutman). Se caută soluția ecuației (1) cu condiția suplimentară , unde este împărțirea șirului în două șiruri de aceeași lungime. Algoritmul are o complexitate de ordinul rădăcinii pătrate a timpului clasic.
• Algoritm pentru găsirea șirurilor de caractere potrivite într-o bază de date (Ambainis). Se caută o pereche de argumente diferite , pe care funcția ia aceeași valoare. Algoritmul necesită apeluri la f .

Variații și generalizări

• Fie Hamiltonianul unui sistem cuantic să aibă forma , unde și sunt operatorii și, respectiv. Apoi evoluția unitară continuă cu Hamiltonianul , pornind de la , duce în mod firesc la . Complexitatea unui astfel de analog continuu al algoritmului lui Grover este exact aceeași ca și pentru cazul discret.
• O versiune adiabatică a algoritmului lui Grover . Evoluţia lentă a stării fundamentale a tipului sub acţiunea unui hamiltonian în funcţie de f , conform teoremei adiabatice , pe un timp de ordin duce la starea .

Note

1. ↑ GSA este uneori denumită în mod incorect căutarea bazei de date .
2. ↑ Complexitatea algoritmului, pentru sarcina cu oracolul se mai numește și timpul lucrului său, este determinată de numărul de apeluri către oracol.
3. ↑ Christof Zalka, algoritmul de căutare cuantică al lui Grover este optim, Phys.Rev. A60 (1999) 2746-2751 [1]  (link nu este disponibil)
4. ↑ Yuri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc. Roy. Soc. Londra. A455 (1999) 2165-2172 [2]

Link -uri

• Grover L.K. Mecanica cuantică ajută la găsirea unui ac într-un car de fân (descărcare)
• Algoritmul cuantic al lui Loginov O. V. și Tsyganov A. V. Grover, Universitatea de Stat din Sankt Petersburg
• Texte sursă pentru un simulator de computer cuantic în C++ și implementări ale algoritmului lui Grover cu o descriere detaliată și diagrame ale porților cuantice