Algoritmo de Grover

En computación cuántica, el algoritmo de Grover es un algoritmo cuántico para la búsqueda en una secuencia no ordenada de datos con N componentes en un tiempo O (N^1/2), y con una necesidad adicional de espacio de almacenamiento de O(logN) (véase notación O). Fue inventado por Lov K. Grover en 1996.

En una búsqueda normal de un dato, si tenemos una secuencia desordenada se debe realizar una inspección lineal, que necesita un tiempo de O (N), por lo que el algoritmo de Grover es una mejora bastante sustancial, evitando, además, la necesidad de la ordenación previa. La ganancia obtenida es cuadrática, lo que contrasta con otras mejoras de los algoritmos cuánticos que obtienen mejoras de orden exponencial sobre sus contrapartidas clásicas.

Al igual que otros algoritmos de naturaleza cuántica, el algoritmo de Grover es un algoritmo de carácter probabilístico, por lo que produce la respuesta correcta con una determinada probabilidad de error, que, no obstante, puede obtenerse tan baja como se desee por medio de iteraciones.

Aplicaciones

Aunque el propósito del algoritmo es, como ha sido indicado, la búsqueda en una secuencia, se podría describir de una manera más adecuada como la "inversión de una función". Así, si tenemos la función y=f (x), que puede ser evaluada en un computador cuántico, este algoritmo nos permite calcular el valor de x cuando se nos da como entrada el valor de y. Invertir una función puede relacionarse con la búsqueda en una secuencia, si consideramos que la misma es una función que produce el valor de y como la posición ocupada por el valor x en dicha secuencia.

El algoritmo de Grover también se puede utilizar para el cálculo de la media y la mediana de un conjunto de números, y para resolver otros problemas de naturaleza análoga. También se puede utilizar para resolver algunos problemas de naturaleza NP-completa, por medio de inspecciones exhaustivas en un espacio de posibles soluciones. Esto resulta en una apreciable mejora sobre soluciones clásicas.

Descripción

Inicialización

Se considera una secuencia desordenada con N componentes. El algoritmo requiere un espacio de estados N-dimensional H, que puede ser modelado con log₂N qubits.

Numeremos las entradas de la secuencia con 0, 1,... (N-1); y seleccionemos un observable Ω, actuando sobre H, con N autovalores distintos conocidos. Cada uno de los autovalores de Ω codifica una de las entradas de la secuencia, de una forma que se describirá más adelante. Denotaremos los autoestados utilizando la notación bra-ket en la forma:

${\displaystyle \{|0\rangle ,|1\rangle ,\cdots ,|N-1\rangle \}}$

y los autovalores correspondientes como

${\displaystyle \{\lambda _{0},\lambda _{1},\cdots ,\lambda _{N-1}\}}$

Ahora tomamos un operador unario, U_ω, que actúa como una subrutina que compara las diferentes entradas de acuerdo al criterio de búsqueda. El algoritmo no especifica cómo funciona la subrutina, pero debe ser una subrutina cuántica que trabaje bajo una superposición de estados. Además, debe actuar de manera especial sobre uno de los autoestados, |ω>, que corresponderá con la entrada que satisface el criterio de búsqueda. Más precisamente, requeriremos U_ω con los siguientes efectos:

${\displaystyle U_{\omega }|\omega \rangle =-|\omega \rangle }$

${\displaystyle U_{\omega }|x\rangle =|x\rangle \qquad {\mbox{para todo}}\ x\neq \omega }$

En concreto,

${\displaystyle \langle \omega |\omega \rangle =1}$.

${\displaystyle \langle \omega |x\rangle =\langle x|\omega \rangle =0}$.

${\displaystyle U_{\omega }|\omega \rangle =(I-2|\omega \rangle \langle \omega |)|\omega \rangle =|\omega \rangle -2|\omega \rangle \langle \omega |\omega \rangle =-|\omega \rangle }$.

${\displaystyle U_{\omega }|x\rangle =(I-2|\omega \rangle \langle \omega |)|x\rangle =|x\rangle -2|\omega \rangle \langle \omega |x\rangle =|x\rangle }$.

Nuestro objetivo es identificar el autoestado |ω>, o de manera equivalente, el autovalor ω, tal que U_ω actúa especialmente sobre él.

Iteraciones del algoritmo

Los pasos del algoritmo de Grover son los siguientes:

1. Inicializar el sistema al estado

   ${\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x}|x\rangle }$

2. Realizar la siguiente iteración r (N) veces. Donde la función r (N) se describe más adelante.
   1. Aplicar el operador ${\displaystyle U_{\omega }}$
   2. Aplicar el operador ${\displaystyle U_{s}=2\left|s\right\rangle \left\langle s\right|-I}$.
