Math
La ricerca di Grover
Esplora l'amplificazione dell'ampiezza in una ricerca non strutturata. Un oracolo di fase cambia il segno dell'ampiezza marcata senza cambiare le probabilità nella base computazionale. Il passaggio di diffusione trasforma la fase relativa in una maggiore probabilità di successo. Troppi iterazioni riducono di nuovo quella probabilità.
Cosa succede
L'oracolo di fase contrassegna un candidato cambiando la sua fase relativa. Misurare immediatamente nella base computazionale dà le stesse probabilità di prima dell’oracolo; Questo non rende la fase relativa inosservabile in ogni base di misura. L'interferenza nel punto di diffusione converte il segno di fase nell'amplificazione di ampiezza.
Una iterazione Grover consiste dell'oracolo e della diffusione. La probabilità di successo oscilla piuttosto che convergere: fermarsi vicino al primo massimo, quindi confrontare con iterazioni successive. Il conteggio delle query scala con la radice quadrata della dimensione dello spazio di ricerca per un singolo elemento contrassegnato; La costruzione dell'oracolo e la preparazione dei dati hanno anche costi. Il modulo mostra una simulazione ideale dello stato-vettore, le ampiezze razionali esatte per le sue dimensioni selezionate ed i conteggi campionati riproducibili della misura.
Equazioni del modulo
Equazioni sin θ = 1/√N; dopo k giri l'ampiezza marcata è sin((2k+1)θ) e la probabilità ne è il quadrato un giro = una chiamata all'oracolo (un segno meno sull'ampiezza marcata) + una riflessione rispetto alla media: a -> 2·mean − a numero ottimale di giri k* = floor(π/4·√N) = 3, 6, 12, 25 per N = 16, 64, 256, 1024; una ricerca alla cieca richiede in media (N + 1)/2 = 8.5, 32.5, 128.5, 512.5 per N = 4^m l'ampiezza è una FRAZIONE esatta, data dalla ricorrenza intera u(k+1) = (2q² − 4)·u(k) − q⁴·u(k−1) con q = 2^(n/2), sin((2k+1)θ) = u(k)/q^(2k+1) sedici elementi: 1/4, 11/16, 61/64, 251/256 (k* = 3), 781/1024, 1451/4096, −2339/16384 (k = 6, probabilità 0.0204 - peggiore dello 0.0625 di partenza), … , 2269261/67108864 (k = 12) sessantaquattro elementi dopo sei giri: 133988401/134217728 = 0.99829138070344925, che il registro riproduce fino all'ultimo bit misurato a confronto con il conteggio: 2000 esecuzioni con k* danno 1913, 1994, 2000, 2000 successi per N = 16, 64, 256, 1024 - ognuno entro tre sigma dalla probabilità esatta
