Algorytm Grovera
Algorytm Grovera to algorytm kwantowy, który został stworzony do pracy na komputerach kwantowych. Został zaprezentowany przez Lova K. Grovera w 1996 roku, a jego publikacja miała miejsce w 2001 roku.
Algorytm ten odnosi się do przeszukiwania bazy danych składającej się z N elementów w celu zidentyfikowania wyróżnionego elementu. Problem ten przypomina „odwrotne” przeszukiwanie książki telefonicznej, gdzie w zbiorze N danych chcemy znaleźć nazwisko odpowiadające określonemu numerowi.
Złożoność obliczeniowa
Dla algorytmu klasycznego liczba kroków wymaganych do rozwiązania tego problemu wynosi:
O(N).
Natomiast kwantowy algorytm Grovera potrzebuje jedynie około:
O(√N) kroków, co oznacza, że umożliwia kwadratowe przyspieszenie czasu wykonania programu.
Algorytm koncentruje się na poszukiwaniu konkretnego elementu w nieposortowanym zbiorze zawierającym N elementów. Problem wyszukiwania sprowadza się do określenia odpowiedniego indeksu, który identyfikuje dany element w zbiorze, przy użyciu przekształceń unitarnych.
Przebieg algorytmu
- Rozpocznij od zainicjowania rejestru kwantowego składającego się z n kubitów, tworząc zrównoważoną superpozycję wszystkich N stanów kwantowych:
- W kolejnych iteracjach przekształć rejestr przy użyciu operatora:
- Na końcu wykonaj pomiar rejestru. Wynikiem będzie wartość własna:
|s⟩ = 1/√N ∑x=0N−1 |x⟩.
Uω = I – 2|ω⟩⟨ω|,
gdzie |ω⟩ to stan poszukiwany, a następnie operator:
Us = 2|s⟩⟨s| – I.
Algorytm polega na iteracyjnym wykonywaniu operacji:
|si+1⟩ = UsUω|si⟩.
λω z prawdopodobieństwem dążącym do 1 dla N ≫ 1. Na tej podstawie można określić stan poszukiwany |ω⟩.
Zobacz też
Przypisy
Bibliografia
Mika M. Hirvensalo, Algorytmy kwantowe, tłum. Paweł P. Zabierowski, Warszawa: WSiP, 2004, ISBN 83-02-09155-3, OCLC 749548876. Brak numerów stron w książce.
Krzysztof Giaro, Marcin Kamiński, Wprowadzenie do algorytmów kwantowych, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2003, ISBN 83-87674-57-5.
