Math
Wyszukiwanie Grovera
Poznaj amplitudę wzmocnienia w nieustrukturyzowanym wyszukiwaniu. Wyrocznia fazowa zmienia znak zaznaczonej amplitudy bez zmiany prawdopodobieństw w podstawie obliczeniowej. Krok dyfuzji zamienia fazę względną w wyższe prawdopodobieństwo sukcesu. Zbyt wiele iteracji ponownie zmniejsza to prawdopodobieństwo.
Co się dzieje
Wyrocznia faz oznacza kandydata poprzez zmianę jego względnej fazy. Pomiar natychmiast w bazie obliczeniowej daje takie same prawdopodobieństwa jak przed wyrocznią; Nie sprawia to, że faza względna jest nieobserwowalna w każdej bazie pomiarowej. Zakłócenia w etapie dyfuzji przekształcają znak fazowy w wzmocnienie amplitudy.
Jedna iteracja Grover składa się z wyroczni i dyfuzji. Prawdopodobieństwo sukcesu oscyluje raczej niż zbiega się: zatrzymaj się w pobliżu pierwszego maksimum, a następnie porównaj z późniejszymi iteracjami. Liczba zapytań jest skalowana z pierwiastkiem kwadratowym rozmiaru przestrzeni wyszukiwania dla pojedynczego oznaczonego elementu; Konstrukcja wyroczni i przygotowanie danych również mają koszty. Moduł pokazuje idealną symulację wektorową stanu, dokładne amplitudy racjonalne dla wybranych wielkości i powtarzalne liczby pomiarów próbek.
Równania modułu
Równania sin θ = 1/√N; po k obrotach amplituda oznaczonego elementu wynosi sin((2k+1)θ), a szansa jest jej kwadratem jeden obrót = jedno wywołanie wyroczni (znak minus przy wyróżnionej amplitudzie) + jedno odbicie względem średniej: a -> 2·mean − a optymalna liczba obrotów k* = floor(π/4·√N) = 3, 6, 12, 25 dla N = 16, 64, 256, 1024; ślepe przeszukiwanie wymaga średnio (N + 1)/2 = 8.5, 32.5, 128.5, 512.5 dla N = 4^m amplituda jest dokładnym UŁAMKIEM, dzięki rekurencji całkowitoliczbowej u(k+1) = (2q² − 4)·u(k) − q⁴·u(k−1) przy q = 2^(n/2), sin((2k+1)θ) = u(k)/q^(2k+1) szesnaście elementów: 1/4, 11/16, 61/64, 251/256 (k* = 3), 781/1024, 1451/4096, −2339/16384 (k = 6, szansa 0.0204 - gorsza niż początkowe 0.0625), … , 2269261/67108864 (k = 12) sześćdziesiąt cztery elementy po sześciu obrotach: 133988401/134217728 = 0.99829138070344925, co rejestr odtwarza co do ostatniego bitu pomiar wobec zliczeń: 2000 uruchomień przy k* daje 1913, 1994, 2000, 2000 trafień dla N = 16, 64, 256, 1024 - każdy wynik w granicach trzech sigm od dokładnej szansy
