Algoritmo de Grover

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

${\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.

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.

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.

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.

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

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.

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.