Este algoritmo fue propuesto por Daniel Simon en 1994. Se trata de encontrar el periodo de una función vectorial booleana del tipo:
El periodo por tanto será un vector booleano T que cumpla:
Se puede probar que de nuevo clásicamente habría que evaluar f sobre la mitad más uno de los elementos del dominio (2n-1+1), es decir, el coste sería exponencial. Incluso con un algoritmo probabilista no podríamos ir más acá de las 2n/2 consultas. Veremos que en este caso la ganancia cuántica es clara ya que bastará evaluar Uf unas pocas veces, del orden de n, para encontrar el periodo con una buena cota de aproximación.
Ahora los dos registros del estado inicial tienen n qubits:
Aplicando los operadores de Hadamard al primer registro obtenemos:
Si hacemos actuar ahora la función obtenemos, dado que todos los bits del registro están a cero:
Ahora añadimos un paso que no es necesario pero sí es muy útil desde el punto de vista pedagógico. Se trata de medir el segundo registro y obtener uno de los posibles valores de la función, digamos f(x0), quedando el estado colapsado a:
en donde por supuesto suponemos el estado más general combinación de x0 y x0+T, dado que sólo conocemos el valor de la función. Si ahora aplicamos Hadamard sobre los primeros qubits se obtiene:
en donde lógicamente ahí sólo sobrevivirán los términos que cumplen que T· y=0, ya que el resto interferirá destructivamente. Si ahora medimos el primer registro:
obtendremos para cada estado yi una probabilidad:
Repitiendo estos pasos del orden de n veces obtenemos n vectores yi que nos darán un sistema lineal homogéneo de ecuaciones cuya solución no trivial nos dará las componentes de T:
que podemos resolver con un algoritmo clásico obteniendo T con un orden O(n) de repeticiones. Como se ha dicho, este algoritmo es exponencialmente más eficiente que cualquier algoritmo clásico, incluso de tipo aleatorio.
Hemos visto en los algoritmos estudiados que una de las armas más potentes en computación cuántica es la puerta de Hadamard. En realidad esta puerta es un caso especial de la llamada transformada cuántica de Fourier (QFT):
Por tanto, sobre los vectores de la base se aplica la transformación unitaria NxN:
La QFT es por tanto una transformada de Fourier discreta (DFT). En principio harían falta del orden de O(N2) operaciones para realizarla, pero en el caso de N=2n, el orden O(22n) se puede reducir mediante la llamada transformada rápida de Fourier (FFT) a un orden de O(NlogN)=O(n2n). Aún así, sigue siendo un orden exponencial que veremos que el algoritmo cuántico mejora a cuadrático.
En este caso binario sustituiremos en la última expresión la expansión binaria:
obteniendo
y utlizando que la exponencial de una suma es el producto de las exponenciales resulta:
En consecuencia se puede ver que la QFT transforma la base computacional en otra base con vectores factorizables, es decir, sin entrelazamiento.
Ahora, teniendo en cuenta la representación de las fracciones binarias:
y despreciando la parte entera que en la exponencial sólo formará unidades, se tiene:
o de forma más compacta
Nótese que como comentamos la puerta de Hadamard no deja de ser una transformada de Fourier actuando sobre un solo qubit:
Vamos a ver un circuito que implementa esta transformación. Sea el caso n=3 con el estado de entrada:
En donde definimos las rotaciones condicionales como:
La primera puerta de Hadamard actúa sobre el bit más significativo, generando el estado:
Las siguientes puertas de rotación controlada agregan las fases π/2 y π/4 a |x2> si los bits correspondientes están encendidos, esto es:
De la misma forma se aplica Hadamard y su rotación controlada al segundo bit:
y por último la puerta de Hadamard al último bit:
Vemos que para n=3 se han necesitado 3 puertas de Hadamard y 3 puertas de rotación condicionada. Para el caso general se necesitan:
Por tanto, el orden de cálculo de esta transformación cuántica es O(n2)=O((logN)2), lo que denota una ganancia exponencial frente al mejor algoritmo clásico, que como comentamos era del orden O(n2n).
Por claridad no hemos incluido las puertas SWAP que se necesitan (del orden de n/2) para obtener el orden correcto al final para nuestra transformada de Fourier tal como la definimos al principio. Un circuito general para n qubits sería de la forma:
No hay comentarios:
Publicar un comentario