Algoritmo de Grover
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.
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 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.
Denotaremos los autoestados utilizando la notación bra-ket en la forma: y los autovalores correspondientes como Ahora tomamos un operador unario, Uω, que actúa como una subrutina que compara las diferentes entradas de acuerdo al criterio de búsqueda.
Entonces |ω> es uno de los vectores base, y tenemos En términos geométricos, hay un ángulo (π/2 - θ) entre |ω> y |s>, donde θ dado por: 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 número de iteraciones necesarias es dado por r. Para alinear correctamente el vector de estado con |ω>, necesitamos: 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, para N>>1, θ ≈ N-1/2, tenemos Además, la probabilidad de obtener una respuesta incorrecta será O(1/N), que tiende a 0 para un valor de N suficientemente elevado.
A continuación presentamos una implementación concreta del algoritmo de Grover.
La operación de este bloque es: Puesto que el último estado no se modifica, vamos a ignorarlo y escribiremos: El bloque que lo realiza se muestra en la figura de la derecha.
Esta operación se interpreta como inversión sobre la media, pues si lo aplicamos sobre un estado genérico
Preparamos un estado haciendo pasar el qubit |0> (realmente compuesto de n ceros) a través de una puerta de Hadamard: Este estado pasa a través del oráculo, obteniendo: A continuación, aplicamos la inversión sobre la media, y obtenemos: 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: 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.
