Transformada cuántica de Fourier

^[1]

Cambio de base aplicado en la computación cuántica

En computación cuántica , la transformada cuántica de Fourier (QFT) es una transformación lineal en bits cuánticos y es el análogo cuántico de la transformada discreta de Fourier . La transformada cuántica de Fourier es parte de muchos algoritmos cuánticos , en particular el algoritmo de Shor para factorizar y calcular el logaritmo discreto , el algoritmo de estimación de fase cuántica para estimar los valores propios de un operador unitario y algoritmos para el problema de subgrupos ocultos . La transformada cuántica de Fourier fue descubierta por Don Coppersmith . ^[2]

La transformada cuántica de Fourier se puede realizar eficientemente en una computadora cuántica con una descomposición en el producto de matrices unitarias más simples . La transformada discreta de Fourier sobre amplitudes se puede implementar como un circuito cuántico que consta únicamente de puertas de Hadamard y puertas de cambio de fase controlado , donde es el número de qubits. ^[3] Esto se puede comparar con la transformada de Fourier discreta clásica, que toma puertas (donde está el número de bits), que es exponencialmente mayor que . ${\displaystyle 2^{n}}$ ${\displaystyle O(n^{2})}$ ${\displaystyle n}$ ${\displaystyle O(n2^{n})}$ ${\displaystyle n}$ ${\displaystyle O(n^{2})}$

La transformada cuántica de Fourier actúa sobre un vector de estado cuántico (un registro cuántico ) y la transformada discreta de Fourier clásica actúa sobre un vector. Ambos tipos de vectores se pueden escribir como listas de números complejos. En el caso cuántico, es una secuencia de amplitudes de probabilidad para todos los resultados posibles tras la medición (los resultados son los estados básicos o estados propios ). Debido a que la medición colapsa el estado cuántico a un estado de base única, no todas las tareas que utilizan la transformada de Fourier clásica pueden aprovechar la aceleración exponencial de la transformada cuántica de Fourier.

Los mejores algoritmos de transformada cuántica de Fourier conocidos (hasta finales de 2000) requieren sólo puertas para lograr una aproximación eficiente, siempre que se implemente una puerta de fase controlada como operación nativa. ^[4] ${\displaystyle O(n\log n)}$

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, que suele tener longitud . ${\displaystyle N=2^{n}}$

La transformada de Fourier clásica actúa sobre un vector y lo asigna al vector según la fórmula: ${\displaystyle (x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}}$ ${\displaystyle (y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}}$

${\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}\omega _{N}^{-nk},\quad k=0,1,2,\ldots ,N-1,}$

donde y es una raíz enésima de la unidad . ${\displaystyle \omega _{N}=e^{\frac {2\pi i}{N}}}$ ${\displaystyle \omega _{N}^{n}}$

De manera similar, la transformada cuántica de Fourier actúa sobre un estado cuántico y lo asigna a un estado cuántico según la fórmula: ${\textstyle |x\rangle =\sum _{i=0}^{N-1}x_{i}|i\rangle }$ ${\textstyle \sum _{i=0}^{N-1}y_{i}|i\rangle }$

${\displaystyle y_{k}={\frac {1}{\sqrt {N}}}\sum _{n=0}^{N-1}x_{n}\omega _{N}^{nk},\quad k=0,1,2,\ldots ,N-1,}$

(Las convenciones para el signo del exponente del factor de fase varían; aquí la transformada cuántica de Fourier tiene el mismo efecto que la transformada discreta inversa de Fourier, y viceversa).

Como es una rotación, la transformada cuántica inversa de Fourier actúa de manera similar pero con: ${\displaystyle \omega _{N}^{n}}$

${\displaystyle x_{n}={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}y_{k}\omega _{N}^{-nk},\quad n=0,1,2,\ldots ,N-1,}$

En caso de que sea un estado base, la transformada cuántica de Fourier también se puede expresar como el mapa ${\displaystyle |x\rangle }$

${\displaystyle {\text{QFT}}:|x\rangle \mapsto {\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}\omega _{N}^{xk}|k\rangle .}$

De manera equivalente, la transformada cuántica de Fourier puede verse como una matriz unitaria (o puerta cuántica ) que actúa sobre vectores de estado cuánticos, donde la matriz unitaria es la matriz DFT. ${\displaystyle F_{N}}$

${\displaystyle F_{N}={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\omega ^{3}&\cdots &\omega ^{N-1}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\cdots &\omega ^{2(N-1)}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\cdots &\omega ^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &&\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\end{bmatrix}}}$

dónde . Por ejemplo, en el caso de y fase la matriz de transformación es ${\displaystyle \omega =\omega _{N}}$ ${\displaystyle N=4=2^{2}}$ ${\displaystyle \omega =i}$