3. Realizar la medida Ω. La medida corresponderá al valor λ_ω con una cierta probabilidad que se puede aproximar a 1, para un cierto N>>1. A partir de λ_ω, se puede obtener ω.

Podemos escribir las operaciones realizadas:

${\displaystyle \langle s|s\rangle =1}$.

${\displaystyle \langle \omega |s\rangle =\langle s|\omega \rangle ={\frac {1}{\sqrt {N}}}}$.

${\displaystyle U_{\omega }|s\rangle =(I-2|\omega \rangle \langle \omega |)|s\rangle =|s\rangle -2|\omega \rangle \langle \omega |s\rangle =|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle }$.

${\displaystyle U_{s}(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )=(2\left|s\right\rangle \left\langle s\right|-I)(|s\rangle -{\frac {2}{\sqrt {N}}}|\omega \rangle )}$

${\displaystyle =2\left|s\right\rangle \left\langle s\right|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}\left|s\right\rangle \left\langle s\right|\omega \rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle }$

${\displaystyle =2|s\rangle -|s\rangle -{\frac {4}{\sqrt {N}}}\cdot {\frac {1}{\sqrt {N}}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle ={\frac {N-4}{N}}|s\rangle +{\frac {2}{\sqrt {N}}}|\omega \rangle }$

${\displaystyle ={\frac {1}{N{\sqrt {N}}}}\left((N-4)\sum _{x\neq w}|x\rangle +(3N-4)|\omega \rangle \right)}$

Después de aplicar los dos operadores ( ${\displaystyle U_{\omega }}$ y ${\displaystyle U_{s}}$ ), la amplitud del elemento buscado se ve incrementado. Y esta es una iteración de Grover.

Número de iteraciones

Ahora consideramos el plano definido por |s> y |ω>. Sea |ω^×> que es perpendicular a |ω>. Entonces |ω> es uno de los vectores base, y tenemos

${\displaystyle \langle \omega |s\rangle ={\frac {1}{\sqrt {N}}}}$

En términos geométricos, hay un ángulo (π/2 - θ) entre |ω> y |s>, donde θ dado por:

${\displaystyle \cos \left({\frac {\pi }{2}}-\theta \right)={\frac {1}{\sqrt {N}}}}$

${\displaystyle \sin \theta ={\frac {1}{\sqrt {N}}}}$

El operador U_ω es un reflejo del hiperplano ortogonal a |ω> para los vectors en el plano definido por |s> y |ω>, además, actúa como un reflejo de la línea |ω^×>. El operador U_s es un reflejo de la línea |s>.

Entonces, el vector de estado permanece en el plano de |s> y |ω> tras cada aplicación de U_s y tras cada aplicación de U_ω, y se puede comprobar que el operador U_sU_ω de cada paso de iteración rota el vector de estado en un ángulo de 2θ hacia |ω>.

El algoritmo se detendrá cuando el vector de estado se acerca a |ω> tras esto, las siguientes iteraciones rotan el vector de estado fuera de |ω>, reduciendo la probabilidad de obtener la respuesta correcta. El número de iteraciones necesarias es dado por r. Para alinear correctamente el vector de estado con |ω>, necesitamos:

${\displaystyle {\frac {\pi }{2}}-\theta =2\theta r}$

${\displaystyle r={\frac {({\frac {\pi }{\theta }}-2)}{4}}}$

Una consideración es que r debe ser entero, por lo que, en general, r será el entero más cercano a (π/θ - 2)/4. Entonces, el ángulo entre |ω> y el vector de estado final es O(θ), y la probabilidad de obtener una respuesta incorrecta es O(1 - cos²θ) = O (sin²θ).

Entonces, para N>>1, θ ≈ N^-1/2, tenemos

${\displaystyle r\rightarrow {\frac {\pi {\sqrt {N}}}{4}}}$

Además, la probabilidad de obtener una respuesta incorrecta será O(1/N), que tiende a 0 para un valor de N suficientemente elevado.

Implementación

A continuación presentamos una implementación concreta del algoritmo de Grover. Supongamos que tenemos una secuencia de 2ⁿ elementos que vamos a referenciar por su índice x. Supongamos también que disponemos de una función f (x) que nos dice si el valor almacenado en la posición x es el que estamos buscando. En concreto sea f (x)=1 para el valor buscado y f (x)=0 para el resto.

Oráculo

Oráculo.

A partir de la función f (x) vamos a construir un oráculo, tal como se muestra en la figura de la derecha. El funcionamiento de este bloque es el mismo que el correspondiente del algoritmo de Deutsch-Jozsa. La operación de este bloque es:

${\displaystyle U_{f}(|x\rangle (|0\rangle -|1\rangle ))=(-1)^{f(x)}|x\rangle |(|0\rangle -|1\rangle )}$

Puesto que el último estado no se modifica, vamos a ignorarlo y escribiremos:

${\displaystyle U_{f}(|x\rangle )=(-1)^{f(x)}|x\rangle }$

Inversión sobre la media

Inversión sobre la media.

El bloque que lo realiza se muestra en la figura de la derecha. Esta operación puede escribirse:

${\displaystyle H^{\oplus n}(2|0\rangle \langle 0|-I)H^{\oplus n}=2|\psi \rangle \langle \psi |-I}$

con ${\displaystyle \textstyle \psi ={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle }$.

Esta operación se interpreta como inversión sobre la media, pues si lo aplicamos sobre un estado genérico ${\displaystyle \textstyle a=\sum _{x=0}^{2^{n}-1}a_{x}|x\rangle }$, obtenemos:

${\displaystyle (2|\psi \rangle \langle \psi |-I)(\sum _{x=0}^{2^{n}-1}a_{x}|x\rangle )=\sum _{x=0}^{2^{n}-1}\left(2\langle a\rangle -a_{x}\right)|x\rangle }$,

en donde ${\displaystyle \textstyle \langle a\rangle =(1/2^{n})\sum _{x=0}^{2^{n}-1}a_{x}}$

Iteración de Grover

Algoritmo de Grover. En detalle se muestra una de las iteraciones.

Una iteración de Grover se compone de dos pasos:

1. Aplicación del oráculo
2. Inversión sobre la media

Por tanto, la iteración de Grover puede escribirse:

${\displaystyle G_{f}=(2|\psi \rangle \langle \psi |-I)U_{f}}$.

El algoritmo completo se muestra en la figura de la derecha.

Interpretación

Hagamos las cuentas para la primera iteración de Grover. Preparamos un estado haciendo pasar el qubit |0> (realmente compuesto de n ceros) a través de una puerta de Hadamard:

${\displaystyle |a\rangle =H^{\oplus n}|0\rangle ={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}|x\rangle }$

Este estado pasa a través del oráculo, obteniendo:

${\displaystyle |b\rangle =U_{f}(|a\rangle )={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(-1)^{f(x)}|x\rangle }$

A continuación, aplicamos la inversión sobre la media, y obtenemos:

${\displaystyle |c\rangle =(2|\psi \rangle \langle \psi |-I)(|b\rangle )={\frac {1}{\sqrt {2^{n}}}}\sum _{x=0}^{2^{n}-1}(2<b>-b_{x})|x\rangle }$

${\displaystyle ={\frac {1}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0}^{2^{n}-1}\left(2\left(\sum _{y=0}^{2^{n}-1}b_{y}\right)-2^{n}b_{x}\right)|x\rangle }$

${\displaystyle ={\frac {1}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0}^{2^{n}-1}\left(2\left(\sum _{y=0}^{2^{n}-1}(-1)^{f(y)}\right)-2^{n}(-1)^{f(x)}\right)|x\rangle }$

Interpretemos ahora este resultado. Supongamos que en la posición x_i se encuentra el valor buscado, esto es, f (x_i)=1 y para el resto, f (x)=0, obtenemos:

${\displaystyle |c\rangle ={\frac {1}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0}^{2^{n}-1}\left(2\left((2^{n}-1)(+1)+(-1)\right)-2^{n}(-1)^{f(x)}\right)|x\rangle }$

${\displaystyle ={\frac {2^{n+1}+2^{n}-4}{2^{n}{\sqrt {2^{n}}}}}|x_{i}\rangle +{\frac {2^{n+1}-2^{n}-4}{2^{n}{\sqrt {2^{n}}}}}\sum _{x=0,x\neq x_{i}}^{2^{n}-1}|x\rangle }$

Como puede observarse, el término que nos interesa aumenta su amplitud en comparación con los demás términos. Repitiendo esta operación en varias iteraciones, este efecto se verá incrementado. Si al final del algoritmo hacemos una medición, muy probablemente obtendremos el valor buscado.

Véase también

• Algoritmo de Shor

Referencias

1. Grover L.K.: A fast quantum mechanical algorithm for database search. Presentación original del algoritmo (en inglés).
2. Grover L.K.: From Schrödinger's equation to quantum search algorithm. Versión pedagógica del algoritmo e historia (en inglés).
3. https://web.archive.org/web/20140201230754/http://www.bell-labs.com/user/feature/archives/lkgrover/
4. Notas de las Charlas Introductorias a la Computación Cuántica (Alejandro Díaz-Caro).
5. Michael A. Nielsen e Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, Reino Unido, 2000, ISBN 0-521-63503-9.

• Datos: Q1028292