Algorytm Grovera: √N zamiast N

Wyobraź sobie książkę telefoniczną z milionem numerów — nieposortowaną. Szukasz osoby, która ma numer 555-0123. Klasycznie nie ma drogi na skróty: w najgorszym razie sprawdzisz wszystkie $N$ wpisów, średnio $N/2$. Algorytm Grovera znajduje odpowiedź w około $\sqrt{N}$ krokach — dla miliona wpisów to tysiąc zapytań zamiast pół miliona. To nie magia, tylko geometria. I właśnie geometrię zobaczysz poniżej na animacji.

Problem: przeszukiwanie nieustrukturyzowane

Formalnie: mamy funkcję $f : \{0,1\}^n \to \{0,1\}$, która zwraca 1 tylko dla jednego, nieznanego argumentu $w$ (ang. winner). Dostęp do $f$ mamy wyłącznie przez wyrocznię — czarną skrzynkę, którą możemy odpytywać. Pytanie brzmi: ile zapytań potrzeba, by znaleźć $w$ wśród $N = 2^n$ kandydatów?

Klasycznie: $\Theta(N)$ zapytań — nic nie wskaże drogi, trzeba próbować.
Kwantowo: $O(\sqrt{N})$ zapytań — i jest to wynik optymalny, lepiej się nie da.

Trzy składniki algorytmu

1. Jednorodna superpozycja

Zaczynamy od stanu będącego superpozycją wszystkich $N$ możliwości — bramka Hadamarda na każdym z $n$ kubitów:

$$|s\rangle = H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle$$

Każdy stan bazowy, w tym szukany $|w\rangle$, ma teraz amplitudę $1/\sqrt{N}$. Gdybyśmy zmierzyli od razu, trafilibyśmy $w$ z prawdopodobieństwem $1/N$ — czyli wcale.

2. Wyrocznia $U_w$ — oznaczanie rozwiązania fazą

Wyrocznia odwraca znak amplitudy wyłącznie przy stanie $|w\rangle$:

$$U_w|x\rangle = (-1)^{f(x)}|x\rangle = \begin{cases} -|x\rangle & x = w \\ \phantom{-}|x\rangle & x \neq w \end{cases}$$

Kluczowa subtelność: zmiana fazy jest niewidoczna w pomiarze — prawdopodobieństwa $|\alpha_x|^2$ się nie zmieniają. Wyrocznia sama niczego nie „znajduje”; ona tylko zostawia znacznik, który wykorzysta następny krok.

3. Operator dyfuzji $U_s$ — odbicie względem średniej

Dyfuzja odbija wszystkie amplitudy względem ich wartości średniej: $\alpha_x \mapsto 2\bar{\alpha} – \alpha_x$, co zapisuje się jako

$$U_s = 2|s\rangle\langle s| – I$$

Amplituda $|w\rangle$ jest po wyroczni ujemna, więc leży daleko pod średnią — odbicie wyrzuca ją wysoko ponad pozostałe. Amplitudy „niewinnych” stanów, minimalnie powyżej średniej, po odbiciu odrobinę maleją. Jedna iteracja Grovera to złożenie $G = U_s U_w$ — i każda kolejna pompuje amplitudę do $|w\rangle$.

Geometria: cały algorytm to obrót

Najpiękniejsza obserwacja: przez cały czas stan układu żyje w dwuwymiarowej płaszczyźnie rozpiętej przez $|w\rangle$ (rozwiązanie) i $|s’\rangle$ — jednorodną superpozycję wszystkich stanów poza rozwiązaniem. Stan początkowy tworzy z osią $|s’\rangle$ mały kąt $\theta$, gdzie $\sin\theta = 1/\sqrt{N}$:

$$|s\rangle = \sin\theta\,|w\rangle + \cos\theta\,|s’\rangle$$

W tej płaszczyźnie obie operacje są zwykłymi odbiciami:

Wyrocznia $U_w$ = odbicie względem osi $|s’\rangle$ (zmienia znak składowej $|w\rangle$),
Dyfuzja $U_s$ = odbicie względem kierunku $|s\rangle$.

Złożenie dwóch odbić to obrót o kąt $2\theta$ — zawsze w stronę $|w\rangle$. Po $k$ iteracjach wektor stanu tworzy z osią $|s’\rangle$ kąt $(2k+1)\,\theta$, a prawdopodobieństwo sukcesu wynosi:

$$P_k = \sin^2\big((2k+1)\,\theta\big)$$

Płaszczyzna ⟨|s′⟩, |w⟩⟩ — wektor stanu

Amplitudy stanów bazowych

różowy słupek = |w⟩ (rozwiązanie), niebieskie = pozostałe stany

N = 16 iteracja k = 0 P(sukces) = 6.3% optimum: k = 3

Kliknij „Iteracja Grovera” i obserwuj obie fazy: najpierw wyrocznia odbija wektor pod oś $|s’\rangle$ (ujemna amplituda rozwiązania), potem dyfuzja odbija go względem $|s\rangle$ — wektor ląduje o $2\theta$ bliżej $|w\rangle$, a różowy słupek rośnie. Zwróć uwagę, co się dzieje po przekroczeniu optimum: wektor przestrzeliwuje i prawdopodobieństwo zaczyna spadać. Grover to nie „im więcej, tym lepiej” — to algorytm, który trzeba zatrzymać w porę.

Ile iteracji? Dokładnie $\tfrac{\pi}{4}\sqrt{N}$

