Algoritmo de Búsqueda de Grover

Encuentra una aguja en un pajar en √N pasos en vez de N

Ejemplo resuelto — Algoritmo de Búsqueda de Grover

Iteración actual	0 (Superposición)
Probabilidad objetivo	12.50%
Clásico (1/N)	12.50%
Iteración	0 / 2 · Superposición

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

¿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.

Problema resuelto al detalle

Dos iteraciones para encontrar un elemento marcado entre 8 5 pasos
El algoritmo de Grover encuentra un elemento marcado entre 8 en dos iteraciones. Deduzca de dónde sale ese dos y qué ocurre si se ejecuta una tercera.
1. Antes de ejecutar nada, el estado es una superposición uniforme: cada elemento es igualmente probable, por lo que el marcado contiene 1/8 de la probabilidad. Eso equivale a una estimación aleatoria clásica, y el panel muestra ambas para dejarlo claro.
  
  $N = 8 : uniform superposition gives P = \frac{1}{8} = 12.50%$
2. Cada iteración de Grover es una rotación según un ángulo fijo en un plano bidimensional generado por el estado marcado y todo lo demás. El ángulo proviene de la amplitud, y para N = 8 es de unos 20,7°.
  
  $sin θ = \frac{1}{N} ⟹ θ = 20.7 0^{\circ}; P_{k} = sin^{2} ((2 k + 1) θ)$
3. Así pues, la probabilidad no es una curva que asciende y se estabiliza: es un seno al cuadrado, y asciende de forma pronunciada: 12,5%, luego 78,1% y después 94,5%.
  
  $k = 1 : 78.12%; k = 2 : 94.53%; k = 3 : 33.01%$
4. El punto de parada óptimo es la rotación que queda más cerca de los 90°, que es π/4 veces la raíz cuadrada de N. Para ocho elementos eso es 2,22, y como no se puede realizar una iteración fraccionaria, queda en 2.
  
  $k_{opt} = ⌊ \frac{π}{4} N ⌋ = ⌊ 2.221 ⌋ = 2$
5. Si se ejecuta una tercera, la rotación sobrepasa el objetivo. La probabilidad cae al 33,0%, peor que tras una iteración, y vuelve hacia el punto de partida.
  
  $classical \sim \frac{N}{2} = 4 queries vs O (N) = 2$
Respuesta

La herramienta muestra 12,50 % tanto para la superposición inicial como para el caso clásico de 1 entre N, y detiene la ejecución automática en 2, aunque los controles para avanzar un paso o saltar al final permiten llegar hasta 5. Lo que suele sorprender es el exceso: hacer más iteraciones empeora el resultado, porque la amplificación de amplitud es una rotación y, al seguir girando, se vuelve al punto de partida. Por eso la aceleración de Grover es cuadrática, no exponencial: hacen falta unas √N rotaciones para alcanzar 90°; con 8 elementos bastan 2 y con un millón se necesitan 785. Es una mejora considerable, pero dista mucho de la ventaja exponencial que parece prometer la expresión «búsqueda cuántica».

$P_{k} = sin^{2} ((2 k + 1) θ) ROTATES : past k_{opt} it falls again$

Referencias (1)

The algorithm this tool steps through: L. K. Grover, "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219, 1996.

Por el equipo de 42Math · Actualizado 2026-07-29

Contrastado con fuentes publicadas. Se agradecen correcciones. Política editorial · Correcciones

Todas las lecciones de Informática →

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