Algorytm Grovera

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Algorytm Grovera
ilustracja
Rodzaj algorytm kwantowy, przeszukiwanie N-elementowego zbioru
Struktura danych rejestr kwantowy
Złożoność
Czasowa
Pamięciowa zależnie od implementacji

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

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[edytuj | edytuj kod]

O ile liczba kroków niezbędna do rozwiązania problemu za pomocą algorytmu klasycznego jest rzędu , o tyle kwantowy algorytm Grovera potrzebuje jedynie około 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[edytuj | edytuj kod]

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

.

2. W kolejnych iteracjach transformuj rejestr operatorem

gdzie jest stanem poszukiwanym, a następnie operatorem

.

Algorytm polega na iteracyjnym wykonywaniu operacji:

.

3. Przeprowadź pomiar rejestru. Jego rezultatem będzie wartość własna z prawdopodobieństwem dążącym do 1 dla N ≫ 1. Na jej podstawie można określić stan poszukiwany .

Zobacz też[edytuj | edytuj kod]

Przypisy[edytuj | edytuj kod]

  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[edytuj | edytuj kod]