Transformada cuántica de Fourier

Cambio de base aplicado en 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 del subgrupo oculto . La transformada cuántica de Fourier fue descubierta por Don Coppersmith . ^[1] Con pequeñas modificaciones a la QFT, también se puede utilizar para realizar operaciones aritméticas rápidas de números enteros, como la suma y la multiplicación. ^{[2] [3] [4]}

La transformada de Fourier cuántica se puede realizar de manera eficiente en una computadora cuántica con una descomposición en el producto de matrices unitarias más simples . La transformada de Fourier discreta en amplitudes se puede implementar como un circuito cuántico que consta solo de puertas de Hadamard y puertas de desplazamiento de fase controlado , donde es el número de cúbits. ^[5] Esto se puede comparar con la transformada de Fourier discreta clásica, que toma puertas (donde es el número de bits), que es exponencialmente más 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 clásica de Fourier discreta actúa sobre un vector. Ambos tipos de vectores se pueden escribir como listas de números complejos. En el caso clásico, el vector se puede representar, por ejemplo, con una matriz de números de punto flotante , y 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 base o estados propios ). Debido a que la medición colapsa el estado cuántico a un solo estado base, no todas las tareas que utilizan la transformada clásica de Fourier 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 solo puertas para lograr una aproximación eficiente, siempre que se implemente una puerta de fase controlada como una operación nativa. ^[6] ${\displaystyle O(n\log n)}$

Definición

La transformada cuántica de Fourier es la clásica transformada de Fourier discreta aplicada al vector de amplitudes de un estado cuántico, que tiene longitud si se aplica a un registro de qubits. ${\displaystyle N=2^{n}}$ ${\displaystyle 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 es una raíz N -ésima de la unidad . ${\displaystyle \omega _{N}=e^{\frac {2\pi i}{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 de Fourier cuántica tiene el mismo efecto que la transformada de Fourier discreta inversa, y viceversa).

Dado que es una rotación, la transformada cuántica de Fourier inversa 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 se trate de 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}}}$

donde . 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 cumple la relación , donde es el adjunto hermítico de . Alternativamente, se puede comprobar que los vectores ortogonales de norma 1 se asignan a vectores ortogonales de 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 hermítico 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 en sentido inverso para realizar la transformada cuántica de Fourier inversa. Por lo tanto, ambas transformadas 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 qubits son la puerta 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 base

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

