Przeszukiwanie nieustrukturyzowane

Podsumowanie

Zaczniemy od opisu problemu, który rozwiązuje algorytm Grovera. Jak zwykle, przez cały czas tej dyskusji będziemy używać $\Sigma = \{0,1\}$ jako alfabetu binarnego.

Przypuśćmy, że

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

jest funkcją ze stringów binarnych długości $n$ na bity. Założymy, że możemy tę funkcję obliczać w sposób wydajny, ale poza tym jest ona dowolna i nie możemy polegać na tym, że ma szczególną strukturę czy konkretną implementację odpowiadającą naszym potrzebom.

Algorytm Grovera szuka stringu $x\in\Sigma^n$ takiego, że $f(x) = 1$. Takie stringi będziemy nazywać rozwiązaniami problemu wyszukiwania. Jeśli istnieje wiele rozwiązań, za poprawny wynik uznaje się dowolne z nich; jeśli zaś nie ma żadnego rozwiązania, poprawna odpowiedź wymaga poinformowania, że rozwiązania nie istnieją.

To zadanie określa się mianem problemu przeszukiwania nieustrukturyzowanego, ponieważ nie możemy zakładać, że $f$ ma jakąkolwiek szczególną strukturę, która ułatwiałaby sprawę. Nie przeszukujemy posortowanej listy ani żadnej struktury danych zaprojektowanej specjalnie z myślą o wyszukiwaniu — szukamy przysłowiowej igły w stogu siana.

Intuicyjnie możemy wyobrazić sobie, że mamy niezwykle skomplikowany obwód boolowski obliczający $f$, który możemy łatwo uruchomić na wybranym stringu wejściowym. Jednak ze względu na złożoność obwodu nie mamy szans na zrozumienie go poprzez analizę (poza możliwością ewaluacji na wybranych stringach wejściowych).

Jednym z klasycznych sposobów wykonania tego zadania wyszukiwania jest iterowanie po wszystkich stringach $x\in\Sigma^n$ i sprawdzanie, czy każdy z nich jest rozwiązaniem. Dla wygody zapiszmy

$$N = 2^n$$

dla zwięzłości. W $\Sigma^n$ jest $N$ stringów, więc iterowanie po wszystkich nich wymaga $N$ ewaluacji $f$. Zakładając, że jesteśmy ograniczeni do ewaluowania $f$ na wybranych wejściach, to jest najlepsze, co można osiągnąć deterministycznym algorytmem gwarantującym sukces. Algorytm probabilistyczny mógłby próbować zaoszczędzić czas, losowo dobierając stringi wejściowe dla $f$, ale wciąż wymagałby $O(N)$ ewaluacji $f$, aby odnieść sukces z wysokim prawdopodobieństwem.

Algorytm Grovera rozwiązuje ten problem wyszukiwania z wysokim prawdopodobieństwem, wykonując zaledwie $O(\sqrt{N})$ ewaluacji $f$. Warto zaznaczyć, że te ewaluacje funkcji muszą zachodzić w superpozycji, podobnie jak w algorytmach zapytaniowych omówionych w lekcji Algorytmy kwantowe oparte na zapytaniach, w tym algorytm Deutscha, algorytm Deutscha-Jozsy i algorytm Simona. W odróżnieniu od tamtych algorytmów, algorytm Grovera stosuje podejście iteracyjne: ewaluuje $f$ na superpozycjach stringów wejściowych i przeplatuje te ewaluacje innymi operacjami, które tworzą wzorce interferencji — prowadząc do rozwiązania z wysokim prawdopodobieństwem (jeśli istnieje) po $O(\sqrt{N})$ iteracjach.

Formalne sformułowanie problemu

Sformalizujemy problem rozwiązywany przez algorytm Grovera, korzystając z modelu obliczeniowego opartego na zapytaniach. Zakładamy mianowicie, że mamy dostęp do funkcji $f:\Sigma^n\rightarrow\Sigma$ poprzez bramkę zapytania zdefiniowaną w zwykły sposób:

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

dla każdego $x\in\Sigma^n$ i $a\in\Sigma$. Jest to działanie $U_f$ na stanach bazy standardowej; działanie w ogólnym przypadku wyznaczone jest przez liniowość.

Jak omówiono w lekcji Podstawy algorytmiczne obliczeń kwantowych, jeśli dysponujemy obwodem boolowskim obliczającym $f$, możemy przekształcić opis tego obwodu boolowskiego w obwód kwantowy implementujący $U_f$ (używając pewnej liczby kubitów roboczych, które rozpoczynają i kończą obliczenia w stanie $\vert 0\rangle$). Chociaż więc używamy modelu zapytaniowego do sformalizowania problemu rozwiązywanego przez algorytm Grovera, nie jest on ograniczony do tego modelu — możemy uruchomić algorytm Grovera na dowolnej funkcji $f$, dla której posiadamy obwód boolowski.

Poniżej podajemy dokładne sformułowanie problemu, nazwanego Wyszukiwanie (ang. Search), ponieważ szukamy rozwiązania, czyli stringu $x$ powodującego, że $f$ przyjmuje wartość $1$.

Wyszukiwanie

Wejście: funkcja $f:\Sigma^n\rightarrow\Sigma$
Wyjście: string $x\in\Sigma^n$ spełniający $f(x) = 1$, lub „brak rozwiązania", jeśli żaden taki string $x$ nie istnieje

Zauważ, że nie jest to problem z obietnicą — funkcja $f$ jest dowolna. Pomocne będzie jednak rozważenie następującego wariantu problemu z obietnicą, w którym mamy gwarancję, że istnieje dokładnie jedno rozwiązanie. Ten problem pojawił się jako przykład problemu z obietnicą w lekcji Algorytmy kwantowe oparte na zapytaniach.

Wyszukiwanie z jednym rozwiązaniem

Wejście: funkcja postaci $f:\Sigma^n \rightarrow \Sigma$
Obietnica: istnieje dokładnie jeden string $z\in\Sigma^n$ taki, że $f(z) = 1$, przy czym $f(x) = 0$ dla wszystkich stringów $x\neq z$
Wyjście: string $z$

Zauważ też, że problem Or wspomniany w tej samej lekcji jest ściśle powiązany z problemem Wyszukiwanie. W tamtym problemie celem jest jedynie ustalenie, czy rozwiązanie istnieje, a nie faktyczne jego znalezienie.