PL 
EnglishDomyślny
Українська🔍 Algorytm Grovera
Zobacz, jak kwantowe wzmacnianie amplitudy znajduje oznaczony element w O(√N) zapytaniach. Wyrocznia odwraca znaki, dyfuzja odbija względem średniej, a amplituda oznaczonego stanu rośnie — z maksimum przy k* ≈ π/4·√N.
Najczęściej zadawane pytania
Jakie przyspieszenie zapewnia algorytm Grovera w porównaniu z wyszukiwaniem klasycznym?
Algorytm Grovera zapewnia przyspieszenie kwadratowe, przeszukując N elementów w O(√N) krokach zamiast O(N). Dla bazy danych z milionem wpisów redukuje to liczbę operacji z miliona do około tysiąca.
Jak działa wyrocznia w algorytmie Grovera?
Wyrocznia to podprocedura kwantowa, która rozpoznaje docelowy element i odwraca znak (fazę) jego amplitudy bez jego pomiaru. Ten odwrót fazy oznacza rozwiązanie, pozostawiając wszystkie pozostałe stany bez zmian.
Czy algorytm Grovera może złamać szyfrowanie?
Algorytm Grovera zmniejsza o połowę efektywną długość klucza szyfrowania symetrycznego. AES-128 miałby bezpieczeństwo klucza 64-bitowego wobec atakującego kwantowego, dlatego NIST zaleca AES-256 dla bezpieczeństwa postkwantowego.
Ile iteracji wymaga algorytm Grovera?
Optymalna liczba iteracji wynosi w przybliżeniu π/4·√N, gdzie N to rozmiar bazy danych. Wykonanie zbyt małej lub zbyt dużej liczby iteracji zmniejsza prawdopodobieństwo znalezienia poprawnej odpowiedzi.
Czy algorytm Grovera wymaga bezbłędnego komputera kwantowego?
Algorytm Grovera wymaga odpornego na błędy komputera kwantowego, by zrealizować swoją pełną przewagę w dużej skali. Obecne szumiące urządzenia kwantowe pośredniej skali (NISQ) mogą demonstrować tę zasadę na małych instancjach, ale jeszcze nie przewyższają sprzętu klasycznego.