Transformada cuántica de Fourier
Usando una descomposición simple, la trasformación discreta de Fourier puede ser implementada como un circuito cuántico que tiene solo
[1] Esto puede ser comparado con la transformada de Fourier discreta, que utiliza
es el número de bits), lo cual es exponencialmente mayor que
Sin embargo, la transformada cuántica de Fourier actúa sobre un estado cuántico, mientras que la trasformada de Fourier clásica actúa sobre un vector, así que no todas las tareas que usan la transformada de Fourier clásica pueden utilizar la ventaja de esta aceleración exponencial.
puertas para alcanzar una aproximación eficiente.
La transformada de Fourier clásica (unitaria) actúa sobre un vector en
, (x0,..., xN−1) y lo mapea al vector (y0,..., yN−1) de acuerdo con la fórmula:Donde
es una raíz de la unidad Nth primitiva.
y lo mapea a un estado cuántico
de acuerdo con la fórmula: Esto puede ser expresado como la aplicación De forma equivalente, la transformada de Fourier cuántica puede ser vista como una matriz unitaria actuando sobre vectores estado cuántico, donde la matriz unitaria
Esto puede ser comprobado realizando la multiplicación de matrices y verificando la relación
Alternativamente, podemos comprobar que los vectores de norma 1 son transformados a su vez en vectores de norma 1.
Así que ambas transformaciones pueden ser realizadas en un ordenador cuántico.
La transformada de Fourier puede ser implementada aproximadamente para cualquier N, sin embargo, la implementación para el caso en el que N es una potencia de 2 es mucho más simple.Cambio de notación.
puede tomar valores entre 0 y 9 ya que se están haciendo operaciones módulo 10.Se puede definir también para fracciones.
Es posible definir el mismo tipo de notación en binario.
Este tipo de notación es conocida como notación binaria o representación binaria Supongamos N = 2n.
Tenemos la base ortogonal consistente en los vectores La base de todos los posibles estados de los qubits es: donde, con la notación producto tensorial
entre 0 y 1 ya que estamos haciendo módulo 2.
La transformada cuántica de Fourier se puede escribir como el producto tensorial de una serie de términos, conocido como tensotorio: Esto también es útil para la notación binaria fraccionaria: Por tanto,
Con esta notación, la acción de la transformada de Fourier cuántica puede ser expresada por: donde la salida del qubit 1 es una superposición del estado
Ahora se especifica la dimensión de nuestro espacio dada por
Utilizando propiedades de la exponencial puedo llegar a
y se llega a que
Si se aplica en general se puede llegar al resultado donde falta por introducir puertas lógicas swap que cambien el qubit 1 con el
El primer término requiere una puerta Hadamard, el siguiente requiere una puerta Hadamard y una puerta controlada de desplazamiento de fase y cada siguiente término requiere una puerta adicional de desplazamiento de fase.
Sumando el número de puertas da
puertas, el cual es proporcional al número de qubits.
[1][3][4] Considerar la transformada cuántica de Fourier sobre 3 qubits.
Como se calculó antes, el número de puertas usadas es
