Algoritmo de Búsqueda de Grover
Encuentra una aguja en un pajar en √N pasos en vez de N
¿Por qué √N y no más rápido? 🖖
El algoritmo de Grover alcanza O(√N) consultas, y esto es demostrablemente óptimo. Cada iteración gira el estado θ ≈ 2/√N radianes.
Cómo se amplifica la respuesta correcta 🖖
En una superposición uniforme, cada candidato empieza con la misma amplitud diminuta. Cada ronda hace dos cosas: un oráculo invierte el signo de la amplitud del objetivo y luego una 'inversión respecto a la media' refleja todas las amplitudes en torno a su promedio, subiendo la marcada y bajando el resto. Al repetir, la probabilidad del objetivo se acerca a 1. Para una lista de N = 1,000,000, una búsqueda clásica revisa 500,000 entradas en promedio; Grover solo necesita unas 1,000.
Cuatro elementos, un paso, certeza 🖖
Para N = 4 —una búsqueda de dos cúbits— Grover no solo es rápido, sino exacto: una sola iteración da con el objetivo con 100% de probabilidad. El ángulo de rotación cumple sin(θ/2) = 1/√N = 1/2, así que θ = 60°, y tras un paso el estado ha girado exactamente (2·1+1)·30° = 90° hasta el eje del objetivo. Es el raro caso en que un algoritmo cuántico da una respuesta garantizada y no solo probable.
Problemas de ejemplo
- N = 4 - N=4 elementos: solo se necesita 1 iteración de Grover para hallar el objetivo
- N = 8 - N=8 elementos: ~2 iteraciones óptimas, el tamaño clásico de demostración
- N = 16 - N=16 elementos: 3 iteraciones óptimas, se hace visible O(√N)
- N = 32 - N=32 elementos: ~4 iteraciones, muestra la ventaja cuadrática