Algorytm Grovera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Algorytm Groveraalgorytm kwantowy przeznaczony do działania na komputerze kwantowym opublikowany w 1996[1] przez Lova K. Grovera.

Algorytm dotyczy przeszukiwania bazy danych składającej się z M 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 M danych chcemy znaleźć nazwisko posiadacza danego numeru. O ile liczba kroków niezbędna do rozwiązania problemu za pomocą algorytmu klasycznego jest rzędu M, o tyle kwantowy algorytm Grovera potrzebuje jedynie około M0,5 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.

Zobacz też[edytuj | edytuj kod]

Przypisy

  1. Grover L.K.: From Schrödinger's equation to quantum search algorithm, American Journal of Physics, 69(7): 769-777, 2001

Bibliografia[edytuj | edytuj kod]

  • Mika Hirvensalo, Algorytmy kwantowe, WSiP, Warszawa 2004, ISBN 83-02-09155-3
  • Krzysztof Giaro, Marcin Kamiński, Wprowadzenie do algorytmów kwantowych, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2003, ISBN 83-87674-57-5