Trasformata di Fourier quantistica

In computazione quantistica, la trasformata di Fourier quantistica (abbreviazione dall'inglese: QFT) è una trasformazione lineare su qubit, ed è l'analogo quantistico della trasformata discreta di Fourier inversa. La trasformata di Fourier quantistica fa parte di molti algoritmi quantistici, in particolare l'algoritmo di fattorizzazione di Shor per fattorizzare e calcolare il logaritmo discreto, l'algoritmo quantistico di stima della fase per stimare gli autovalori di un operatore unitario, e algoritimi per il problema del sottogruppo nascosto. La trasformata di Fourier quantistica fu inventata da Don Coppersmith.^[1]

La trasformata di Fourier quantistica può essere effettuata efficientemente su un computer quantistico, con una particolare scomposizione in un prodotto di matrici unitarie più semplici. Usando una semplice scomposizione, la trasformata di Fourier discreta su ${\displaystyle 2^{n}}$ampiezze può essere implementato come un circuito quantistico che consiste solo di ${\displaystyle O(n^{2})}$ porte di Hadamard e porte di phase shift controllate, dove ${\displaystyle n}$ è il numero dei qubit.^[2] Ciò può essere paragonato alla trasformata di Fourier discreta classica, che ha ${\displaystyle O(n2^{n})}$ porte (dove ${\displaystyle n}$ è il numero dei bit), che è esponenzialmente più di ${\displaystyle O(n^{2})}$.

I migliori algoritmi noti per la trasformata di Fourier quantistica (agli ultimi anni 2000) necessitano solo di ${\displaystyle O(n\log n)}$ porte per ottenere una buona approssimazione.^[3]

Definizione

La trasformata di Fourier quantistica è la trasformata di Fourier classica applicata al vettore di ampiezze di uno stato quantistico, dove solitamente si considerano vettori di lunghezza ${\displaystyle N=2^{n}}$.

La trasformata di Fourier classica agisce su un vettore ${\displaystyle (x_{0},x_{1},\ldots ,x_{N-1})\in \mathbb {C} ^{N}}$ e lo mappa sul vettore ${\displaystyle (y_{0},y_{1},\ldots ,y_{N-1})\in \mathbb {C} ^{N}}$ secondo la formula:

${\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,}$

dove ${\displaystyle \omega _{N}=e^{\frac {2\pi i}{N}}}$ e ${\displaystyle \omega _{N}^{n}}$ è la ${\displaystyle N}$-esima radice dell'unità.

Similmente, la trasformata di Fourier quantistica agisce su uno stato quantistico ${\displaystyle |x\rangle =\sum _{i=0}^{N-1}x_{i}|i\rangle }$ e lo mappa su uno stato quantistico ${\displaystyle \sum _{i=0}^{N-1}y_{i}|i\rangle }$ secondo la formula:

${\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.}$

(Le convenzioni per il segno del fattore di fase all'esponente sono molteplici; qui si usa la convenzione secondo la quale la trasformata ha lo stesso effetto della trasformata inversa, e viceversa.)

Siccome ${\displaystyle \omega _{N}^{n}}$ è una rotazione, la trasformata inversa agisce similmente ma con:

${\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.}$

Nel caso in cui ${\displaystyle |x\rangle }$ sia uno stato di base, la trasformata di Fourier quantistica (QFT) può essere espressa come la mappa

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

Equivalentemente, la trasformata può essere vista come una matrice unitaria ${\displaystyle F_{N}}$ (o una porta quantistica, simile a una porta logica booleana per i computer classici), che agisce su vettori di stato quantico, data da

${\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}}}$

dove ${\displaystyle \omega =\omega _{N}}$. Nel caso di ${\displaystyle N=4=2^{2}}$ e fase ${\displaystyle \omega =i}$ la matrice di trasformazione diventa

${\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}}}$

Proprietà

Unitarietà

La maggior parte delle proprietà della trasformata di Fourier quantistica segue dal fatto che è una trasformazione unitaria. Questo può essere controllato effettuando la moltiplicazione di matrici e assicurandosi che valga la relazione ${\displaystyle FF^{\dagger }=F^{\dagger }F=I}$, dove ${\displaystyle F^{\dagger }}$ è l'aggiunto di ${\displaystyle F}$. In alternativa, si può vedere che vettori ortogonali di norma 1 siano mappati a vettori ortogonali di norma 1.

Dalla unitarietà segue che la trasformata inversa sia l'aggiunta della matrice di Fourier, ${\displaystyle F^{-1}=F^{\dagger }}$. Siccome ci sono circuiti che implementano la trasformata, gli stessi circuiti possono essere attivati percorsi al contrario per effettuare la trasformata inversa. Quindi entrambe le trasformate possono essere effettuate in modo efficiente su un computer quantistico.

Implementazione in un circuito

Le porte quantistiche usate nel circuito sono la porta di Hadamard e la phase gate controllata ${\displaystyle R_{m}}$, definite come

${\displaystyle H={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}\qquad {\text{e}}\qquad R_{m}={\begin{pmatrix}1&0\\0&e^{\frac {2\pi i}{2^{m}}}\end{pmatrix}}}$

dove ${\displaystyle e^{\frac {2\pi i}{2^{m}}}=\omega _{m}'=\omega _{\left(2^{m}\right)}}$ è la ${\displaystyle 2^{m}}$-esima radice dell'unità. Il circuito è quindi composto da porte ${\displaystyle H}$ e la versione controllata di ${\displaystyle R_{m}}$

Note

1. D. Coppersmith, An approximate Fourier transform useful in quantum factoring., in Technical Report RC19642, IBM, 16 gennaio 2002 [1994].
2. Michael Nielsen and Isaac Chuang, Quantum Computation and Quantum Information, Cambridge, Cambridge University Press, 2000, ISBN 0-521-63503-9, OCLC 174527496.
3. L. Hales e S. Hallgren, An improved quantum Fourier transform algorithm and applications, in Proceedings 41st Annual Symposium on Foundations of Computer Science, November 12-14, 2000, pp. 515–525, DOI:10.1109/SFCS.2000.892139, ISBN 0-7695-0850-2.

• K. R. Parthasarathy, Lectures on Quantum Computation and Quantum Error Correcting Codes (Indian Statistical Institute, Delhi Center, giugno 2001)
• John Preskill, Lecture Notes for Physics 229: Quantum Information and Computation (CIT, settembre 1998)

Collegamenti esterni

• Wolfram Demonstration Project: Quantum Circuit Implementing Grover's Search Algorithm
• Wolfram Demonstration Project: Quantum Circuit Implementing Quantum Fourier Transform
• Quirk online life quantum fourier transform

Portale Informatica

Portale Matematica

Portale Quantistica