Math
La recherche de Grover
Explorez l'amplification d'amplitude dans une recherche non structurée. Un oracle de phase change le signe de l'amplitude marquée sans changer les probabilités dans la base de calcul. L'étape de diffusion transforme la phase relative en une probabilité de succès plus élevée. Trop d'itérations réduisent à nouveau cette probabilité.
Ce qui se passe
L'oracle de phase marque un candidat en changeant sa phase relative. Mesurer immédiatement dans la base de calcul donne les mêmes probabilités qu'avant l'oracle; Cela ne rend pas la phase relative inobservable dans chaque base de mesure. L'interférence dans l'étape de diffusion convertit la marque de phase en amplification d'amplitude.
Une itération Grover se compose de l'oracle et de la diffusion. La probabilité de succès oscille plutôt que de converger : arrêtez-vous près du premier maximum, puis comparez avec les itérations ultérieures. Le nombre de requêtes évolue avec la racine carrée de la taille de l'espace de recherche pour un seul élément marqué; La construction de l'oracle et la préparation des données ont également des coûts. Le module montre une simulation d'état-vecteur idéal, des amplitudes rationnelles exactes pour ses tailles sélectionnées, et des comptes de mesure échantillonnés reproductibles.
Équations du module
Équations sin θ = 1/√N ; après k tours l'amplitude de l'élément marqué est sin((2k+1)θ) et la probabilité en est le carré un tour = un appel à l'oracle (un signe moins sur l'amplitude marquée) + une réflexion autour de la moyenne : a -> 2·mean − a nombre optimal de tours k* = floor(π/4·√N) = 3, 6, 12, 25 pour N = 16, 64, 256, 1024 ; une recherche à l'aveugle demande en moyenne (N + 1)/2 = 8.5, 32.5, 128.5, 512.5 pour N = 4^m l'amplitude est une FRACTION exacte, par la récurrence entière u(k+1) = (2q² − 4)·u(k) − q⁴·u(k−1) avec q = 2^(n/2), sin((2k+1)θ) = u(k)/q^(2k+1) seize éléments : 1/4, 11/16, 61/64, 251/256 (k* = 3), 781/1024, 1451/4096, −2339/16384 (k = 6, probabilité 0.0204 - pire que les 0.0625 du départ), … , 2269261/67108864 (k = 12) soixante-quatre éléments après six tours : 133988401/134217728 = 0.99829138070344925, que le registre reproduit jusqu'au dernier bit mesuré face au compté : 2000 exécutions à k* donnent 1913, 1994, 2000, 2000 succès pour N = 16, 64, 256, 1024 - chacun à moins de trois sigma de la probabilité exacte
