Algorytm Grovera

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 M½ 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]