Równowaga Kwasowo-Zasadowa

Szatnia z N słomkami

Przeszukiwanie nieposortowanej listy N elementów w poszukiwaniu tego, który spełnia określone warunki, klasycznie jest problemem O(N): bez możliwości wykorzystania struktury, sprawdzamy elementy po kolei i średnio potrzebujemy około N/2 prób. Lov Grover wykazał w 1996 roku, że komputer kwantowy może wykonać to samo zadanie przy użyciu w przybliżeniu √N wywołań do czarnej skrzynki – co daje kwadratowe przyspieszenie. Nie jest to skok wykładniczy, jaki zapewnia algorytm Shora w przypadku rozkładu na czynniki, ale jest to udowodnione, że jest to najlepsze, jakie może osiągnąć dowolny algorytm kwantowy dla nieustrukturyzowanego wyszukiwania i jest wystarczająco ogólne, aby przyspieszyć każdy problem sformułowany jako "sprawdź tego kandydata w oparciu o test tak/nie".

Superpozycja jako pierwszy: zadawanie wszystkich pytań naraz

Algorytm rozpoczyna się od umieszczenia n kubitów (N = 2^n) w superpozycji wszystkich możliwych indeksów, wykorzystując warstwę bram Hadamard na stanie zerowym. Każdy z N stanów bazowych teraz posiada tę samą amplitudę, 1/√N, co oznacza, że prawdopodobieństwo zmierzenia dowolnego danego stanu wynosi 1/N – dokładnie takie same szanse jak przy pojedynczej klasycznej zgadnce. Kluczem nie jest jeszcze zgadywanie, ale przekształcenie tej płaskiej mapy amplitud tak, aby amplituda wybranego stanu rosła kosztem pozostałych, zanim w ogóle dokonano pomiaru.

Orkul: odwrócenie fazy, którego nikt nie widzi

Orkul U_f jest operatorem jednorodnym, który rozpoznaje oznaczony element bez ujawniania go: pozostawia niezmienione wszystkie stany niezamówione i mnoży amplitudę zamówionego stanu przez -1. Zmierzony natychmiast, ten przesunięcie fazowy byłoby niewidzialny – prawdopodobieństwo dowolnego wyniku to kwadrat amplitudy, a kwadratowanie usuwa znak. Cały algorytm jest sposobem przekształcenia tego niewidzialnej różnicy fazowej w widoczną różnicę prawdopodobieństwa przed pomiarami kubitów.

Dyfuzja: odwracanie względem średniej

Drugi operator, operator dyfuzyjny, odbija każdą amplitudę wokół ich wartości średniej. Ponieważ oracle jedynie sprawił, że jedna amplituda stała się ujemna, a pozostałe były dodatnie i równe, średnia lekko opadła poniżej wspólnej wartości. Odbicie względem tej obniżonej średniej podniosło zaznaczoną amplitudę o około 2/√N, a wszystkie pozostałe amplitudy zostały delikatnie obniżone. Jedna operacja oracle i jeden krok dyfuzyjny nazywane są iteracją Grovera, a geometrycznie jest to stałobiegły obrót wektora stanu wewnątrz płaszczyzny spanned przez podprzestrzeń zaznaczoną i niezaznaczoną.

|s⟩ = H^⊗n |0⟩                    every state gets amplitude 1/√N

repeat k ≈ (π/4)·√(N/M) times:
  |s⟩ ← Uf |s⟩                    oracle: flip the sign of marked states
  |s⟩ ← (2|s⟩⟨s| − I) |s⟩         diffusion: reflect about the mean amplitude

measure |s⟩                        marked state now dominates
P(marked after k steps) = sin²( (2k+1)·θ ),   θ = arcsin(√(M/N))

Dlaczego pierwiastek kwadratowy, a nie coś więcej

Każda iteracja obróci stan o ten sam mały kąt θ ≈ 2/√N (dla jednego zaznaczonego elementu spośród N), więc liczba iteracji potrzebna do obrotu w przybliżeniu ćwiartki okręgu – punktu, w którym największa amplituda zaznaczenia – wynosi około (π/4)·√N. Wykonanie większej liczby iteracji powoduje, że stan nadal obraca się za ten sam punkt, co prowadzi do spadku prawdopodobieństwa sukcesu i jego ponownego wzrostu, oscylując z okresem w przybliżeniu π√N kroków: jest to dobrze znany problem przetrzymania (overshoot), a więc i powód, dla którego rzeczywiste implementacje wymagają przynajmniej przybliżonej wiedzy o N (lub liczbie zaznaczonych elementów M) z góry. Bennett, Bernstein, Brassard i Vazirani udowodnili w 1997 roku, że żaden algorytm kwantowy traktujący orakulum jako czarną skrzynkę nie może uzyskać lepszego wyniku niż Ω(√N) zapytań, więc algorytm Grovera nie jest tylko szybki, ale i optymalny.

Rozbijanie kluczy i dlaczego AES-256 nadal jest bezpieczny

Najczęściej cytowane zastosowanie traktuje przestrzeń klucza symetrycznego szyfru jako nieposortowaną listę: przy danym parze plaintext/ciphertext, pytanie "czy ten klucz jest właściwy" stanowi orakulum, a Grover znajduje klucz w około 2^(n/2) próbach zamiast 2^n. To zredukuje efektywną ochronę n-bitowego klucza o połowę, a nie rozbija go całkowicie, dlatego standardową obroną przed przyszłym komputerem kwantowym o dużej skali jest po prostu podwojenie długości klucza - AES-256 w przypadku działania Grovera zachowuje się tak samo jak współczesny AES-128, a AES-128 nadal uważa się za bezpieczny przeciwko atakującym klasycznie. Jest to znacznie łagodniejsze zagrożenie niż stanowi algorytm Shora dla kryptografii RSA i krzywoprzecinkowej, który ją całkowicie i wydajnie rozbija, zamiast jedynie osłabiać.

Frequently asked questions

Wypróbuj na żywo

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