Transformada quàntica de Fourier

Transformada de Fourier quàntica en n qubits.

Circuit quàntic per a la transformada quàntica de Fourier amb 3 qubits.

En computació quàntica, la transformada quàntica de Fourier (amb acrònim anglès QFT) és una transformació lineal sobre bits quàntics, i és l'anàleg quàntic de la transformada de Fourier discreta. La transformada quàntica de Fourier forma part de molts algorismes quàntics, en particular l'algoritme de Shor per factoritzar i calcular el logaritme discret, l'algoritme d'estimació de fase quàntica per estimar els valors propis d'un operador unitari i algorismes per al problema del subgrup ocult. La transformada quàntica de Fourier va ser descoberta per Don Coppersmith.^[1]

La transformada quàntica de Fourier es pot realitzar de manera eficient en un ordinador quàntic amb una descomposició en el producte de matrius unitàries més simples. La transformada discreta de Fourier activa ${\displaystyle 2^{n}}$ les amplituds es poden implementar com un circuit quàntic que consisteix només en ${\displaystyle O(n^{2})}$ Portes Hadamard i portes de canvi de fase controlats, on ${\displaystyle n}$ és el nombre de qubits.^[2] Això es pot comparar amb la transformada discreta de Fourier clàssica, que pren ${\displaystyle O(n2^{n})}$ portes (on ${\displaystyle n}$ és el nombre de bits), que és exponencialment més que ${\displaystyle O(n^{2})}$.^[3]

La transformada quàntica de Fourier actua sobre un vector d'estat quàntic (un registre quàntic), i la transformada de Fourier clàssica actua sobre un vector. Els dos tipus de vectors es poden escriure com a llistes de nombres complexos. En el cas quàntic, és una seqüència d'amplituds de probabilitat per a tots els resultats possibles després de la mesura (anomenats estats bàsics o estats propis). Com que la mesura col·lapsa l'estat quàntic a un únic estat base, no totes les tasques que utilitzen la transformada de Fourier clàssica poden aprofitar l'acceleració exponencial de la transformada de Fourier quàntica.

Els millors algorismes de transformada quàntica de Fourier coneguts (a finals de 2000) només requereixen ${\displaystyle O(n\log n)}$ portes per aconseguir una aproximació eficient.^[4]

La transformada quàntica de Fourier és la transformada de Fourier discreta clàssica aplicada al vector d'amplituds d'un estat quàntic, on normalment considerem vectors de longitud. ${\displaystyle N=2^{n}}$ .

La transformada de Fourier clàssica actua sobre un vector ${\displaystyle (x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}}$ i el mapa al vector ${\displaystyle (y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}}$ segons la fórmula:

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

on ${\displaystyle \omega _{N}=e^{\frac {2\pi i}{N}}}$ i ${\displaystyle \omega _{N}^{n}}$ és una arrel N de la unitat.

Referències

1. Coppersmith, D. Technical Report RC19642, IBM, 1994. arXiv: quant-ph/0201067.
2. Michael Nielsen and Isaac Chuang. Quantum Computation and Quantum Information (en anglès). Cambridge: Cambridge University Press, 2000. ISBN 0-521-63503-9. OCLC 174527496. 
3. «Quantum Fourier Transform» (en anglès). https://community.qiskit.org.+[Consulta: 17 novembre 2022].
4. Hales, L.; Hallgren, S. Proceedings 41st Annual Symposium on Foundations of Computer Science, 1 novembre 2–14, 2000, pàg. 515–525. DOI: 10.1109/SFCS.2000.892139.