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

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 cor-chete 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$ .

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:

Inicializar el sistema al estado

$|s\rang = \frac{1}{\sqrt{N}} \sum_x |x\rang$
Realizar la siguiente iteración r (N) veces. Donde la función r (N) se describe más adelante.
1. Aplicar el operador $U ω$
2. Aplicar el operador $U_s = 2 \left|s\right\rangle \left\langle s\right| - I$ .
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 ω$ y $U s$ ), la amplitud del elemento buscado se ve incrementado. Y esta es una iteración de Grover.

Número de iteraciones

$\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}}$

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 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 - cos²θ) = O (sin²θ).

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

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:

$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

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

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

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

Aplicación del oráculo
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

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 x_i se encuentra el valor buscado, esto es, f (x_i)=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

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

Categoría:

Algoritmos cuánticos

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

Algoritmo cuántico — Transformada de Fourier cuántica sobre tres qubits, basada en la aplicación reiterada de la puerta cuántica de Hadamard y de puertas de cambio de fase. Un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación… … Wikipedia Español
Computación cuántica — La esfera de Bloch es una representación de un qubit, el bloque de construcción fundamental de los computadores cuánticos. La computación cuántica es un paradigma de computación distinto al de la computación clásica. Se basa en el uso de qubits… … Wikipedia Español
Check Wikipedia — Wikiproyecto:Check Wikipedia Saltar a navegación, búsqueda Esta página contiene de forma consciente fallos ortográficos. Los bots no deben intentar corregirlos. Atajo PR:CWPR:CW … Wikipedia Español
Crowdsourcing — Este artículo o sección necesita una revisión de ortografía y gramática. Puedes colaborar editándolo (lee aquí sugerencias para mejorar tu ortografía). Cuando se haya corregido, borra este aviso por favor. Crowdsourcing , del inglés crowd (masa)… … Wikipedia Español

Los diccionarios y las enciclopedias sobre el Académico

Algoritmo de Grover

Contenido

Aplicaciones