${\displaystyle F_{4}={\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&i&-1&-i\\1&-1&1&-1\\1&-i&-1&i\end{bmatrix}}}$

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 comprobar realizando una multiplicación de matrices y asegurándose de que se mantenga la relación, donde está el adjunto hermitiano de . Alternativamente, se puede comprobar que los vectores ortogonales de la norma 1 se asignan a vectores ortogonales de la norma 1. ${\displaystyle FF^{\dagger }=F^{\dagger }F=I}$ ${\displaystyle F^{\dagger }}$ ${\displaystyle F}$

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 tanto, ambas transformaciones se pueden realizar de manera eficiente en una computadora cuántica. ${\displaystyle F^{-1}=F^{\dagger }}$

Implementación del circuito

Las puertas cuánticas utilizadas en el circuito de los qubits son la puerta de Hadamard y la puerta de fase : ${\displaystyle n}$ ${\displaystyle R_{k}}$

${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\qquad {\text{and}}\qquad R_{k}={\begin{pmatrix}1&0\\0&e^{i2\pi /2^{k}}\end{pmatrix}}}$

El circuito se compone de puertas y la versión controlada de : ${\displaystyle H}$ ${\displaystyle R_{k}}$

Una base ortonormal consta de los estados de la base.

${\displaystyle |0\rangle ,\ldots ,|2^{n}-1\rangle .}$

Estos estados básicos abarcan todos los estados posibles de los qubits:

${\displaystyle |x\rangle =|x_{1}x_{2}\ldots x_{n}\rangle =|x_{1}\rangle \otimes |x_{2}\rangle \otimes \cdots \otimes |x_{n}\rangle }$

donde, con notación de producto tensorial , indica que el qubit está en estado , con 0 o 1. Por convención, el índice de estado base es el número binario codificado por , con el bit más significativo. ${\displaystyle \otimes }$ ${\displaystyle |x_{j}\rangle }$ ${\displaystyle j}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{j}}$ ${\displaystyle x}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{1}}$

La acción de la puerta Hadamard es de donde depende la señal . ${\displaystyle H|x_{i}\rangle =\left({\frac {1}{\sqrt {2}}}\right)\left(|0\rangle +e^{2\pi ix_{i}2^{-1}}|1\rangle \right)}$ ${\displaystyle x_{i}}$

La transformada cuántica de Fourier se puede escribir como el producto tensorial de una serie de términos:

${\displaystyle {\text{QFT}}(|x\rangle )={\frac {1}{\sqrt {N}}}\bigotimes _{j=1}^{n}\left(|0\rangle +\omega _{N}^{x2^{n-j}}|1\rangle \right).}$

Usando la notación binaria fraccionaria

${\displaystyle [0.x_{1}\ldots x_{m}]=\sum _{k=1}^{m}x_{k}2^{-k}.}$

La acción de la transformada cuántica de Fourier se puede expresar de forma compacta:

${\displaystyle {\text{QFT}}(|x_{1}x_{2}\ldots x_{n}\rangle )={\frac {1}{\sqrt {N}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{n}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{n-1}x_{n}]}|1\rangle \right)\otimes \cdots \otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}\ldots x_{n}]}|1\rangle \right).}$

Para obtener este estado del circuito mostrado arriba, se debe realizar una operación de intercambio de los qubits para invertir su orden. Como máximo se requieren cambios. ^[3] ${\displaystyle n/2}$

Debido a que 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, se representa fácilmente como un circuito cuántico (hasta una inversión de orden de la salida). Cada una de esas operaciones de un solo qubit se puede implementar de manera eficiente utilizando una puerta Hadamard y un número lineal de puertas de fase controladas . El primer término requiere una puerta de Hadamard y puertas de fase controlada, el siguiente término requiere una puerta de Hadamard y una puerta de fase controlada, y cada término siguiente requiere una puerta de fase controlada menos. Sumar el número de puertas, excluyendo las necesarias para la inversión de salida, da como resultado puertas, que son un polinomio cuadrático en el número de qubits. ${\displaystyle (n-1)}$ ${\displaystyle (n-2)}$ ${\displaystyle n+(n-1)+\cdots +1=n(n+1)/2=O(n^{2})}$

La implementación a nivel de circuito de la transformada cuántica de Fourier en una arquitectura lineal del vecino más cercano se ha estudiado anteriormente. ^{[5] [6]} La profundidad del circuito es lineal en el número de qubits.

Aplicaciones de la transformada cuántica de Fourier

La Transformada Cuántica de Fourier (QFT) encuentra aplicaciones en un espectro de algoritmos y protocolos cuánticos, lo que demuestra su versatilidad e importancia en la computación cuántica y el procesamiento de información. Algunas aplicaciones notables incluyen:

