La transformada cuántica de Fourier se puede realizar de manera eficiente en una computadora cuántica, con una descomposición particular en un producto de matrices unitarias más simples . Usando una descomposición simple, la transformada discreta de Fourier enLas amplitudes se pueden implementar como un circuito cuántico que consta solo dePuertas de Hadamard y puertas de cambio de fase controladas , dondees el número de qubits. [2] Esto se puede comparar con la clásica transformada discreta de Fourier, que toma puertas (donde es el número de bits), que es exponencialmente más de . Sin embargo, la transformada cuántica de Fourier actúa sobre un estado cuántico, mientras que la transformada clásica de Fourier actúa sobre un vector, por lo que no todas las tareas que utilizan la transformada clásica de Fourier pueden aprovechar esta aceleración exponencial. [ cita requerida ]
Los mejores algoritmos de transformada cuántica de Fourier conocidos (a finales de 2000) solo requieren puertas para lograr una aproximación eficiente. [3]
Definición
La transformada cuántica de Fourier es la clásica transformada discreta de Fourier aplicada al vector de amplitudes de un estado cuántico, donde generalmente consideramos vectores de longitud .
La transformada de Fourier clásica actúa sobre un vector y lo asigna al vector según la fórmula:
De manera similar, la transformada cuántica de Fourier actúa sobre un estado cuántico. y lo mapea a un estado cuántico según la fórmula:
(Las convenciones para el signo del exponente del factor de fase varían; aquí usamos la convención de que la transformada cuántica de Fourier tiene el mismo efecto que la transformada discreta inversa de Fourier, y viceversa).
Desde es una rotación, la transformada cuántica de Fourier inversa actúa de manera similar pero con:
En caso de que es un estado base, la transformada cuántica de Fourier también se puede expresar como el mapa
De manera equivalente, la transformada cuántica de Fourier puede verse como una matriz unitaria (o una puerta cuántica , similar a una puerta lógica booleana para computadoras clásicas) que actúa sobre vectores de estado cuántico, donde la matriz unitaria es dado por
dónde . Obtenemos, por ejemplo, en el caso de y fase la matriz de transformación
Propiedades
Unitaridad
La mayoría de las propiedades de la transformada cuántica de Fourier se derivan del hecho de que es una transformación unitaria . Esto se puede verificar realizando una multiplicación de matrices y asegurándose de que la relación sostiene, donde es el adjunto hermitiano de. Alternativamente, se puede verificar que los vectores ortogonales de la norma 1 se mapeen con los vectores ortogonales de la norma 1.
De la propiedad unitaria se deduce que la inversa de la transformada cuántica de Fourier es el adjunto hermitiano de la matriz de Fourier, por lo tanto . Dado que existe un circuito cuántico eficiente que implementa la transformada cuántica de Fourier, el circuito se puede ejecutar a la inversa para realizar la transformada cuántica de Fourier inversa. Por lo tanto, ambas transformaciones se pueden realizar de manera eficiente en una computadora cuántica.
con el primitivo -ésima raíz de la unidad. El circuito se compone depuertas y la versión controlada de
Todas las operaciones cuánticas deben ser lineales, por lo que basta con describir la función en cada uno de los estados base y dejar que los estados mixtos se definan por linealidad. Esto contrasta con la forma en que generalmente se describen las transformadas de Fourier. Normalmente describimos las transformadas de Fourier en términos de cómo se calculan los componentes de los resultados en una entrada arbitraria. Así es como calcularía la integral de ruta o mostraría que BQP está en PP . Pero es mucho más simple aquí (y en muchos casos) simplemente explicar lo que sucede con un estado de base arbitrario específico, y el resultado total se puede encontrar por linealidad.
La transformada cuántica de Fourier se puede implementar aproximadamente para cualquier N ; sin embargo, la implementación para el caso donde N es una potencia de 2 es mucho más simple. Como ya se dijo, asumimos. Tenemos la base ortonormal que consta de los vectores
Los estados base enumeran todos los estados posibles de los qubits:
donde, con notación de producto tensorial , indica que qubit está en estado , con 0 o 1. Por convención, el índice de estado base ordena los posibles estados de los qubits de forma lexicográfica, es decir, convirtiendo de binario a decimal de esta forma:
También es útil tomar prestada la notación binaria fraccionaria:
Por ejemplo, y
Con esta notación, la acción de la transformada cuántica de Fourier se puede expresar de manera compacta:
o
donde hemos usado:
y
Esto se puede ver reescribiendo la fórmula de la transformada de Fourier en la expansión binaria:
Ahora:
.
Dejar
luego , porque , por , y , Por lo tanto, la se convierte en:
desde para todos .
Entonces podemos escribir:
Para obtener este estado del circuito que se muestra arriba, se deben realizar operaciones de intercambio de los qubits para invertir su orden. A lo sumoSe requieren intercambios, cada uno de los cuales se realiza mediante tres puertas NO controladas (C-NOT) . [2]
Después de la inversión, el n- ésimo qubit de salida estará en un estado de superposición de y , y de manera similar los otros qubits antes de eso (eche un segundo vistazo al boceto del circuito de arriba).
En otras palabras, la transformada discreta de Fourier, una operación en n qubits, se puede factorizar en el producto tensorial de n operaciones de un solo qubit, lo que sugiere que se representa fácilmente como un circuito cuántico (hasta una inversión de orden de la salida). De hecho, cada una de esas operaciones de un solo qubit se puede implementar de manera eficiente utilizando una puerta Hadamard y puertas de fase controladas . El primer término requiere una puerta Hadamard y puertas de fase controladas, la siguiente requiere una puerta Hadamard y puerta de fase controlada, y cada término siguiente requiere una puerta de fase controlada menos. Resumiendo el número de puertas, excluyendo las necesarias para la inversión de salida, se obtiene puertas, que es polinomio cuadrático en el número de qubits.
Ejemplo
Considere la transformada cuántica de Fourier en 3 qubits. Es la siguiente transformación:
Para abreviar, ajuste , la representación matricial de esta transformación en 3 qubits es:
Podría simplificarse aún más usando , y
y luego aún más dado que , y .
La transformada cuántica de Fourier de 3 qubit se puede reescribir como:
o
En caso de que usemos el circuito obtenemos la factorización en orden inverso, es decir
Aquí hemos utilizado notaciones como:
y
En el siguiente croquis, tenemos el circuito respectivo para (con orden incorrecto de qubits de salida con respecto al QFT adecuado):
Como se calculó anteriormente, el número de puertas utilizadas es que es igual a , por .
Relación con la transformada cuántica de Hadamard
Utilizando la transformada de Fourier generalizada en grupos finitos (abelianos) , en realidad hay dos formas naturales de definir una transformada de Fourier cuántica en un registro cuántico de n-qubit . El QFT como se define arriba es equivalente al DFT, que considera estos n qubits como indexados por el grupo cíclico. Sin embargo, también tiene sentido considerar los qubits como indexados por el grupo booleano, y en este caso la transformada de Fourier es la transformada de Hadamard . Esto se logra aplicando una puerta Hadamard a cada uno de los n qubits en paralelo. [4] [5] Tenga en cuenta que el algoritmo de Shor utiliza ambos tipos de transformadas de Fourier, tanto una transformada inicial de Hadamard como una QFT.
Referencias
^ Calderero, D. (1994). "Una transformada de Fourier aproximada útil en factorización cuántica". Informe técnico RC19642, IBM .
^ a bMichael Nielsen e Isaac Chuang (2000). Computación cuántica e información cuántica . Cambridge: Cambridge University Press. ISBN 0-521-63503-9. OCLC 174527496 .
^Hales, L .; Hallgren, S. (12 a 14 de noviembre de 2000). "Un algoritmo y aplicaciones mejorados de la transformada cuántica de Fourier". Actas 41º Simposio anual sobre los fundamentos de la informática : 515–525. CiteSeerX 10.1.1.29.4161 . doi : 10.1109 / SFCS.2000.892139 . ISBN 0-7695-0850-2. S2CID 424297 .
^ Análisis de Fourier de mapas booleanos - Un tutorial -, págs. 12-13
^ Clase 5: Algoritmos cuánticos básicos, Rajat Mittal, págs. 4-5
KR Parthasarathy , Conferencias sobre computación cuántica y códigos de corrección de errores cuánticos (Instituto de Estadística de la India, Centro de Delhi, junio de 2001)
John Preskill , Lecture Notes for Physics 229: Quantum Information and Computation (CIT, septiembre de 1998)
enlaces externos
Proyecto de demostración Wolfram: Circuito cuántico que implementa el algoritmo de búsqueda de Grover
Proyecto de demostración Wolfram: Circuito cuántico que implementa la transformada cuántica de Fourier
Transformada cuántica de Fourier de la vida en línea de Quirk