Wprowadzenie
Algorytm Grovera to kwantowy algorytm dla tzw. problemów nieustrukturyzowanego przeszukiwania, oferujący kwadratową poprawę względem algorytmów klasycznych. Oznacza to, że algorytm Grovera wymaga liczby operacji rzędu pierwiastka kwadratowego z liczby operacji potrzebnych do klasycznego rozwiązania nieustrukturyzowanego przeszukiwania — co jest równoważne stwierdzeniu, że klasyczne algorytmy dla nieustrukturyzowanego przeszukiwania muszą mieć koszt co najmniej rzędu kwadratu kosztu algorytmu Grovera.
Algorytm Grovera wraz z jego rozszerzeniami i metodologią okazuje się szeroko stosowany, prowadząc do kwadratowej przewagi dla wielu interesujących zadań obliczeniowych, które na pierwszy rzut oka mogą nie wyglądać jak problemy nieustrukturyzowanego przeszukiwania.
Choć szeroka stosowalność techniki przeszukiwania Grovera jest przekonująca, należy przyznać już na początku lekcji, że kwadratowa przewaga, którą oferuje, najprawdopodobniej nie doprowadzi do praktycznej przewagi obliczeń kwantowych nad klasycznymi w niedalekiej przyszłości. Klasyczny sprzęt obliczeniowy jest znacznie bardziej zaawansowany niż kwantowy — a kwadratowa przewaga kwantowa nad klasyczną oferowana przez algorytm Grovera z pewnością zostanie zniwelowana przez oszałamiające taktowania nowoczesnych komputerów klasycznych dla każdego problemu nieustrukturyzowanego przeszukiwania, który mógłby być praktycznie uruchamiany w niedalekiej przyszłości.
W miarę jak technologia obliczeń kwantowych się rozwija, algorytm Grovera może mieć jednak potencjał. Rzeczywiście, niektóre z najważniejszych i najbardziej wpływowych klasycznych algorytmów, w tym szybka transformata Fouriera i szybkie sortowanie (np. quicksort i mergesort), oferują nieco mniejszą niż kwadratową przewagę nad naiwnymi podejściami do problemów, które rozwiązują. Kluczowa różnica polega oczywiście na tym, że do uruchomienia algorytmu Grovera wymagana jest zupełnie nowa technologia (czyli obliczenia kwantowe). Choć technologia ta jest wciąż w powijakach w porównaniu z obliczeniami klasycznymi, nie powinniśmy zbyt szybko lekceważyć potencjału postępu technologicznego, który mógłby kiedyś umożliwić kwadratowej przewadze obliczeń kwantowych nad klasycznymi przyniesienie wymiernych korzyści praktycznych.
Wideo do lekcji
W poniższym filmie John Watrous przeprowadzi Cię przez treść tej lekcji dotyczącej algorytmu Grovera. Możesz też otworzyć film na YouTube w osobnym oknie. Pobierz slajdy do tej lekcji.