Algoritmo de Shor

El algoritmo de Shor, un algoritmo cuántico histórico desarrollado por Peter Shor en 1994, explota el QFT para factorizar números enteros grandes de manera eficiente. Aprovechando las propiedades de periodicidad reveladas por el QFT, el algoritmo de Shor puede factorizar números enteros en tiempo polinómico, una tarea que sigue siendo exponencialmente difícil para las computadoras clásicas. Este algoritmo tiene profundas implicaciones para la criptografía, ya que hace que los criptosistemas clásicos de clave pública, como RSA, sean vulnerables a ataques cuánticos.

Estimación de fase cuántica

La estimación de fase cuántica (QPE) es una subrutina fundamental en muchos algoritmos cuánticos, incluido el algoritmo de Shor. QPE estima la fase de un vector propio correspondiente a un operador unitario. El QFT sirve como un componente clave en QPE, permitiendo la estimación eficiente de valores propios con alta precisión. Las aplicaciones de QPE se extienden más allá de la factorización de números enteros hasta diversas simulaciones cuánticas y problemas de química cuántica.

Procesamiento de señales cuánticas

En el procesamiento de señales cuánticas (QSP), el QFT juega un papel crucial en el análisis y manipulación de señales cuánticas. De manera análoga a las técnicas clásicas de procesamiento de señales, QSP implica tareas como transformación de señales, filtrado y análisis espectral. El QFT permite transformaciones de señales eficientes en el dominio cuántico, facilitando aplicaciones en comunicación, detección y procesamiento de datos cuánticos.

Aprendizaje automático cuántico

El aprendizaje automático cuántico (QML) aprovecha las técnicas de computación cuántica para mejorar los algoritmos tradicionales de aprendizaje automático. El QFT encuentra aplicaciones en el mapeo de características cuánticas y en los métodos del kernel, lo que permite la extracción eficiente de características y medidas de similitud a partir de datos cuánticos. Los algoritmos QML que emplean QFT prometen ventajas en tareas de reconocimiento, clasificación y optimización de patrones.

Corrección de errores cuánticos

La corrección de errores cuánticos (QEC) es esencial para mitigar los errores derivados de la decoherencia y el ruido en los sistemas cuánticos. La QFT, junto con otras operaciones cuánticas, constituye la base para el diseño de códigos de corrección de errores cuánticos y circuitos cuánticos tolerantes a fallos. Al codificar información cuántica en múltiples qubits y emplear técnicas de corrección y detección de errores basadas en QFT, los sistemas cuánticos pueden lograr una mayor estabilidad y confiabilidad.

Metrología cuántica

En metrología cuántica, el QFT permite mediciones precisas de cantidades físicas, superando los límites clásicos impuestos por el principio de incertidumbre de Heisenberg. Al codificar información en estados cuánticos y aplicar técnicas de medición basadas en QFT, los sensores cuánticos pueden alcanzar niveles de sensibilidad y precisión sin precedentes. Las aplicaciones de la metrología cuántica van desde la detección de ondas gravitacionales hasta la detección de campos magnéticos y más.

En resumen, la Transformada Cuántica de Fourier (QFT) sirve como un bloque de construcción fundamental en varios algoritmos y protocolos cuánticos, permitiendo tareas eficientes de computación, procesamiento de señales, corrección de errores, metrología y aprendizaje automático en el ámbito de la computación cuántica y el procesamiento de información. Su versatilidad y potencia subrayan su importancia para mejorar las capacidades de las tecnologías cuánticas.

Operaciones aritmeticas

Con pequeñas modificaciones al QFT, también se puede utilizar para realizar operaciones aritméticas enteras rápidas , como la suma y la multiplicación, en una computadora cuántica . También funciona con operaciones aritméticas de enteros de superposición , etc. ^{[7] [8]}

Ejemplo

La transformada cuántica de Fourier en tres qubits, con , está representada por la siguiente transformación: ${\displaystyle F_{8}}$ ${\displaystyle n=3,N=8=2^{3}}$

${\displaystyle {\text{QFT}}:|x\rangle \mapsto {\frac {1}{\sqrt {8}}}\sum _{k=0}^{7}\omega ^{xk}|k\rangle ,}$

donde una raíz octava de la unidad satisface . ${\displaystyle \omega =\omega _{8}}$ ${\displaystyle \omega ^{8}=\left(e^{\frac {i2\pi }{8}}\right)^{8}=1}$

La representación matricial de la transformada de Fourier en tres qubits es:

