Căutare nestructurată

Rezumat

Vom începe cu o descriere a problemei pe care o rezolvă algoritmul lui Grover. Ca de obicei, vom nota $\Sigma = \{0,1\}$ alfabetul binar pe parcursul acestei discuții.

Presupune că

$$f:\Sigma^n \rightarrow \Sigma$$

este o funcție de la șiruri binare de lungime $n$ la biți. Vom presupune că putem calcula această funcție eficient, dar altfel este arbitrară și nu ne putem baza pe faptul că are o structură specială sau o implementare specifică care să ne avantajeze.

Ce face algoritmul lui Grover este să caute un șir $x\in\Sigma^n$ pentru care $f(x) = 1.$ Vom numi astfel de șiruri soluții ale problemei de căutare. Dacă există mai multe soluții, atunci oricare dintre ele este considerată un răspuns corect, iar dacă nu există nicio soluție, un răspuns corect presupune să raportăm că nu există soluții.

Această sarcină este descrisă ca o problemă de căutare nestructurată deoarece nu ne putem baza pe faptul că $f$ are vreo structură particulară care să o facă ușoară. Nu căutăm într-o listă ordonată sau într-o structură de date concepută special pentru a facilita căutarea — practic căutăm un ac în carul cu fân.

Intuitiv vorbind, ne putem imagina că avem un circuit Boolean extrem de complicat care calculează $f,$ și putem rula ușor acest circuit pe un șir de intrare ales. Dar deoarece circuitul este atât de complicat, nu avem nicio șansă să înțelegem circuitul examinându-l (dincolo de capacitatea de a-l evalua pe șiruri de intrare alese).

O modalitate de a efectua această sarcină de căutare în mod clasic este să iterăm pur și simplu prin toate șirurile $x\in\Sigma^n,$ evaluând $f$ pe fiecare pentru a verifica dacă este sau nu o soluție. De acum înainte, să scriem

$$N = 2^n$$

pentru comoditate. Există $N$ șiruri în $\Sigma^n,$ deci iterarea prin toate necesită $N$ evaluări ale lui $f.$ Operând sub presupunerea că suntem limitați la evaluarea lui $f$ pe intrări alese, acesta este tot ce putem face cu un algoritm determinist dacă vrem să garantăm succesul. Cu un algoritm probabilistic, am putea spera să economisim timp alegând aleatoriu șiruri de intrare pentru $f,$ dar vom mai necesita $O(N)$ evaluări ale lui $f$ dacă vrem ca această metodă să reușească cu probabilitate mare.

Algoritmul lui Grover rezolvă această problemă de căutare cu probabilitate mare cu doar $O(\sqrt{N})$ evaluări ale lui $f.$ Pentru a fi clar, aceste evaluări ale funcției trebuie să se întâmple în superpoziție, similar cu algoritmii de interogare discutați în lecția Algoritmi cuantici de interogare, inclusiv algoritmul lui Deutsch, algoritmul Deutsch-Jozsa și algoritmul lui Simon. Spre deosebire de acei algoritmi, algoritmul lui Grover adoptă o abordare iterativă: evaluează $f$ pe superpoziții de șiruri de intrare și intercalează aceste evaluări cu alte operații care au efectul de a crea tipare de interferență, ducând la o soluție cu probabilitate mare (dacă una există) după $O(\sqrt{N})$ iterații.

Enunțul formal al problemei

Vom formaliza problema pe care o rezolvă algoritmul lui Grover folosind modelul de calcul prin interogare. Adică, vom presupune că avem acces la funcția $f:\Sigma^n\rightarrow\Sigma$ printr-un gate de interogare definit în mod obișnuit:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

pentru orice $x\in\Sigma^n$ și $a\in\Sigma.$ Aceasta este acțiunea lui $U_f$ pe stările bazei standard, iar acțiunea sa în general este determinată de liniaritate.

Așa cum s-a discutat în lecția Fundamente algoritmice cuantice, dacă avem un circuit Boolean pentru calcularea lui $f,$ putem transforma descrierea acelui circuit Boolean într-un circuit cuantic care implementează $U_f$ (folosind un număr de qubiți de lucru care încep și termină calculul în starea $\vert 0\rangle$). Deci, deși folosim modelul de interogare pentru a formaliza problema pe care o rezolvă algoritmul lui Grover, acesta nu este limitat la acest model; putem rula algoritmul lui Grover pe orice funcție $f$ pentru care avem un circuit Boolean.

Iată un enunț precis al problemei, care se numește Căutare deoarece căutăm o soluție, adică un șir $x$ care face ca $f$ să se evalueze la $1.$

Căutare

Intrare: o funcție $f:\Sigma^n\rightarrow\Sigma$
Ieșire: un șir $x\in\Sigma^n$ care satisface $f(x) = 1,$ sau „nicio soluție" dacă nu există niciun astfel de șir $x$

Observă că aceasta nu este o problemă cu promisiune — funcția $f$ este arbitrară. Va fi totuși util să considerăm următoarea variantă cu promisiune a problemei, unde ni se garantează că există exact o soluție. Această problemă a apărut ca exemplu de problemă cu promisiune în lecția Algoritmi cuantici de interogare.

Căutare unică

Intrare: o funcție de forma $f:\Sigma^n \rightarrow \Sigma$
Promisiune: există exact un șir $z\in\Sigma^n$ pentru care $f(z) = 1,$ cu $f(x) = 0$ pentru toate șirurile $x\neq z$
Ieșire: șirul $z$

De asemenea, observă că problema Or menționată în aceeași lecție este strâns legată de Căutare. Pentru acea problemă, scopul este pur și simplu să determinăm dacă există sau nu o soluție, spre deosebire de a găsi efectiv o soluție.