Un algoritmo de búsqueda es el que nos permite encontrar un elemento x0 en un conjunto posible de soluciones (estructura de datos) que cumpla una determinada proposición f(x). Dentro de este tipo de problemas están la búsqueda en una base de datos o el coloreado ordenado de una gráfica.
Si no sabemos nada sobre la estructura del espacio de soluciones estamos ante un problema desestructurado, como el que resolvió Lov K. Grover en 1996. Un ejemplo sería la búsqueda de un teléfono en una guía telefónica sin conocer el nombre. Clásicamente el mejor algoritmo aleatorio nos llevaría a un coste de O(N) (si se quiere N/2 consultas de media) para una base de datos de tamaño N. Con el algoritmo de Grover se mejora este resultado con una ganancia cuadrática de orden O(√N). El algoritmo de Grover es probabilístico, es decir, sólo da la respuesta correcta con cierta probabilidad (al contrario que el de Deutsch por ejemplo que era determinista).
Lógicamente nuestra proposición aquí está implementada por un oráculo que actúe de la siguiente forma:
Por tanto, asumimos que de entrada necesitaremos un registro fuente de n qubits tal que N=2n y uno adicional para almacenar la información de la función. (Nótese el hecho de que conocer de antemano x0 no es lo mismo que reconocerlo entre un conjunto de estados).
La estrategia será preparar un estado superposición de todas las entradas del catálogo:
después aplicar el oráculo que nos dé todos los valores de la veracidad de la proposición sobre las entradas:
para en último lugar desbalancear los pesos estadísticos de forma que halla suficiente probabilidad de encontrar el estado |x0>|1>. Para ello hay que utlizar las operaciones de cambio de signo e inversión sobre el promedio.
Se trata de aplicar un cambio de signo al elemento que cumpla la proposición, de forma que quede de algún modo marcado (figura).
En el algoritmo clásico esto ya supondría, lógicamente, el haberlo encontrado, pero recordemos que aquí el elemento sigue dentro de un estado global que todavía no podremos medir por no tener la suficiente certeza de que el resultado nos va a dar nuestro elemento. El operador a implementar será de la forma:
La forma de implementar este algoritmo es preparando un estado destino, tal como hicimos para el de Deutsch-Jozsa (inicializandolo a |1> y aplicando Hadamard), en |0> - |1>. De este modo el oráculo de la función nos dará un cambio de signo cuando ésta sea 1.
es decir, al no alterarse el segundo registro lo que se tiene es que:
De esta forma el oráculo marca la solución del problema, mediante el operador cambio de signo:
Para N=4 por ejemplo este operador oráculo se puede implementar mediante las siguientes puertas de tipo Toffoli, dependiendo de si el x0=0,1,2,3:
Se trata de un algoritmo que superpone sobre la media la diferencia respecto de ésta. De este modo el valor negativo recientemente invertido aparecerá por encima de todos los demás (figura). Para ello hay que usar el llamado por Grover operador de difusión:
El efecto de este operador es equivalente a realizar una reflexión respecto del estado:
es decir
lo que se deduce simplemente aplicando la definición del operador Walsh-Hadamard respecto al estado fundamental y calculando después los elementos de matriz respecto de la base computacional.
Lo más interesante de este operador es estudiar lo que hace con las componentes de cualquier entrada que se le ponga, del tipo general:
cuya acción es
es decir, se produce un cambio de las amplitudes en la forma
Vamos a ver el ejemplo de la actuación del cambio de signo y esta inversión para el caso N=4 (que puede ser implementado con dos qubits). En el registro entrante las amplitudes de todos los estados son las mismas:
si se aplica un cambio de signo (sea x0=2=(10)):
y por último aplicamos el operador de difusión, con lo que las amplitudes cambian a:
Lo que indica que en una sola iteración ya tenemos la certeza absoluta de encontrar el elemento, frente a una media de 2 en el caso clásico. En la figura anterior se ven las primeras iteraciones en este caso (y lo perjudicial que puede ser calcular de más). En general podemos decir que el aumento que se produce en la inversión temporal es aproximadamente:
lo que sería una forma heurística de ver que en efecto el método de Grover es de orden O(√N), dado que con ese orden de iteraciones llegaríamos a la unidad. En realidad esto no es así dado que las sucesivas iteraciones no tienen el mismo comportamiento, por eso va a ser tan importante calcular el número de iteraciones suficiente para una cierta probabilidad.
Para implementar este algoritmo basta con saber cómo se implementa la inversión respecto del eje |0> dada por -U0. Para ello se usa el hecho de que:
A partir de esto podemos construir, con ayuda de puertas CNOT o Toffoli controladas, el operador que actúa reflejando el último vector de la base |111···1>. Si nos ayudamos también de puertas X podemos dar la vuelta al estado de forma que lo que gire sea el primero. Por ejemplo, para dos qubits tendríamos:
y el circuito correspondiente a U0 sería:
como para implementar una puerta de Toffoli de n bits se necesitan 2n-5 puertas ternarias de Toffoli, será ese el orden de cálculo de este algoritmo, es decir O(n)=O(log N).
Partimos de un estado entrante de la forma:
y al pasar por las puertas de Hadamard se tiene:
Como a partir de aquí el segundo registro no se va a modificar, es útil trabajar sólo con el primero y empezar con el estado:
y estudiar su evolución bajo las iteraciones del operador de Grover:
y de esta forma también podemos simplificar su representación gráfica:
donde
Por tanto la primera reflexión respecto a |x0> nos dará en el primer registro el resultado:
y la inversión sobre el promedio nos da:
en donde se ve claramente que para N=4 con una sola iteración ya se puede medir. Si continuamos el siguiente paso nos daría:
La expresión general es difícil de compactar con fracciones polinómicas (seguramente habría que hacer uso de las funciones de Chebyshev), pero tiene una expresión trigonométrica particularmente sencilla:
El estado |ψ1 se puede separar mediante una base reducida en dos estados ortonormales:
De forma que Ux0 es una simetría respecto a |x⊥> y D es una simetría respecto a |ψ1> que en este caso tiene la forma:
Por geometría básica se sabe que la composición de dos reflexiones de ejes secantes es un giro de ángulo doble al que forman los ejes. Sea ese ángulo de giro θ, luego el que forman los ejes será la mitad y
luego
Si llamamos γ=θ/2 el estado inicial es
y la aplicación del algoritmo supone un giro de θ=2γ en ese plano, es decir
por lo que después de k interacciones tendremos
Es obvio que para rotar completamente el estado |ψi> a |x0> se debe cumplir:
Expresión que no es entera, y por tanto habrá que aproximar, y aquí es cuando sale la dependencia del algoritmo en cuanto al orden O(N).
Vamos a calcular la probabilidad de fallo, definida como
usando el siguiente hecho
por tanto
Y por esto la probabilidad de fallo después de π√N/4 iteraciones es 1/N. Normalmente además la probabilidad de encontrar el elemento es mayor que esta cota, como se aprecia en la figura anterior para 64 elementos, en donde aunque esta probabilidad es de 0.016, en realidad en la iteración recomendada tenemos una amplitud de 0.998, con lo que el margen de error probabilístico es de 0.004.
Para introducir la dependencia con el número de soluciones hay que definir los conjuntos:
de forma que, si s es el número de soluciones
y por tanto
Y de nuevo tendremos la misma interpretación trigonométrica:
solo que ahora el ángulo se define como
Así que por la misma razón ahora el orden de iteraciones va con O(√N/s):
con una probabilidad de error de s/N.
Casos particulares interesantes son:
s=1. Ya hemos visto que si N es grande:
s=N/4. En este caso sen(γ)=1/2 y
es decir, con una sola iteración se consigue la solución.
s=N/2. Entonces sen(γ)=1/√2 luego γ=π/4 y
pero en este caso la aplicación del algoritmo no mejora la probabilidad de acierto clásica, que sigue siendo s/N=1/2:
s>N/2. A partir de aquí, el número de iteraciones se va haciendo más grande y no se gana respecto al caso clásico, ya que el ángulo de giro cumple:
expresión que alcanza su valor máximo en s=N/2, con lo que después desciende y por tanto el número de iteraciones será mayor.
De todo esto se deduce que si a priori no se conoce el número de soluciones el algoritmo no es útil. En efecto, si por ejemplo N=220, ya hemos visto que una probabilidad de fallo menor que 2-20 nos la darían, para una solución
pero si mantenemos este número de iteraciones y resulta que existen s=4 soluciones el error que se comete es muy grande, ya que en este caso deberíamos haber empleado 402 iteraciones, encontrando para el valor 804:
cuando teníamos que haber parado en el 402:
No obstante, hay formas de usar el algoritmo de Grover más cuidadosamente cuando uno tiene pistas sobre el número de soluciones (Boyer, Brassard, Hoyer, Tapp, 1996), e incluso un algoritmo de conteo de soluciones mediante la transformada de Fourier (Brassard, Hoyer, Tapp, 1998).
Para hallar la relación de recurrencia escribimos el estado en la forma:
en donde la semilla es
Como en cada iteracción las amplitudes cambian de signo y se produce la inversión en el promedio, las relaciones recursivas son
En forma matricial
Por inducción se puede demostrar que la solución de este sistema es precisamente el resultado obtenido geométricamente:
Un artículo de los profesores Galindo y Martín-Delgado de la Universidad Complutense aparecido en Physical Review en el 2000, titulado "Family of Grover's quantum-searching algorithm" abrió varias vías de investigación sobre los algoritmos de tipo Grover.
La más evidente es la posible generalización aprovechando el hecho de que (véase la transformada cuántica de Fourier)
por tanto la inversión sobre la media toma la misma forma matricial en la base de momentos que el cambio de signo en la de coordenadas. Si definimos
en la base transformada toma la forma:
Esto, aparte de abrir el estudio hamiltoniano del sistema que ya se había dado (Farhi, Gutmann, 1998), nos puede inducir a descubrir qué pasaría si se utiliza un proyector sobre otro estado de "momento". Los estudios hechos muestran que el caso concreto encierra toda la esencia del algoritmo, parece que no aportando la generalización nuevos hechos.
En cualquier caso, el artículo aludido se centra en la generalización de los operadores de Grover a operadores de la forma:
definiendo la iteración de Grover como la composición de dos de estas superposiciones de proyectores ortogonales, con el llamado kernel de Grover:
donde
con
La elección particular de Grover lógicamente es
en general podemos poner
que en forma matricial en la base reducida ya estudiada
toma la forma
Pero lógicamente en el kernel cada operador de Grover tendrá una libertad de fase con la que podemos reducir a dos el número de grados de libertad, fijando por conveniencia:
con lo que un cálculo fácil nos da la expresión para el kernel en la base reducida:
La estrategia de generalización se basa en recoger la expresión para la amplitud de probabilidad después de m iteraciones del kernel:
entonces, si somos capaces de diagonalizar K en términos de sus autovectores {|k1>,|k2>} y autovalores { eiω1,eiω2} la expresión quedaría más manejable y podríamos sacar conclusiones.
El caso s=1 estudiado en el artículo nos daría un desarrollo:
un estudio para N⟶∞ de estos autovectores nos da
pero el primer sumando de la primera componente nos daría una probabilidad no convergente, con lo que necesariamente
y de este modo se obtiene
que alcanza su valor máximo en
y teniendo en cuenta que la expresión de los autovalores da un comportamiento asintótico cuando N⟶∞ de
si parametrizamos el parámetro de Grover como δ= eiΦ se tiene la expresión
obteniendo por fin una expresión generalizada para la eficacia de los algoritmos tipo Grover. Lógicamente para Φ=0 recuperamos el principal. Además en el artículo mencionado se hace un estudio de las perturbaciones sobre las condiciones iniciales viendo su estabilidad.
No hay comentarios:
Publicar un comentario