La Transformada Cuántica de Fourier funciona igual que la Transformada Clásica de Fourier, sin embargo, tiene aplicaciones muy profundas y elegantes en algoritmos cuánticos exponencialmente rápidos sin contrapartes clásicas que nos llevan a creer en la potencial superioridad de las computadoras cuánticas.
Más:
La transformada de Fourier clásica mapea el vector [matemática] x [/ matemática] de números complejos [matemática] x_ {1}, x_ {2}, x_ {n} [/ matemática]
en el vector [matemática] y [/ matemática] de números complejos [matemática] y_ {1}, y_ {2}, y_ {n} [/ matemática] a través de la receta
[matemáticas] y_ {k} = \ frac {1} {\ sqrt {N}} \ sum_ {j = 0} ^ {N-1} x_ {j}
e ^ {\ frac {2 \ pi jk} {N}} [/ matemáticas]
- ¿Qué algoritmos existen para la reconstrucción de un conjunto de vectores de un diccionario de cardinalidad más pequeña?
- Como saber entiendo totalmente un algoritmo
- ¿Por qué la complejidad del algoritmo O (logN) significa que los datos disminuyen a la mitad?
- ¿Vale la pena iniciar una compresión de datos sin pérdidas?
- Los electrones son extraños. ¿Cómo conocen el camino más corto al suelo? ¿No tendrían que 'mirar' hacia adelante?
La transformación cuántica de Fourier hace más o menos lo mismo. Sin embargo, actúa sobre estados cuánticos: versiones cuánticas de los vectores que vimos en el caso clásico.
Por lo tanto, un vector de base cuántica [math] | j> [/ math] se mapea en
[matemáticas] \ frac {1} {\ sqrt {N}} \ sum_ {j = 0} ^ {N-1}
e ^ {\ frac {2 \ pi jk} {N}} | k \ rangle [/ math]
Usando esto podemos ver que el estado arbitrario
[math] \ sum_ {j = 0} ^ {N-1} x_ {j} | j \ rangle [/ math] se asigna a [math] \ sum_ {k = 0} ^ {N-1} y_k | k \ rangle [/ matemáticas]
Dónde
[matemáticas] y_ {k} = \ frac {1} {\ sqrt {N}} \ sum_ {j = 0} ^ {N-1} x_ {j}
e ^ {\ frac {2 \ pi jk} {N}} [/ math] (es decir, los estados arbitrarios están relacionados por una transformada de Fourier)
La Transformada Cuántica de Fourier se puede escribir explícitamente como el operador:
[matemáticas] F = \ frac {1} {\ sqrt {N}} \ sum_ {j, k} ^ {N-1} e ^ {\ frac {2 \ pi jk} {N}}
| k \ rangle \ langle j | [/ math]
Propiedades y aplicaciones
La transformación cuántica de Fourier se puede implementar físicamente
Una cosa clave a tener en cuenta aquí es que la Transformada Cuántica de Fourier es unitaria y, por lo tanto, puede implementarse a través de procesos físicos coherentes, es decir, qubits en una computadora cuántica [1].
Al alinear los qubits en el circuito cuántico apropiado (tal como se podría alinear las puertas lógicas clásicas) se puede calcular la Transformación Cuántica de Fourier.
La transformación cuántica de Fourier se implementa de manera más eficiente en una computadora cuántica
Una diferencia importante entre las transformadas de Fourier cuántica y clásica es que solo necesitamos puertas [matemáticas] O (n ^ 2) [/ matemáticas] para implementar la transformación cuántica de Fourier mientras que la secuencia equivalente de [matemáticas] 2 ^ n [/ matemáticas] Las amplitudes clásicas requieren compuertas [matemáticas] O (n2 ^ n) [/ matemáticas]. Esta es una ganancia exponencial en eficiencia.
Sin embargo, la Computadora Quantum es solo más eficiente en el cálculo de las Transformaciones Cuánticas de Fourier y no las Transformaciones Clásicas de Fourier. Por lo tanto, la Transformación Cuántica de Fourier no necesariamente proporciona aceleraciones directas para problemas clásicos que requieren una Transformada de Fourier.
La transformación cuántica de Fourier está en el corazón de los algoritmos cuánticos que resuelven problemas que las computadoras clásicas no pueden resolver.
Aunque la ganancia exponencial no se puede usar directamente para obtener aceleraciones en problemas clásicos, la eficiencia de calcular la Transformación Cuántica de Fourier en una Computadora Cuántica se puede aprovechar de manera más sutil.
En particular, se puede demostrar que el problema de encontrar [matemáticas] r [/ matemáticas]: el menor entero tal que [matemáticas] x ^ {r} = 1 (mod N) con 0 <x <N [/ matemáticas] donde [matemáticas] x [/ matemáticas] y [matemáticas] N [/ matemáticas] no tienen factores comunes. es equivalente al problema de factorización prima.
Armado con la Transformación Cuántica de Fourier y la equivalencia de encontrar y ordenar factores, uno puede encontrar un algoritmo [matemático] O (n ^ 2 \ log n \ log \ log n) [/ matemático] para factorizar un número entero (bueno, al menos Peter Shor Can :)). Esto es exponencialmente más rápido que el algoritmo clásico más conocido: el tamiz de campo numérico que se ejecuta en [matemáticas] O (\ exp (cn ^ {1/3} (\ log n) ^ {2/3})) [/ matemáticas] tiempo [2].
Es bien sabido que este hecho de que los algoritmos cuánticos pueden encontrar factores primos de manera eficiente representa una amenaza para la criptografía RSA estándar.
Nuevamente: matemáticamente, la Transformación Cuántica de Fourier funciona de manera muy similar a la transformada clásica de Fourier, sin embargo, tiene implicaciones y aplicaciones de largo alcance en la búsqueda de algoritmos cuánticos eficientes que no tienen contrapartes clásicas eficientes.
[1] “La transformación es unitaria” significa que cuando transforma un vector cuántico de Fourier no cambia la magnitud del vector
[2] En esta sección (a diferencia de la primera sección que trata solo con la transformada de Fourier) “n” se refiere a la longitud de bits del número que estamos factorizando.
