Algorytm Grovera

Algorytm Grovera – algorytm kwantowy przeznaczony do działania na komputerze kwantowym, przedstawiony przez Lova K. Grovera w 1996^[1] i opublikowany w 2001^[2].

Algorytm Grovera

Rodzaj	algorytm kwantowy, przeszukiwanie N-elementowego zbioru
Struktura danych	rejestr kwantowy
Złożoność
Czasowa	${\displaystyle O({\sqrt {N}})}$
Pamięciowa	zależnie od implementacji

Algorytm dotyczy przeszukiwania bazy danych składającej się z N elementów w celu znalezienia w niej elementu wyróżnionego. Jest to problem podobny do „odwrotnego” przeszukiwania książki telefonicznej. W książce zawierającej N danych chcemy znaleźć nazwisko posiadacza danego numeru.

Złożoność obliczeniowa

O ile liczba kroków niezbędna do rozwiązania problemu za pomocą algorytmu klasycznego jest rzędu ${\displaystyle \mathrm {O} (N)}$, o tyle kwantowy algorytm Grovera potrzebuje jedynie około ${\displaystyle \mathrm {O} ({\sqrt {N}})}$ kroków, a więc pozwala na kwadratowe przyspieszenie czasu realizacji programu.

Algorytm dotyczy poszukiwania danego elementu w nieposortowanym N-elementowym zbiorze. Problem wyszukiwania sprowadza się do wyznaczenia, na drodze przekształceń unitarnych, odpowiedniego indeksu określającego dany element w zbiorze.

Przebieg algorytmu

Obwód kwantowy algorytmu Grovera dla N elementów zapisanych na n qubitach

1. Zainicjuj rejestr kwantowy n kubitów zrównoważoną superpozycją wszystkich N stanów kwantowych

${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}$

2. W kolejnych iteracjach transformuj rejestr operatorem

${\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |}$

gdzie ${\displaystyle |\omega \rangle }$ jest stanem poszukiwanym, a następnie operatorem

${\displaystyle U_{s}=2|s\rangle \langle s|-I.}$

Algorytm polega na iteracyjnym wykonywaniu operacji:

${\displaystyle |s_{i+1}\rangle =U_{s}U_{\omega }|s_{i}\rangle .}$

3. Przeprowadź pomiar rejestru. Jego rezultatem będzie wartość własna ${\displaystyle \lambda _{\omega }}$ z prawdopodobieństwem dążącym do 1 dla N ≫ 1. Na jej podstawie można określić stan poszukiwany ${\displaystyle |\omega \rangle .}$

Zobacz też

• informatyka kwantowa
• komputer kwantowy
• kryptologia kwantowa

Przypisy

1. Lov K. Grover. A fast quantum mechanical algorithm for database search. In STOC ’96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212-219, New York, NY, USA, 1996. ACM Press.
2. Grover L.K.: From Schrödinger’s equation to quantum search algorithm, American Journal of Physics, 69(7): 769-777, 2001.

Bibliografia

• MikaM. Hirvensalo MikaM., Algorytmy kwantowe, PawełP. Zabierowski (tłum.), 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.