Chcemy, by $(2k+1)\theta \approx \pi/2$, czyli by wektor stanął możliwie blisko $|w\rangle$. Stąd optymalna liczba iteracji:

$$k_{\text{opt}} = \left\lfloor \frac{\pi}{4\theta} \right\rfloor \approx \frac{\pi}{4}\sqrt{N} \qquad (\theta \approx 1/\sqrt{N} \text{ dla dużych } N)$$

Dla $N = 16$: $\theta = \arcsin(1/4) \approx 14.5°$, optimum przy $k = 3$, gdzie $P = \sin^2(7\theta) \approx 96\%$. Dla miliona elementów — około 785 iteracji. Jeśli rozwiązań jest $M$, kąt rośnie do $\sin\theta = \sqrt{M/N}$, a optimum spada do $\approx \tfrac{\pi}{4}\sqrt{N/M}$.

Implementacja w Qiskit

Kompletny przykład dla $n = 4$ kubitów ($N = 16$), szukamy stanu $|1011\rangle$:

from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
import numpy as np

n = 4                       # 4 kubity -> N = 16
target = "1011"             # szukany stan |w>

def oracle(qc):
    """Odwraca fazę stanu |1011> (multi-controlled Z)."""
    for i, bit in enumerate(reversed(target)):
        if bit == "0":
            qc.x(i)
    qc.h(n - 1); qc.mcx(list(range(n - 1)), n - 1); qc.h(n - 1)
    for i, bit in enumerate(reversed(target)):
        if bit == "0":
            qc.x(i)

def diffusion(qc):
    """U_s = 2|s><s| - I : odbicie względem średniej."""
    qc.h(range(n)); qc.x(range(n))
    qc.h(n - 1); qc.mcx(list(range(n - 1)), n - 1); qc.h(n - 1)
    qc.x(range(n)); qc.h(range(n))

qc = QuantumCircuit(n)
qc.h(range(n))                        # jednorodna superpozycja

k_opt = int(np.floor(np.pi / (4 * np.arcsin(1 / np.sqrt(2**n)))))
for _ in range(k_opt):                # k_opt = 3 iteracje Grovera
    oracle(qc)
    diffusion(qc)

qc.measure_all()
counts = AerSimulator().run(qc, shots=4096).result().get_counts()
best = max(counts, key=counts.get)
print(f"najczęstszy wynik: |{best}>  ({counts[best]/4096:.1%})")
# najczęstszy wynik: |1011>  (~96%)

Symulacja obwodu: 4 kubity, bramka po bramce

Powyższy kod to nie abstrakcja — poniżej dokładna symulacja tego obwodu (pełny wektor stanu, 16 amplitud). Przechodź strzałkami przez kolejne kolumny bramek i obserwuj, co każda z nich robi ze stanem: jak wyrocznia odwraca znak amplitudy $|1011\rangle$ (słupek spada pod oś), a dyfuzja odbija wszystkie amplitudy względem średniej (żółta przerywana linia) i wypycha rozwiązanie w górę.

Obwód Grovera — n = 4, cel |1011⟩

amplitudy: ■ dodatnie · ■ ujemne · — średnia · ■ |1011⟩ (cel)

krok 0/37 blok: start P(|1011⟩) = 0.0%

stan początkowy |0000⟩ — kliknij „krok ▶”

Warto zatrzymać się na dwóch momentach. Po bramce MCX w wyroczni (z Hadamardami po bokach działa jak wielokrotnie sterowane Z) dokładnie jedna amplituda schodzi pod oś — pomiar niczego by tu jeszcze nie wykrył, bo $|{-}0.25|^2 = |0.25|^2$. Dopiero końcowe H⊗4 dyfuzji zamienia tę ukrytą fazę na widoczną różnicę wysokości: średnia (żółta linia) leży tuż pod poziomem „niewinnych” słupków, więc odbicie ledwo je muska, a wywindowany zostaje tylko $|1011\rangle$. Po trzech iteracjach różowy słupek niesie ~96% prawdopodobieństwa — dokładnie tyle, ile wyszło w symulatorze Qiskit powyżej.

O czym się często zapomina

Przyspieszenie jest kwadratowe, nie wykładnicze. $\sqrt{N}$ to wciąż dużo dla naprawdę wielkich przestrzeni — Grover nie łamie NP-zupełności.
Wyrocznię trzeba umieć zbudować. Algorytm zakłada, że sprawdzenie kandydata jest tanie jako obwód kwantowy; koszt wyroczni bywa dominujący.
Wynik jest probabilistyczny. $P \approx 96\%$ przy $N=16$ — w praktyce wynik weryfikujemy klasycznie (to jedno wywołanie $f$) i ewentualnie powtarzamy.
Głębokość obwodu rośnie z $\sqrt{N}$ — na sprzęcie ery NISQ dekoherencja ogranicza praktyczne rozmiary problemu (więcej we wpisie o erze NISQ).

Grover bywa nazywany „szwajcarskim scyzorykiem” informatyki kwantowej: wzmacnianie amplitudy, którego jest szczególnym przypadkiem, pojawia się jako podprogram w dziesiątkach innych algorytmów — od zliczania kwantowego po uczenie maszynowe. Zrozumienie tego jednego obrotu o $2\theta$ otwiera drzwi do całej rodziny metod.

Algorytm Grovera: √N zamiast N — skąd bierze się przyspieszenie