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