🔍 Algorytm wyszukiwania Grovera

Wizualizuje algorytm Grovera przeszukujący nieustrukturyzowany rejestr N = 16 elementów w poszukiwaniu jednego oznaczonego celu. Amplituda każdego elementu jest rysowana jako słupek, a słupek celu rośnie w kierunku niemal pewności w miarę stosowania kolejnych iteracji Grovera.

Każda iteracja łączy dwa kroki. Wyrocznia odwraca znak amplitudy celu, oznaczając go; operator dyfuzji następnie odbija wszystkie amplitudy względem ich średniej. To „odwrócenie względem średniej” podnosi cel, obniżając resztę, obracając wektor stanu w kierunku rozwiązania.

Lista rozwijana celu wybiera, który z 16 elementów (pokazanych jako |0000⟩ do |1111⟩) jest oznaczonym rozwiązaniem. Step wykonuje jedną iterację wyrocznia+dyfuzja, Auto uruchamia iteracje co 0,9 sekundy, a Reset przywraca jednorodną superpozycję 1/√16 z zerową liczbą iteracji.

Optymalna liczba to w przybliżeniu π/4·√N. Dla N = 16 zaokrągla się to do 3 iteracji, przy których prawdopodobieństwo celu jest bliskie maksimum. Pasek informacyjny wyświetla to jako „π/4·√16 ≈ 3”.

Klasycznie przeszukanie nieposortowanej listy N elementów wymaga średnio około N/2 porównań (8 dla N = 16). Grover znajduje cel w zaledwie O(√N) iteracjach — kwadratowe przyspieszenie. Dla miliona elementów to około 1000 zapytań zamiast 500 000.

Iteracje Grovera to obrót, więc mogą go przekroczyć. Po punkcie optymalnym prawdopodobieństwo celu ponownie spada, gdy stan obraca się poza rozwiązanie. Symulacja oznacza to jako „nadmierny obrót”, pokazując, że więcej iteracji nie zawsze jest lepsze.

Jest to macierz unitarna D = 2|s⟩⟨s| − I, gdzie |s⟩ to jednorodna superpozycja. W praktyce odbija każdą amplitudę względem średniej wszystkich amplitud, co wzmacnia każdą wartość, którą wyrocznia zepchnęła poniżej średniej — czyli oznaczony cel.

Arytmetyka amplitud jest dokładna dla wyidealizowanego, bezszumowego komputera kwantowego z rzeczywistymi amplitudami, co jest wszystkim, czego wymaga algorytm Grovera. Pomija rzeczywiste efekty, takie jak dekoherencja, błędy bramek i kolaps pomiarowy, więc jest to wierny model matematyczny, a nie emulacja sprzętu.

Algorytm zaczyna od umieszczenia rejestru w jednorodnej superpozycji, zwykle za pomocą bramek Hadamarda, więc każdy element ma amplitudę 1/√N = 1/4 i prawdopodobieństwo 1/16 (6,25%). Ten równy punkt startowy odzwierciedla brak wcześniejszej wiedzy o tym, gdzie znajduje się cel.

Nie. Dla wyszukiwania nieustrukturyzowanego skalowanie O(√N) jest dowiedzione optymalne; żaden algorytm kwantowy nie może znaleźć oznaczonego elementu przy mniejszej liczbie zapytań do wyroczni. Ta optymalność, udowodniona przez Bennetta, Bernsteina, Brassarda i Vaziraniego, czyni Grovera punktem odniesienia dla wyszukiwania kwantowego.

Wzmacnianie amplitudy w stylu Grovera przyspiesza zadania brute-force: przeszukiwanie nieustrukturyzowanych baz danych, odwracanie funkcji, rozwiązywanie problemów ograniczeń i SAT oraz atakowanie kryptografii symetrycznej (zmniejszając efektywną siłę klucza o połowę), dlatego wytyczne postkwantowe zalecają większe rozmiary kluczy.