Búsqueda de Grover: amplificación de amplitud y complejidad de consulta oracular

Sea \(\mathcal{X} = \{0, 1, \ldots, N-1\}\) un espacio de búsqueda de \(N = 2^n\) elementos y \(f: \mathcal{X} \to \{0,1\}\) una función que marca exactamente un elemento \(x^* \in \mathcal{X}\) con \(f(x^*) = 1\). El objetivo es encontrar \(x^*\) consultando al oráculo \(\mathcal{O}_f\) el mínimo número de veces.

Cualquier algoritmo clásico (determinista o probabilístico) necesita \(\Omega(N)\) consultas para localizar \(x^*\) con alta probabilidad. El algoritmo de Grover requiere únicamente \(\mathcal{O}(\sqrt{N})\) consultas, lo que para \(N = 2^{64}\) representa la diferencia entre \(10^{19}\) y \(\approx 4 \times 10^9\) operaciones.

El algoritmo opera iterando dos operadores unitarios sobre el estado inicial de superposición uniforme \(|s\rangle = H^{\otimes n}|0\rangle^{\otimes n} = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle\).

Operador oráculo \(\mathcal{O}\): refleja la fase del estado marcado: \[ \mathcal{O}|x\rangle = (-1)^{f(x)}|x\rangle. \] Geometricamente, esta operación invierte el signo de la componente \(|x^*\rangle\), separándola de la superposición uniforme.

Operador de difusión de Grover \(\mathcal{D}\): realiza la inversión alrededor de la media de las amplitudes: \[ \mathcal{D} = 2|s\rangle\langle s| - I = H^{\otimes n}(2|0\rangle\langle 0| - I)H^{\otimes n}. \] Esta operación amplifica la amplitud del estado marcado a expensas de los estados no marcados. Cada iteración \(G = \mathcal{D} \circ \mathcal{O}\) incrementa la amplitud de \(|x^*\rangle\) en un factor \(\approx \sqrt{N}^{-1}\).

Después de \(k\) iteraciones de \(G\), la probabilidad de medir \(|x^*\rangle\) es: \[ P(x^*) = \sin^2\!\left((2k+1)\theta\right), \quad \theta = \arcsin\!\left(\frac{1}{\sqrt{N}}\right). \] El número óptimo de iteraciones que maximiza \(P(x^*)\) es: \[ k^* = \left\lfloor\frac{\pi}{4}\sqrt{N}\right\rfloor. \] Para \(N = 4\) (\(n = 2\) cúbits), \(k^* = 1\) y la probabilidad teórica de éxito es exactamente \(1\) (no hay error de búsqueda en el caso ideal). Esta propiedad hace del caso de 2 cúbits el ejemplo pedagógico ideal para introducir Grover sin el factor de aproximación presente en espacios de mayor dimensión.

Sea \(\mathcal{A}\) el subespacio de dimensión dos generado por \(|w\rangle\) (estado marcado normalizado) y \(|s'\rangle\), la superposición uniforme sobre los estados no marcados. El operador de Grover restringido a \(\mathcal{A}\) es una rotación de ángulo \(2\theta\) en dirección determinada por la composición de reflexión respecto de \(|s\rangle\) y respecto de \(|w\rangle\). Por ello, aplicar \(G\) más veces de lo óptimo «pasa de largo» el objetivo y la probabilidad de éxito disminuye; este fenómeno es observable numéricamente al variar el número de iteraciones en simuladores.

Para \(N=4\) y una solución, \(\theta = \pi/6\) y una única iteración alcanza probabilidad unitaria en el modelo ideal; el ejemplo de dos cúbits de esta guía es, por tanto, el caso marginal donde la aproximación continua coincide exactamente con la dinámica finita.

Bennett, Bernstein, Brassard y Vazirani demostraron que, para búsqueda no estructurada en el modelo de oráculo, \(\Omega(\sqrt{N})\) consultas son necesarias incluso para algoritmos cuánticos. Grover alcanza asintóticamente esa cota, de modo que el algoritmo es óptimo en orden de magnitud. La generalización de Brassard–Høyer–Mosca–Tapp encapsula \(G\) dentro de la amplificación de amplitud, subrutina estándar en estimación de fase y conteo cuántico.