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.

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 $2^n$ampiezze può essere implementato come un circuito quantistico che consiste solo di $O(n^2)$ porte di Hadamard e porte di phase shift controllate, dove $n$ è il numero dei qubit. Ciò può essere paragonato alla trasformata di Fourier discreta classica, che ha $O(n{2}^n)$ porte (dove $n$ è il numero dei bit), che è esponenzialmente più di $O(n^2)$.

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

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 $N=2^n$.

La trasformata di Fourier classica agisce su un vettore $(x_0,x_1,\dots ,x_{N-1})\in {ℂ}^N$ e lo mappa sul vettore $(y_0,y_1,\dots ,y_{N-1})\in {ℂ}^N$ secondo la formula:

$y_k=\frac{1}{\sqrt{N}}\sum _{n=0}^{N-1}{x}_n{\omega }_N^{-kn},k=0,1,2,\dots ,N-1,$

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

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

$y_k=\frac{1}{\sqrt{N}}\sum _{n=0}^{N-1}{x}_n{\omega }_N^{nk},k=0,1,2,\dots ,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 ${\omega }_N^n$ è una rotazione, la trasformata inversa agisce similmente ma con:

$x_n=\frac{1}{\sqrt{N}}\sum _{k=0}^{N-1}{y}_k{\omega }_N^{-nk},n=0,1,2,\dots ,N-1.$

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

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

Equivalentemente, la trasformata può essere vista come una matrice unitaria $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

$F_N=\frac{1}{\sqrt{N}}\left[\begin{array}{cccccc}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)}\\ ⋮& ⋮& ⋮& ⋮& & ⋮\\ 1& {\omega }^{N-1}& {\omega }^{2(N-1)}& {\omega }^{3(N-1)}& \cdots & {\omega }^{(N-1)(N-1)}\end{array}\right]$

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

$F_4=\frac{1}{2}\left[\begin{array}{cccc}1& 1& 1& 1\\ 1& i& -1& -i\\ 1& -1& 1& -1\\ 1& -i& -1& i\end{array}\right]$

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 $F{F}^{†}=F^{†}F=I$, dove $F^{†}$ è l'aggiunto di $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, $F^{-1}=F^{†}$. 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 $R_m$, definite come

$H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)\text{e}{R}_m=\left(\begin{array}{cc}1& 0\\ 0& e^{\frac{2\pi i}{2^m}}\end{array}\right)$

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

Note

• 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