Hindi nakaayos na paghahanap

Buod

Magsisimula tayo sa paglalarawan ng problema na nireresolta ng algorithm ni Grover. Tulad ng dati, itatatakda natin ang $\Sigma = \{0,1\}$ bilang binary alphabet sa buong talakayan na ito.

Ipagpalagay na ang

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

ay isang function mula sa mga binary string na may haba $n$ patungo sa mga bit. Ipagpalagay natin na kaya nating kalkulahin ang function na ito nang mahusay, ngunit bukod doon ay arbitrary ito at hindi natin maaasahan na may espesyal na estruktura ito o isang partikular na implementasyon na angkop sa ating pangangailangan.

Ang ginagawa ng algorithm ni Grover ay maghanap ng string $x\in\Sigma^n$ kung saan $f(x) = 1.$ Tatawagin natin ang mga ganitong string na solusyon sa problema ng paghahanap. Kung mayroong maraming solusyon, ang alinman sa mga ito ay itinuturing na tamang output, at kung walang solusyon, ang tamang sagot ay nangangailangan na iulat natin na walang solusyon.

Ang gawaing ito ay tinatawag na problema ng hindi nakaayos na paghahanap dahil hindi natin maaasahan na ang $f$ ay may anumang partikular na estruktura para maging madali ito. Hindi tayo naghahanap sa isang ordered na listahan, o sa loob ng ilang data structure na espesyal na dinisenyo para mapadali ang paghahanap — sa esensya ay naghahanap tayo ng karayom sa isang mandala ng dayami.

Sa intuitive na pagsasalita, maaari nating isipin na mayroon tayong isang napaka-komplikadong Boolean circuit na nagkakalkula ng $f,$ at madali nating maaaring patakbuhin ang circuit na ito sa isang napiling input string kung gusto natin. Ngunit dahil napakacomplex ng circuit, wala tayong pagkakataon na maunawaan ito sa pamamagitan ng pagsusuri nito (bukod sa kakayahang suriin ito sa mga napiling input string).

Isang paraan para isagawa ang gawaing paghahanap na ito nang klasikal ay ang simpleng pag-ulit sa lahat ng string $x\in\Sigma^n,$ sinusuri ang $f$ sa bawat isa para malaman kung ito ay solusyon o hindi. Mula rito, isulat natin ang

$$N = 2^n$$

para sa kaginhawaan. Mayroong $N$ na mga string sa $\Sigma^n,$ kaya ang pag-ulit sa lahat ng mga ito ay nangangailangan ng $N$ na evaluations ng $f.$ Sa ilalim ng pagpapalagay na limitado tayo sa pag-evaluate ng $f$ sa mga napiling input, ito ang pinakamahusay na magagawa natin sa isang deterministic na algorithm kung gusto nating garantiyahan ang tagumpay. Sa isang probabilistic na algorithm, maaari tayong umasa na makatipid ng oras sa pamamagitan ng random na pagpili ng mga input string para sa $f,$ ngunit kakailanganin pa rin natin ng $O(N)$ na evaluations ng $f$ kung gusto nating mabigyan ng mataas na probabilidad ng tagumpay ang paraang ito.

Nireresolta ng algorithm ni Grover ang problema ng paghahanap na ito nang may mataas na probabilidad gamit lamang ang $O(\sqrt{N})$ na evaluations ng $f.$ Para maging malinaw, ang mga function evaluation na ito ay dapat na mangyari sa superposition, katulad ng mga query algorithm na tinalakay sa aralin na Quantum query algorithms, kabilang ang algorithm ni Deutsch, ang Deutsch-Jozsa algorithm, at ang algorithm ni Simon. Hindi tulad ng mga algorithm na iyon, ang algorithm ni Grover ay gumagamit ng iterative na diskarte: sinusuri nito ang $f$ sa mga superposition ng mga input string at inihahalo ang mga evaluations na ito sa iba pang mga operasyon na nagdudulot ng mga interference pattern, na nagreresulta sa isang solusyon nang may mataas na probabilidad (kung mayroon) pagkatapos ng $O(\sqrt{N})$ na iterations.

Pormal na pahayag ng problema

Ipopormal natin ang problema na nireresolta ng algorithm ni Grover gamit ang query model ng computation. Ibig sabihin, ipagpalagay nating mayroon tayong access sa function $f:\Sigma^n\rightarrow\Sigma$ sa pamamagitan ng isang query gate na tinutukoy sa karaniwang paraan:

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

para sa bawat $x\in\Sigma^n$ at $a\in\Sigma.$ Ito ang aksyon ng $U_f$ sa mga standard basis state, at ang aksyon nito sa pangkalahatan ay tinutukoy ng linearidad.

Tulad ng tinalakay sa aralin na Quantum algorithmic foundations, kung mayroon tayong Boolean circuit para sa pagkalkula ng $f,$ maaari nating i-transform ang deskripsiyon ng Boolean circuit na iyon sa isang quantum circuit na nagpapatupad ng $U_f$ (gamit ang ilang bilang ng workspace qubits na nagsisimula at nagtatapos ng computation sa estado na $\vert 0\rangle$). Kaya, kahit gumagamit tayo ng query model para ipormal ang problema na nireresolta ng algorithm ni Grover, hindi ito limitado sa modelong ito; maaari nating patakbuhin ang algorithm ni Grover sa anumang function $f$ na mayroon tayong Boolean circuit.

Narito ang isang tumpak na pahayag ng problema, na pinangalanang Search dahil naghahanap tayo ng solusyon, ibig sabihin ang isang string $x$ na nagdudulot sa $f$ na mag-evaluate sa $1.$

Search

Input: isang function $f:\Sigma^n\rightarrow\Sigma$
Output: isang string $x\in\Sigma^n$ na nagsasatisfy ng $f(x) = 1,$ o "walang solusyon" kung walang ganitong string $x$ na umiiral

Pansinin na ito ay hindi isang promise problem — ang function $f$ ay arbitrary. Magiging kapaki-pakinabang, gayunpaman, na isaalang-alang ang sumusunod na promise variant ng problema, kung saan garantisado na may eksaktong isang solusyon. Lumabas ang problemang ito bilang halimbawa ng promise problem sa aralin na Quantum query algorithms.

Natatanging paghahanap

Input: isang function ng anyo $f:\Sigma^n \rightarrow \Sigma$
Promise: mayroon eksaktong isang string $z\in\Sigma^n$ kung saan $f(z) = 1,$ na may $f(x) = 0$ para sa lahat ng string $x\neq z$
Output: ang string $z$

Pansinin din na ang problema ng Or na binanggit sa parehong aralin ay malapit na kaugnay ng Search. Para sa problemang iyon, ang layunin ay simpleng matukoy kung mayroon o wala bang solusyon, kumpara sa aktwal na paghanap ng solusyon.