Algoritmo de Grover

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 (N1/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 "sólo" de la raíz cuadrada, 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[editar]

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[editar]

Inicialización[editar]

Se considera una secuencia desordenada con N componentes. El algoritmo requiere un espacio de estados N-dimensional H, que puede ser modelado con log2N 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:

\{|0\rang, |1\rang, \cdots, |N-1\rang\}

y los autovalores correspondientes como

\{\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 como 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:

 U_\omega |\omega\rang = - |\omega\rang
 U_\omega |x\rang = |x\rang \qquad \mbox{para todo}\ x \ne
\omega

En concreto,

 \langle \omega| \omega\rang =1.
 \langle \omega| x \rang =\langle x| \omega\rang =0.
 U_\omega |\omega\rang = (I-2| \omega\rangle \langle \omega|)|\omega\rang=|\omega\rang-2| \omega\rangle \langle \omega|\omega\rang=-|\omega\rangle .
 U_\omega |x\rang = (I-2| \omega\rangle \langle \omega|)|x\rang=|x\rang-2| \omega\rangle \langle \omega|x\rang=|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[editar]

Los pasos del algoritmo de Grover son los siguientes:

  1. Inicializar el sistema al estado
    |s\rang = \frac{1}{\sqrt{N}} \sum_x |x\rang
  2. Realizar la siguiente iteración r (N) veces. Donde la función r (N) se describe más adelante.
    1. Aplicar el operador U_\omega
    2. Aplicar el operador 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:

 \langle s| s\rang =1.
 \lang\omega|s\rang =\lang s|\omega\rang = \frac{1}{\sqrt{N}} .
 U_\omega |s\rang = (I-2| \omega\rangle \langle \omega|)|s\rang=|s\rang-2| \omega\rangle \langle \omega|s\rang=|s\rang-\frac{2}{\sqrt{N}}|\omega\rangle .
U_s(|s\rang-\frac{2}{\sqrt{N}}|\omega\rangle) = (2 \left|s\right\rangle \left\langle s\right| - I)(|s\rang-\frac{2}{\sqrt{N}}|\omega\rangle)
=2 \left|s\right\rangle \left\langle s\right|s\rang-|s\rang-\frac{4}{\sqrt{N}}\left|s\right\rangle \left\langle s\right|\omega\rangle+\frac{2}{\sqrt{N}}|\omega\rangle
=2|s\rang-|s\rang-\frac{4}{\sqrt{N}}\cdot\frac{1}{\sqrt{N}}|s\rang+\frac{2}{\sqrt{N}}|\omega\rangle =\frac{N-4}{N}|s\rang+\frac{2}{\sqrt{N}}|\omega\rangle
=\frac{1}{N\sqrt{N}}\left( (N-4)\sum_{x\neq w} |x\rang+ (3N-4)|\omega\rangle\right)

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

Número de iteraciones[editar]

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

 \lang\omega|s\rang = \frac{1}{\sqrt{N}}

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

 \cos \left(\frac{\pi}{2} - \theta \right) = \frac{1}{\sqrt{N}}
 \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 Us 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 Us y tras cada aplicación de Uω, y se puede comprobar que el operador UsUω 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 probabildad de obtener la respuesta correcta. El número de iteraciones necesarias es dado por r. Para alinear correctamente el vector de estado con |ω>, necesitamos:

\frac{\pi}{2} - \theta = 2 \theta r
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 - cos2θ) = O (sin2θ).

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

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[editar]

A continuación presentamos una implementación concreta del algoritmo de Grover. Supongamos que tenemos una secuencia de 2n 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[editar]

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:

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:

U_f(|x\rangle )= (-1)^{f(x)} |x\rangle

Inversión sobre la media[editar]

Inversión sobre la media.

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

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

con \textstyle \psi=\frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^n-1} |x\rangle .

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

(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 \textstyle \langle a \rangle=(1/2^n)\sum_{x=0}^{2^n-1} a_x

Iteración de Grover[editar]

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:

G_f=(2|\psi\rangle\langle\psi| -I)U_f.

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

Interpretación[editar]

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:

|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:

|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:

|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
=\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
=\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 xi se encuentra el valor buscado, esto es, f (xi)=1 y para el resto, f (x)=0, obtenemos:

|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
=\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 demás los términos. Repitiendo esta operación en varias iteraciones, este efecto se verá incrementado. Si al final del algoritmo hacemos un medición, muy probablemente obtendremos el valor buscado.

Referencias[editar]

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