¿Qué describen los resultados de una transformada cuántica de Fourier?

Question

La transformada discreta de Fourier clásica toma una secuencia de valores y da como resultado otra secuencia de valores que describen un conjunto de coeficientes de sinusoides complejas que pueden utilizarse para reconstruir (o aproximar) la entrada original.

En cambio, ¿qué hace exactamente una transformada cuántica de Fourier? ¿Y por qué se dice que es el "análogo" de la transformada discreta de Fourier?

Más concretamente, dado que todos los qubits de entrada están en superposición unos con otros, ¿sigue existiendo la noción de secuencia ordenada que existe en la DFT (ya que el orden de las entradas de la DFT afecta claramente a la salida)?

¿Y cómo se interpreta el resultado de la QFT? Digamos que la salida de una QFT es una superposición de $a |00\rangle +b|01\rangle + c|10\rangle + d|11\rangle$ ¿Qué me dice esto sobre la superposición original?

Answer 1

La transformada cuántica de Fourier aplica una transformada discreta de Fourier a las amplitudes en una superposición. Esto es, si su entrada es $$ \sum a_n |n\rangle\ , $$ entonces la salida es $$ \sum \hat a_n |n\rangle\ , $$ donde el vector $(\hat a_n)$ es la transformada discreta de Fourier del vector $(a_n)$ .

La cuestión es que si $|n\rangle$ se codifica en binario (es decir, en un $N$ -registro de qubits, con $n=2^N$ ), esto puede llevarse a cabo de forma muy eficiente, concretamente en el tiempo $O(N^2) = O((\log n)^2$ ), que es exponencialmente más rápido que el clásico (donde $O(n\log n)$ se requieren operaciones).