Math
La búsqueda de Grover
Explora la amplificación de amplitud en una búsqueda no estructurada. Un oráculo de fase cambia el signo de la amplitud marcada sin cambiar las probabilidades en la base computacional. El paso de difusión convierte la fase relativa en una mayor probabilidad de éxito.
Qué ocurre
El oráculo de fases marca a un candidato cambiando su fase relativa. Medir inmediatamente en la base computacional da las mismas probabilidades que antes del oráculo; Esto no hace que la fase relativa sea inobservable en cada base de medición. La interferencia en el paso de difusión convierte la marca de fase en amplificación de amplitud.
Una iteración Grover consiste en el oráculo y la difusión. La probabilidad de éxito oscila en lugar de converger: detente cerca del primer máximo, luego compara con iteraciones posteriores. El recuento de consultas escala con la raíz cuadrada del tamaño del espacio de búsqueda para un único elemento marcado; La construcción del oráculo y la preparación de los datos también tienen costos. El módulo muestra una simulación vectorial de estado ideal, amplitudes racionales exactas para sus tamaños seleccionados y conteos reproducibles de muestreo de medición.
Ecuaciones del módulo
Ecuaciones sin θ = 1/√N; tras k giros la amplitud marcada es sin((2k+1)θ) y la probabilidad es su cuadrado un giro = una consulta al oráculo (un signo menos en la amplitud marcada) + una reflexión respecto a la media: a -> 2·mean − a número óptimo de giros k* = floor(π/4·√N) = 3, 6, 12, 25 para N = 16, 64, 256, 1024; una búsqueda a ciegas promedia (N + 1)/2 = 8.5, 32.5, 128.5, 512.5 para N = 4^m la amplitud es una FRACCIÓN exacta, por la recursión entera u(k+1) = (2q² − 4)·u(k) − q⁴·u(k−1) con q = 2^(n/2), sin((2k+1)θ) = u(k)/q^(2k+1) dieciséis elementos: 1/4, 11/16, 61/64, 251/256 (k* = 3), 781/1024, 1451/4096, −2339/16384 (k = 6, probabilidad 0.0204 - peor que el 0.0625 del que partió), … , 2269261/67108864 (k = 12) sesenta y cuatro elementos tras seis giros: 133988401/134217728 = 0.99829138070344925, que el registro reproduce hasta el último bit contraste con el recuento: 2000 ejecuciones en k* dan 1913, 1994, 2000, 2000 aciertos para N = 16, 64, 256, 1024 - cada uno a menos de tres sigmas de la probabilidad exacta
