Math
Grovers Suche
Ein Phasenorakel ändert das Vorzeichen der markierten Amplitude, ohne die Wahrscheinlichkeiten in der Berechnungsbasis zu ändern. Der Diffusionsschritt verwandelt die relative Phase in eine höhere Erfolgswahrscheinlichkeit. Zu viele Iterationen verringern diese Wahrscheinlichkeit wieder.
Was passiert
Das Phasenorakel markiert einen Kandidaten, indem es seine relative Phase ändert. Sofortige Messung in der rechnerischen Basis gibt die gleichen Wahrscheinlichkeiten wie vor dem Orakel; Dies macht die relative Phase nicht in jeder Messbasis unbeobachtbar. Interferenz im Diffusionsschritt wandelt die Phasenmarke in Amplitudenverstärkung um.
Eine Grover-Iteration besteht aus dem Orakel und der Diffusion. Die Erfolgswahrscheinlichkeit oszilliert statt zu konvergieren: Halten Sie nahe dem ersten Maximum an und vergleichen Sie dann mit späteren Iterationen. Die Anzahl der Abfragen skaliert mit der Quadratwurzel der Suchraumgröße für ein einzelnes markiertes Element. Der Bau des Orakels und die Aufbereitung der Daten haben ebenfalls Kosten. Das Modul zeigt eine ideale Zustandsvektorsimulation, exakte rationale Amplituden für die ausgewählten Größen und reproduzierbare Stichprobenmesszahlen.
Gleichungen des Moduls
Gleichungen sin θ = 1/√N; nach k Drehungen ist die markierte Amplitude sin((2k+1)θ) und die Trefferwahrscheinlichkeit ihr Quadrat eine Drehung = ein Orakelaufruf (ein Minuszeichen an der markierten Amplitude) + eine Spiegelung am Mittelwert: a -> 2·mean − a optimale Anzahl der Drehungen k* = floor(π/4·√N) = 3, 6, 12, 25 für N = 16, 64, 256, 1024; eine blinde Suche braucht im Mittel (N + 1)/2 = 8.5, 32.5, 128.5, 512.5 für N = 4^m ist die Amplitude ein exakter BRUCH, nach der ganzzahligen Rekursion u(k+1) = (2q² − 4)·u(k) − q⁴·u(k−1) mit q = 2^(n/2), sin((2k+1)θ) = u(k)/q^(2k+1) sechzehn Einträge: 1/4, 11/16, 61/64, 251/256 (k* = 3), 781/1024, 1451/4096, −2339/16384 (k = 6, Wahrscheinlichkeit 0.0204 - schlechter als die 0.0625, mit der sie begann), … , 2269261/67108864 (k = 12) vierundsechzig Einträge nach sechs Drehungen: 133988401/134217728 = 0.99829138070344925, was das Register bis auf das letzte Bit reproduziert gemessen gegen gezählt: 2000 Läufe bei k* ergeben 1913, 1994, 2000, 2000 Treffer für N = 16, 64, 256, 1024 - jeweils innerhalb von drei Sigma der exakten Wahrscheinlichkeit
