Algorytm Poszukiwań Grovera: Wyjaśnienie Wzmocnienia Amplitudy

Kwanty, superpozycja i model obwodu

Komputer kwantowy operuje na kubitach – systemach dwustanowowych, które w przeciwieństwie do klasycznych bitów mogą istnieć w dowolnych stanach superpozycji |ψ⟩ = α|0⟩ + β|1⟩, gdzie |α|² + |β|² = 1. Rejestr z n kubitów żyje w przestrzeni Hilberta o 2ⁿ amplitudach zespolonych: już 3 kubity rozkładają się na 8 równoległych amplitud. Bramka Hadamarda tworzy równą superpozycję, a zbiór {Hadamard, T, CNOT} jest uniwersalny – dowolne obliczenie kwantowe można zbudować wyłącznie z tych trzech bram.

Algorytm: orakl plus dyfuzja

Lov Grover (1996) opracował algorytm do znalezienia oznaczonych elementu w nieusortowanym zbiorze N elementów, co klasycznie wymaga średnio O(N) zapytań. Algorytm Grovera potrzebuje jedynie O(√N):

1. Initialise: |ψ⟩ = H^⊗n |0⟩ⁿ   (equal superposition of all N states)

2. Repeat ≈(π/4)·√N times:
   a. Oracle:     O|x⟩ = −|x⟩ if x matches, +|x⟩ otherwise
   b. Diffusion:  2|ψ⟩⟨ψ| − I   ("inversion about the mean")

3. Measure → obtains the marked item with probability ≥ 1 − ε

N = 2²⁰ ≈ 10⁶:  classical avg 500,000 queries  vs  Grover ~785 queries

Geometryczna wizualizacja

Każda iteracja Grovera obróci wektor stanu o stały kąt 2θ w kierunku wskazywanego stanu, gdzie sin(θ) = 1/√N. Optymalna liczba iteracji wynosi t = (π/4)·√N – przekroczenie tego punktu powoduje powrót amplitudy z celem, co różni się od klasycznego wyszukiwania, w którym więcej iteracji nie zawsze jest korzystne. Przy N = 2⁵⁶ ≈ 7×10¹⁶, klasyczne brute force wymaga średnio około 10¹⁷ zapytań, natomiast Grover potrzebuje mniej więcej 2×10⁸ – różnica ta wynosi dziewic rozporządań.

Dlaczego to ma znaczenie dla kryptografii

Algorytm Grovera ma bezpośrednie implikacje dotyczące bezpieczeństwa kryptografii klucza symetrycznego. Klucz o długości 128 bitów (AES-128) wymaga klasycznego przeszukiwania brute-force z możliwością 2¹²⁸ kombinacji; Grover redukuje to do około 2⁶⁴ zapytań kwantowych – co w zasadzie zmniejsza margines bezpieczeństwa o połowę. Odpowiedź NIST jest prosta: używać AES-256 zamiast AES-128, aby zachować prawdziwy poziom bezpieczeństwa 128-bitowego przeciwko przeciwnikom kwantowym. Kluczowe jest to, że przyspieszenie Grovera jest kwadratowe, a nie wykładnicze, jak algorytm Shora do rozkładu liczb – nie może rozwiązać problemów NP-całkowitych w czasie wielomianowym, ponieważ przestrzeń przeszukiwania pozostaje wykładnicza nawet po zmniejszeniu pierwiastkiem z kwadratu.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.