Estos estados base 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 la notación del producto tensorial , indica que el qubit está en el estado , con 0 o 1. Por convención, el índice del 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 de Hadamard es , donde el signo depende de . ${\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 manera 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 a partir del circuito representado arriba, se debe realizar una operación de intercambio de los cúbits para invertir su orden. Como máximo, se requieren intercambios. ^[5] ${\displaystyle n/2}$

Como la transformada de Fourier discreta, una operación sobre n cúbits, puede factorizarse en el producto tensorial de n operaciones de un solo cúbit, 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 cúbit se puede implementar de manera eficiente utilizando una compuerta de Hadamard y un número lineal de compuertas de fase controlada . El primer término requiere una compuerta de Hadamard y compuertas de fase controlada, el siguiente término requiere una compuerta de Hadamard y una compuerta de fase controlada, y cada término siguiente requiere una compuerta de fase controlada menos. Sumando el número de compuertas, excluyendo las necesarias para la inversión de salida, se obtienen compuertas, que es un polinomio cuadrático en el número de cúbits. Este valor es mucho menor que para la transformada de Fourier clásica. ^[7] ${\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 de vecino más cercano lineal se ha estudiado anteriormente. ^{[8] [9]} La profundidad del circuito es lineal en el número de qubits.

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 es una octava raíz de la unidad que 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 correspondiente (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 que es igual a , para . ${\displaystyle n(n+1)/2}$ ${\displaystyle 6}$ ${\displaystyle n=3}$

Relación con la transformada cuántica de Hadamard

Usando 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 -qubits . La QFT como se definió arriba es equivalente a la 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 compuerta de Hadamard a cada uno de los n qubits en paralelo. ^{[10] [11]} El algoritmo de Shor usa ambos tipos de transformadas de Fourier, una transformada de Hadamard inicial así como una QFT. ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$ ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$

Para otros grupos

La transformada de Fourier se puede formular para grupos distintos del grupo cíclico y extenderse al entorno cuántico. ^[12] Por ejemplo, considere el grupo simétrico . ^{[13] [14]} La transformada de Fourier se puede expresar en forma matricial ${\displaystyle S_{n}}$

${\displaystyle {\mathfrak {F}}_{n}=\sum _{\lambda \in \Lambda _{n}}\sum _{p,q\in {\mathcal {P}}(\lambda )}\sum _{g\in S_{n}}{\sqrt {\frac {d_{\lambda }}{n!}}}[\lambda (g)]_{q,p}|\lambda ,p,q\rangle \langle g|}$

donde es el elemento de la representación matricial de , es el conjunto de caminos desde el nodo raíz hasta en el diagrama de Bratteli de , es el conjunto de representaciones de indexadas por diagramas de Young, y es una permutación. ${\displaystyle [\lambda (g)]_{q,p}}$ ${\displaystyle (q,p)}$ ${\displaystyle \lambda (g)}$ ${\displaystyle {\mathcal {P}}(\lambda )}$ ${\displaystyle \lambda }$ ${\displaystyle S_{n}}$ ${\displaystyle \Lambda _{n}}$ ${\displaystyle S_{n}}$ ${\displaystyle g}$

Sobre un campo finito

La transformada de Fourier discreta también se puede formular sobre un campo finito , y se puede definir una versión cuántica. ^[15] Aquí . Sea un mapa lineal arbitrario (traza, por ejemplo). Luego, para cada definición ${\displaystyle F_{q}}$ ${\displaystyle N=q=p^{n}}$ ${\displaystyle \phi :GF(q)\rightarrow GF(p)}$ ${\displaystyle x\in GF(q)}$

${\displaystyle F_{q,\phi }:|x\rangle \mapsto {\frac {1}{\sqrt {q}}}\sum _{y\in GF(q)}\omega ^{\phi (xy)}|y\rangle }$

para y se extienden linealmente. ${\displaystyle \omega =e^{2\pi i/p}}$ ${\displaystyle F_{q,\phi }}$

Referencias

1. Coppersmith, D. (2002). Una transformada de Fourier aproximada útil en factorización cuántica (Preimpresión). arXiv : quant-ph/0201067 .
2. Draper, Thomas G. (7 de agosto de 2000). "Suma en una computadora cuántica". arXiv : quant-ph/0008033 .
3. Ruiz-Pérez, Lidia; Juan Carlos, Garcia-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 Bibliográfico :2017QuIP...16..152R. doi :10.1007/s11128-017-1603-1. S2CID  10948948.
4. Şahin, Engin (2020). "Operaciones aritméticas cuánticas basadas en la transformada cuántica de Fourier sobre números enteros con signo". Revista Internacional de Información Cuántica . 18 (6): 2050035. arXiv : 2005.00443v3 . doi :10.1142/s0219749920500355. ISSN  1793-6918.
5. Nielsen, Michael A.; Chuang, Isaac L. (2012). Computación cuántica e información cuántica . doi :10.1017/CBO9780511976667. ISBN 978-1-107-00217-3.
6. Hales, L.; Hallgren, S. (12-14 de noviembre de 2000). "Un algoritmo de transformada cuántica de Fourier mejorado y aplicaciones". Actas del 41.º Simposio anual sobre fundamentos de la informática . pp. 515-525. CiteSeerX 10.1.1.29.4161 . doi :10.1109/SFCS.2000.892139. ISBN .  0-7695-0850-2.S2CID 424297  .
7. Kurgalin, Sergei; Borzunov, Sergei (2021). Guía concisa de computación cuántica: algoritmos, ejercicios e implementaciones . Textos de informática. Cham: Springer. ISBN 978-3-030-65054-4.
8. Fowler, AG; Devitt, SJ; Hollenberg, LCL (julio de 2004). "Implementación del algoritmo de Shor en una matriz lineal de cúbits vecinos más próximos". Información y computación cuántica . 4 (4): 237–251. doi :10.26421/QIC4.4-1.
9. Maslov, Dmitri (15 de noviembre de 2007). "Estabilizador de profundidad lineal y circuitos de transformación cuántica de Fourier sin cúbits auxiliares en arquitecturas cuánticas de vecinos finitos". Physical Review A . 76 (5): 052310. arXiv : quant-ph/0703211 . Bibcode :2007PhRvA..76e2310M. doi :10.1103/PhysRevA.76.052310. S2CID  18645435.
10. Análisis de Fourier de mapas booleanos: un tutorial, págs. 12-13 ^{[ cita completa necesaria ]}
11. Conferencia 5: Algoritmos cuánticos básicos, Rajat Mittal, págs. 4-5 ^{[ enlace roto ]}
12. Moore, Cristopher; Rockmore, Daniel; Russell, Alexander (2003). Transformadas de Fourier cuánticas genéricas (preimpresión). arXiv : quant-ph/0304064 .
13. Kawano, Yasuhito; Sekigawa, Hiroshi (julio de 2016). "Transformada cuántica de Fourier sobre grupos simétricos: resultado mejorado". Journal of Symbolic Computation . 75 : 219–243. doi :10.1016/j.jsc.2015.11.016.
14. Beals, Robert (1997). "Cálculo cuántico de transformadas de Fourier sobre grupos simétricos". Actas del vigésimo noveno simposio anual de la ACM sobre teoría de la computación - STOC '97 . págs. 48-53. doi :10.1145/258533.258548. ISBN 0-89791-888-6.
15. de Beaudrap, Niel; Cleve, Richard; Waltrous, John (8 de noviembre de 2002). "Separaciones de complejidad de consultas clásicas y cuánticas nítidas". Algorithmica . 34 (4): 449–461. doi :10.1007/s00453-002-0978-1.

Lectura adicional

• Parthasarathy, KR (2006). Conferencias sobre computación cuántica, códigos de corrección de errores cuánticos y teoría de la información . Instituto Tata de Investigación Fundamental. ISBN 978-81-7319-688-1.
• Preskill, John (septiembre de 1998). "Apuntes de la clase de Física 229: Información y computación cuántica" (PDF) .

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