Algorytm Grovera

Szablon:Algorytm infobox Algorytm Grovera – algorytm kwantowy przeznaczony do działania na komputerze kwantowym, przedstawiony przez Lova K. Grovera w 1996 i opublikowany w 2001.

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 $O(N)$, o tyle kwantowy algorytm Grovera potrzebuje jedynie około $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

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

2. W kolejnych iteracjach transformuj rejestr operatorem

$U_{\omega }=I-2|\omega ⟩⟨\omega |$

gdzie $|\omega ⟩$ jest stanem poszukiwanym, a następnie operatorem

$U_s=2|s⟩⟨s|-I.$

Algorytm polega na iteracyjnym wykonywaniu operacji:

$|s_{i+1}⟩=U_s{U}_{\omega }|s_i⟩.$

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

Zobacz też

• informatyka kwantowa
• komputer kwantowy
• kryptologia kwantowa

Bibliografia

• Szablon:Cytuj
• Krzysztof Giaro, Marcin Kamiński, Wprowadzenie do algorytmów kwantowych, Akademicka Oficyna Wydawnicza EXIT, Warszawa 2003, Szablon:ISBN.