Transformada cuántica de Fourier
En computación cuántica, la transformada cuántica de Fourier es una transformación sobre bits cuánticos, y es la analogía cuántica de la transformada de Fourier discreta. La transformada de Fourier es una parte de muchos algoritmos cuánticos, el algoritmo de factorización de Shor y el cálculo del logaritmo discreto, el algoritmo de estimación de fase para estimar los eigenvalores de un operador unitario, y logaritmos para HSP (hidden subgroup problem).
La transformada de Fourier puede ser realizada eficientemente en un ordenador cuántico, con una particular descomposición en un producto de matrices unitarias simples. Usando una descomposición simple, la trasformación discreta de Fourier puede ser implementada como un circuito cuántico que tiene solo puertas Hadamard y puertas de desplazamiento de fase controladas, donde es el número de qubits.[1] Esto puede ser comparado con la transformada de Fourier discreta, que utiliza puertas (donde 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.
Los mejores algoritmos cuánticos de transformada de Fourier conocidos actualmente requieren solo puertas para alcanzar una aproximación eficiente.[2]
Definición
La transformada de Fourier cuántica es la transformada de Fourier discreta clásica aplicada al vector de amplitudes de un estado cuántico. 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.
De forma similar, la transformada cuántica de Fourier actúa sobre un estado cuántico 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 está dada por
Propiedades
Unitaria
Muchas de las propiedades de la transformada de Fourier surgen del hecho de que es una transformación unitaria. Esto puede ser comprobado realizando la multiplicación de matrices y verificando la relación , donde es la Hermitica adjunta de . Alternativamente, podemos comprobar que los vectores de norma 1 son transformados a su vez en vectores de norma 1.
De las propiedades unitarias surge que la inversa de la transformada cuántica de Fourier es la hermítica adjunta de la matriz de Fourier, así . Existe un circuito cuántico eficiente que implementa la transformada inversa cuántica de Fourier. Así que ambas transformaciones pueden ser realizadas en un ordenador cuántico.
Implementación del Circuito
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.
![](../I/Qft.png.webp)
Cambio de notación.
Sea el número 123456. Dicho número realmente puede ser descrito por
donde es el número de término que describe dicho número. Cabe destacar que puede tomar valores entre 0 y 9 ya que se están haciendo operaciones módulo 10.
Se puede definir también para fracciones. Por ejemplo, el número puede ser visto como
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 , indica que el qubit está en el estado , con entre 0 y 1 ya que estamos haciendo módulo 2. Por convención, el índice de la base de estados ordena los posibles estados de los qubits lexicográficamente, por ejemplo, por convención el paso de binario a decimal es de la forma.:
Esto también es útil para la notación binaria fraccionaria:
Por tanto, and
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 y , y así en los otros qubits.
Demostración
Se parte de la demostración de transformada discreta de Fourier cuántica dada por
Ahora se especifica la dimensión de nuestro espacio dada por llegando a
.
Aplicando notación binaria sobre de tal forma que . Luego separando, la sumatoria en en sumatorias sobre los distintos valores .
Utilizando propiedades de la exponencial puedo llegar a
Cambiando el productorio por el sumatorio puedo llegar a
Aplicando la sumatoria:
La cuestión ahora es poner en notación binaria como . Realizando un par de términos. Por ejemplo, para :
.
Ahora bien,
donde se ha utilizado que es un número entero ya que es con .
Aplicando el mismo razonamiento para :
Se tiene:
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 2 con el y así llegando a:
En otras palabras, la operación de la transformada de Fourier discreta sobre n-qubits, puede ser factorizada dentro del producto tensor de n qubits-únicos, sugiriendo que es fácil de representar en un circuito cuántico. De hecho, cada una de las operaciones de los qubits-únicos puede ser implementada eficientemente usando una puerta Hadamard y puertas controladas de desplazamiento de fase. 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]
Ejemplo
Considerar la transformada cuántica de Fourier sobre 3 qubits. Es la siguiente transformación:
donde satisface (ya que ).
La matriz que representa esta transformación es
La transformada de Fourier cuántica de 3-qubit es las siguiente operación:
Este circuito cuántico implementa la transformada cuántica de Fourier sobre el estado cuántico .
Las puertas cuánticas usadas en el circuito de arriba son la puerta Hadamard y la puerta controlada de desplazamiento de fase .
Como se calculó antes, el número de puertas usadas es lo cual es igual a 6, para n = 3.[1][2]
Referencias
- Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. OCLC 174527496.
- L. Hales, S. Hallgren, An improved quantum Fourier transform algorithm and applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p. 515, November 12–14, 2000
- Parthasarathy, K. R. (2001-03). «The mathematics of error correcting quantum codes». Resonance 6 (3): 34-45. ISSN 0971-8044. doi:10.1007/bf02837670.
- PRESKILL, JOHN (1998-10). Introduction to Quantum Computation and Information. WORLD SCIENTIFIC. pp. 213–269. ISBN 9789810233990.