${\displaystyle F_{8}={\frac {1}{\sqrt {8}}}{\begin{bmatrix}1&1&1&1&1&1&1&1\\1&\omega &\omega ^{2}&\omega ^{3}&\omega ^{4}&\omega ^{5}&\omega ^{6}&\omega ^{7}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&1&\omega ^{2}&\omega ^{4}&\omega ^{6}\\1&\omega ^{3}&\omega ^{6}&\omega &\omega ^{4}&\omega ^{7}&\omega ^{2}&\omega ^{5}\\1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}&1&\omega ^{4}\\1&\omega ^{5}&\omega ^{2}&\omega ^{7}&\omega ^{4}&\omega &\omega ^{6}&\omega ^{3}\\1&\omega ^{6}&\omega ^{4}&\omega ^{2}&1&\omega ^{6}&\omega ^{4}&\omega ^{2}\\1&\omega ^{7}&\omega ^{6}&\omega ^{5}&\omega ^{4}&\omega ^{3}&\omega ^{2}&\omega \\\end{bmatrix}}.}$

La transformada cuántica de Fourier de 3 qubits se puede reescribir como:

${\displaystyle {\text{QFT}}(|x_{1},x_{2},x_{3}\rangle )={\frac {1}{\sqrt {8}}}\ \left(|0\rangle +e^{2\pi i\,[0.x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{2}x_{3}]}|1\rangle \right)\otimes \left(|0\rangle +e^{2\pi i\,[0.x_{1}x_{2}x_{3}]}|1\rangle \right).}$

El siguiente esquema muestra el circuito respectivo (con orden inverso de qubits de salida con respecto al QFT adecuado): ${\displaystyle n=3}$

Como se calculó anteriormente, el número de puertas utilizadas es igual a , para . ${\displaystyle n(n+1)/2}$ ${\displaystyle 6}$ ${\displaystyle n=3}$

Relación con la transformada cuántica de Hadamard

Utilizando la transformada de Fourier generalizada en grupos finitos (abelianos) , en realidad existen dos formas naturales de definir una transformada cuántica de Fourier en un registro cuántico de n -qubits . El QFT tal como se define anteriormente es equivalente al DFT, que considera estos n qubits indexados por el grupo cíclico . Sin embargo, también tiene sentido considerar los qubits 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. ^{[9] [10]} El algoritmo de Shor utiliza ambos tipos de transformadas de Fourier, una transformada inicial de Hadamard y una QFT. ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$ ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$

Referencias

1. https://ercim-news.ercim.eu/en128/special/quantum-fourier-transformation-in-industrial-applications
2. Calderero, D. (1994). "Una transformada de Fourier aproximada útil en factorización cuántica". Informe técnico RC19642, IBM . arXiv : quant-ph/0201067 .
3. Michael Nielsen e Isaac Chuang (2000). Computación cuántica e información cuántica . Cambridge: Prensa de la Universidad de Cambridge. ISBN 0-521-63503-9. OCLC  174527496.
4. Hales, L.; Hallgren, S. (12 al 14 de noviembre de 2000). "Un algoritmo y aplicaciones de transformada cuántica de Fourier mejorados". Actas del 41º Simposio Anual sobre Fundamentos de la Informática . págs. 515–525. CiteSeerX 10.1.1.29.4161 . doi :10.1109/SFCS.2000.892139. ISBN  0-7695-0850-2. S2CID  424297.
5. Fowler, AG; Devitt, SJ; Hollenberg, LCL (1 de julio de 2004). "Implementación del algoritmo de Shor en una matriz lineal de qubits vecinos más cercanos". Información y computación cuánticas . 4 (4): 237–251. doi :10.26421/QIC4.4-1. ISSN  1533-7146.
6. Maslov, Dmitri (15 de noviembre de 2007). "Circuitos de transformación cuántica de Fourier y estabilizador de profundidad lineal sin qubits auxiliares en arquitecturas cuánticas de vecinos finitos". Revisión física A. 76 (5): 052310. arXiv : quant-ph/0703211 . Código bibliográfico : 2007PhRvA..76e2310M. doi : 10.1103/PhysRevA.76.052310. S2CID  18645435.
7. Draper, Thomas G. (7 de agosto de 2000). "Suma en una computadora cuántica". arXiv : quant-ph/0008033 .
8. Ruiz-Pérez, Lidia; Juan Carlos, García-Escartin (2 de mayo de 2017). "Aritmética cuántica con la transformada cuántica de Fourier". Procesamiento de información cuántica . 16 (6): 152. arXiv : 1411.5949v2 . Código Bib : 2017QuiP...16..152R. doi :10.1007/s11128-017-1603-1. S2CID  10948948.
9. Análisis de Fourier de mapas booleanos – Un tutorial –, págs. 12-13
10. Conferencia 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: Información y computación cuánticas (CIT, septiembre de 1998)

enlaces externos

• Proyecto de demostración de Wolfram: circuito cuántico que implementa el algoritmo de búsqueda de Grover
• Proyecto de demostración de 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