Opis algorytmu Grovera

W tej sekcji opiszemy algorytm Grovera. Zaczniemy od omówienia bramek zapytań fazowych i sposobu ich budowy, a następnie przejdziemy do opisu samego algorytmu Grovera. Na koniec krótko omówimy, jak naturalnie stosuje się ten algorytm do przeszukiwania.

Bramki zapytań fazowych

Algorytm Grovera korzysta z operacji znanych jako bramki zapytań fazowych. W odróżnieniu od zwykłej bramki zapytania $U_f,$ zdefiniowanej dla danej funkcji $f$ w standardowy sposób opisany wcześniej, bramka zapytania fazowego dla funkcji $f$ jest zdefiniowana jako

$$Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle$$

dla każdego ciągu $x\in\Sigma^n.$

Operację $Z_f$ można zaimplementować za pomocą jednej bramki zapytania $U_f,$ jak sugeruje poniższy diagram:

Ta implementacja korzysta ze zjawiska phase kickback i wymaga udostępnienia jednego roboczego qubitu, zainicjalizowanego do stanu $\vert -\rangle$. Ten qubit pozostaje w stanie $\vert - \rangle$ po zakończeniu implementacji i może być ponownie użyty (na przykład do implementacji kolejnych bramek $Z_f$) lub po prostu odrzucony.

Oprócz operacji $Z_f$ będziemy również używać bramki zapytania fazowego dla $n$-bitowej funkcji OR, zdefiniowanej dla każdego ciągu $x\in\Sigma^n$ w następujący sposób.

$$\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}$$

Konkretnie, bramka zapytania fazowego dla $n$-bitowej funkcji OR działa następująco:

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}$$

Dla jasności: tak właśnie działa $Z_{\mathrm{OR}}$ na standardowych stanach bazowych; jej zachowanie na dowolnych stanach wynika z tej definicji przez liniowość.

Operację $Z_{\mathrm{OR}}$ można zaimplementować jako Circuit kwantowy, zaczynając od układu logicznego dla funkcji OR, następnie konstruując operację $U_{\mathrm{OR}}$ (czyli standardową bramkę zapytania dla $n$-bitowej funkcji OR) zgodnie z procedurą opisaną w lekcji Podstawy algorytmiczne obliczeń kwantowych, a na końcu operację $Z_{\mathrm{OR}}$ z wykorzystaniem zjawiska phase kickback opisanego powyżej. Zauważ, że operacja $Z_{\mathrm{OR}}$ nie zależy od funkcji $f$ i dlatego można ją zaimplementować za pomocą Circuitu kwantowego bez żadnych bramek zapytań.

Opis algorytmu

Teraz, gdy mamy już obie operacje $Z_f$ i $Z_{\mathrm{OR}},$ możemy opisać algorytm Grovera.

Algorytm odwołuje się do liczby $t,$ która jest liczbą iteracji wykonywanych przez algorytm (a zatem liczbą zapytań do funkcji $f,$ których wymaga). Liczba $t$ nie jest określona przez algorytm Grovera w opisywanej przez nas wersji — omówimy później w tej lekcji, jak można ją wybrać.

Algorytm Grovera

1. Zainicjalizuj rejestr $n$ qubitów $\mathsf{Q}$ do stanu zerowego $\vert 0^n \rangle,$ a następnie zastosuj operację Hadamarda do każdego qubitu w $\mathsf{Q}.$
2. Zastosuj $t$ razy operację unitarną $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ do rejestru $\mathsf{Q}.$
3. Zmierz kubity rejestru $\mathsf{Q}$ względem pomiarów standardowej bazy i zwróć otrzymany ciąg.

Operacja $G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f$ iterowana w kroku 2 będzie przez resztę tej lekcji nazywana operacją Grovera. Oto reprezentacja Circuitu kwantowego operacji Grovera dla $n=7\!:$

Na tym diagramie operacja $Z_f$ jest przedstawiona jako większa niż $Z_{\mathrm{OR}},$ co stanowi nieformalną wizualną wskazówkę sugerującą, że prawdopodobnie jest ona kosztowniejsza. W szczególności, gdy pracujemy w modelu zapytań, $Z_f$ wymaga jednego zapytania, natomiast $Z_{\mathrm{OR}}$ nie wymaga żadnych. Jeśli zamiast tego dysponujemy układem logicznym dla funkcji $f$ i konwertujemy go na obwód kwantowy dla $Z_f,$ możemy zasadnie oczekiwać, że otrzymany Circuit kwantowy będzie większy i bardziej skomplikowany niż Circuit dla $Z_{\mathrm{OR}}.$

Poniżej przedstawiono diagram Circuitu kwantowego dla całego algorytmu przy $n=7$ i $t=3.$ Dla większych wartości $t$ wystarczy wstawić kolejne instancje operacji Grovera bezpośrednio przed pomiarami.

Zastosowanie do przeszukiwania

Algorytm Grovera można zastosować do problemu przeszukiwania w następujący sposób:

• Wybierz liczbę $t$ w kroku 2. (Omówiono to w dalszej części lekcji.)
• Uruchom algorytm Grovera dla funkcji $f,$ używając wybranej wartości $t,$ aby otrzymać ciąg $x\in\Sigma^n.$
• Zapytaj funkcję $f$ o ciąg $x,$ aby sprawdzić, czy jest to prawidłowe rozwiązanie:
  • Jeśli $f(x) = 1,$ to znaleźliśmy rozwiązanie i możemy zatrzymać się oraz zwrócić $x.$
  • W przeciwnym razie, jeśli $f(x) = 0,$ możemy albo ponownie uruchomić procedurę, być może z innym wyborem $t,$ albo zdecydować się poddać i zwrócić „brak rozwiązania".

Kiedy przeanalizujemy działanie algorytmu Grovera, zobaczymy, że przyjmując $t = O(\sqrt{N}),$ uzyskujemy rozwiązanie naszego problemu przeszukiwania (jeśli istnieje) z dużym prawdopodobieństwem.