Algoritmo de Grover: Buscar con rotaciones

Imagina una guía telefónica con $N$ entradas desordenadas y un único nombre que buscas. Sin ninguna estructura que ayude, la única estrategia clásica es mirar entrada a entrada: $N / 2$ consultas de media, $N$ en el peor caso. En 1996 Lov Grover, en los Laboratorios Bell, demostró que un ordenador cuántico puede encontrarlo con unas $\frac{π}{4} \sqrt{N}$ consultas. Para un millón de entradas, unas 800 en lugar de medio millón.

El problema

Tenemos $N = 2^{n}$ elementos y un oráculo que reconoce el marcado, $w$ : una función $f (x) = 1$ si $x = w$ y 0 si no. Cuánticamente, el oráculo actúa como un cambio de signo:

O | x ⟩ = (- 1)^{f (x)} | x ⟩, O = I - 2 | w ⟩ ⟨ w | .

El oráculo cambia el signo de la amplitud del elemento marcado pero, por sí solo, no cambia ninguna probabilidad. Algo tiene que convertir ese signo en probabilidad. Ese es el trabajo de la interferencia.

El algoritmo

Se parte de la superposición uniforme $| s ⟩ = H^{\otimes n} | 0 ⟩ = \frac{1}{\sqrt{N}} \sum_{x} | x ⟩$ y se repite $k$ veces la iteración de Grover:

G = D O, D = 2 | s ⟩ ⟨ s | - I .

El operador $D$ , llamado difusión, es una inversión respecto a la media: lleva cada amplitud $a_{x}$ a $2 \bar{a} - a_{x}$ , donde $\bar{a}$ es la media. Tras el oráculo, la amplitud marcada es negativa y queda muy por debajo de la media; al invertirla, sube muy por encima. Cada iteración bombea un poco más de amplitud hacia $| w ⟩$ .

El algoritmo de Grover paso a paso. Las barras son las amplitudes (reales, con signo) y la línea discontinua es su media. «Oráculo» cambia el signo del elemento marcado; «Difusión» refleja cada amplitud respecto a la media. La gráfica de la derecha muestra la probabilidad de éxito tras cada iteración: oscila como

\sin^{2} ((2 k + 1) θ)

, así que iterar de más es tan malo como iterar de menos.

La geometría: dos reflexiones forman una rotación

Todo el algoritmo ocurre en un plano de dos dimensiones. Sean $| w ⟩$ el estado marcado y $| w^{⟂} ⟩$ la superposición uniforme de los no marcados. El estado inicial está en el plano que generan:

| s ⟩ = \sin θ | w ⟩ + \cos θ | w^{⟂} ⟩, \sin θ = \frac{1}{\sqrt{N}} .

Teorema (la iteración de Grover es una rotación)

En el plano generado por $| w ⟩$ y $| w^{⟂} ⟩$ , el oráculo $O$ es la reflexión respecto a $| w^{⟂} ⟩$ y $D$ es la reflexión respecto a $| s ⟩$ . Su producto $G = D O$ es una rotación de ángulo $2 θ$ hacia $| w ⟩$ . Tras $k$ iteraciones,

G^{k} | s ⟩ = \sin ((2 k + 1) θ) | w ⟩ + \cos ((2 k + 1) θ) | w^{⟂} ⟩,

y la probabilidad de medir $w$ es $\sin^{2} ((2 k + 1) θ)$ .

Demostración

$O$ deja fijo $| w^{⟂} ⟩$ y cambia de signo $| w ⟩$ , así que es la reflexión respecto a la recta de $| w^{⟂} ⟩$ . $D = 2 | s ⟩ ⟨ s | - I$ deja fijo $| s ⟩$ y cambia de signo todo vector ortogonal a él: la reflexión respecto a la recta de $| s ⟩$ . La composición de dos reflexiones respecto a rectas que forman un ángulo $θ$ es una rotación de ángulo $2 θ$ (un resultado clásico de geometría plana). El estado inicial forma un ángulo $θ$ con $| w^{⟂} ⟩$ ; tras $k$ rotaciones, forma $(2 k + 1) θ$ .

Para llegar a $| w ⟩$ queremos $(2 k + 1) θ \approx π / 2$ , es decir,

k \approx \frac{π}{4 θ} - \frac{1}{2} \approx \frac{π}{4} \sqrt{N},

ya que $θ \approx 1 / \sqrt{N}$ para $N$ grande. Con $M$ elementos marcados, $\sin θ = \sqrt{M / N}$ y hacen falta unas $\frac{π}{4} \sqrt{N / M}$ iteraciones. La aceleración cuadrática viene de que la probabilidad es el cuadrado de la amplitud: la amplitud crece linealmente con $k$ , así que solo tiene que llegar a $1$ partiendo de $1 / \sqrt{N}$ .

No se puede hacer mejor

Antes de que se conociera siquiera el algoritmo de Grover, Bennett, Bernstein, Brassard y Vazirani ya habían demostrado que sería óptimo.

Teorema (BBBV, 1997)

Todo algoritmo cuántico que encuentra el elemento marcado entre $N$ con probabilidad al menos $2 / 3$ , consultando el oráculo como una caja negra, debe hacer $Ω (\sqrt{N})$ consultas.

Idea de la demostración (argumento híbrido)

Ejecutamos el algoritmo con un oráculo que no marca nada. Tras $T$ consultas, el «peso de consulta» total que ha puesto sobre todos los elementos es $T$ , así que algún elemento $w$ ha recibido un peso de como mucho $T / N$ . Cambiar el oráculo para que marque $w$ perturba cada paso en una cantidad proporcional a la raíz cuadrada de ese peso, y las perturbaciones suman como mucho $O (T / \sqrt{N})$ en norma. Para distinguir las dos situaciones, los estados finales deben diferir en una constante, así que $T = Ω (\sqrt{N})$ .

Christof Zalka (1999) demostró que el algoritmo de Grover es óptimo incluso en la constante. La consecuencia es importante: para problemas sin estructura, los ordenadores cuánticos ofrecen una aceleración cuadrática, no exponencial. En particular, no se espera que resuelvan problemas NP-completos en tiempo polinómico simplemente «probando todas las respuestas a la vez».

Amplificación de amplitud

Brassard, Høyer, Mosca y Tapp (2002) generalizaron la idea. Si un algoritmo cuántico $𝒜$ acierta con probabilidad $p$ , se puede convertir en uno que acierta con alta probabilidad usando solo $O (1 / \sqrt{p})$ repeticiones de $𝒜$ y $𝒜^{- 1}$ , frente a las $O (1 / p)$ que necesita la repetición clásica. Es un acelerador cuadrático para casi cualquier subrutina cuántica.

Referencias

L. K. Grover (1996). «A fast quantum mechanical algorithm for database search». STOC.
C. H. Bennett, E. Bernstein, G. Brassard y U. Vazirani (1997). «Strengths and Weaknesses of Quantum Computing». SIAM J. Computing, 26(5).
M. Boyer, G. Brassard, P. Høyer y A. Tapp (1998). «Tight bounds on quantum searching». Fortschritte der Physik, 46.
C. Zalka (1999). «Grover's quantum searching algorithm is optimal». Physical Review A, 60(4).
G. Brassard, P. Høyer, M. Mosca y A. Tapp (2002). «Quantum amplitude amplification and estimation». Contemporary Mathematics, 305.

§El problema

§El algoritmo

§La geometría: dos reflexiones forman una rotación

§No se puede hacer mejor

§Amplificación de amplitud