In questo articolo introduciamo la trasformata di Fourier quantistica, che è alla base di molti algoritmi quantistici.
La trasformata di Fourier discreta
Prima di vedere la versione quantistica, consideriamo per un momento la trasformata di Fourier discreta, che è la versione classica della trasformata quantistica. Supponiamo di avere un numero intero $x$ modulo $N$. Cioè $x=0,1,2,\ldots N-1$ e quindi in termini astratti $x \in \Z_N$ è un elemento del gruppo ciclico con $N$ elementi. Una funzione su $\Z_N$ è una funzione $f: \Z_N \to \C$ che prende in input un intero modulo $N$ e sputa fuori un numero complesso. La sua trasformata di Fourier discreta è data da
$$\hat{f}(k) = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1} e^{-2\pi i \frac{k x}{N}} f(x)$$
dove anche $k = 0,1,2,\ldots N-1 \in \Z_N$. Ci sono come al solito diverse convenzioni per il prefattore. La trasformata inversa è data da
$$f(x) = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1} e^{2\pi i \frac{x k}{N}} \hat{f}$$
Per dimostrare che effettivamente la trasformazione inversa è data da questa formula, è sufficiente dimostrare che
$$ \frac{1}{N}\sum_{n=0}^{N-1} e^{2\pi i \frac{n m}{N}} = \begin{cases} 1 & m=0\\ 0 & \mathrm{altrimenti} \end{cases}$$
Se $m=0$ allora tutti i termini della somma sono uguali ad $1$ e quindi sommando e dividendo per $N$ otteniamo $1$. Se invece $m \neq 0$ possiamo usare la formula per la somma geometrica. Infatti ponendo $r= e^{2\pi i \frac{m}{N}}$ abbiamo
$$\sum_{n=0}^{N-1} e^{2\pi i \frac{n m}{N}} = \sum_{n=0}^{N-1} r^n = \frac{1-r^N}{1-r} =0$$
poiché $r^N=1$. Ciò conclude la dimostrazione.
Trasformata di Fourier quantistica
Ora consideriamo la versione quantistica della stessa cosa. Supponiamo di avere un sistema quantistico il cui spazio di Hilbert ha $N$ stati. Per un sistema di $k$ qubit, $N=2^k$. In questo caso non ci limitiamo a potenze di due e scegliamo un sistema arbitrario per etichettare una base di stati, chiamandola $\{\ket{n}\}$ per $n=0,1,\ldots, N-1$. La trasformata di Fourier quantistica $\mathcal{F}$ è definita in maniera analoga alla trasformata di Fourier discreta. Sulla base di stati definiamo
$$\mathcal{F} \ket{n} = \frac{1}{\sqrt{N}}\sum_{m=0}^{N-1} e^{-2\pi i \frac{m n}{N}} \ket{m}$$
Estendiamo poi $\mathcal{F}$ a tutto lo spazio di Hilbert per linearità. In termini matriciali, notiamo che gli elementi di matrice dell’operatore $\mathcal{F}$ sono $\mathcal{F}_{nm} = \frac{1}{\sqrt{N}} e^{-2\pi i \frac{m n}{N}}$. In particolare, $\mathcal{F}$ è una matrice simmetrica. Inoltre la trasformazione è suriettiva ed è anche unitaria, perché
$$(\mathcal{F} \mathcal{F}^\dagger)_{nm} = \sum_{k=0}^{N-1} \mathcal{F}_{nk} \mathcal{F}_{mk}^* = \frac{1}{N} \sum_{k=0}^{N-1} e^{-2\pi i \frac{k (n-m)}{N}} = \delta_{nm}$$
per la formula che abbiamo dimostrato nella sezione precedente. Un caso particolarmente semplice è $N=2$, cioè un singolo qubit. In tal caso $e^{-2\pi i \frac{m n}{N}}=(-1)^{mn}$ e quindi
$$\mathcal{F} \ket{0} = \frac{\ket{0} + \ket{1}}{\sqrt{2}} \quad \quad \quad \mathcal{F} \ket{1} = \frac{\ket{0} -\ket{1}}{\sqrt{2}}$$
Cioè $\mathcal{F}$ è identica alla porta di Hadamard su un singolo qubit. Il collegamento con la trasformata discreta è abbastanza chiaro ma può essere reso più esplicito. In particolare supponiamo di avere uno stato generico
$$\ket{f} \equiv \sum_{n=0}^{N-1} f(n) \ket{n}$$
Allora applicando la trasformata di Fourier quantistica abbiamo
$$\mathcal{F} \ket{f} = \sum_{n=0}^{N-1} f(n)\mathcal{F} \ket{n}=\sum_{m=0}^{N-1} \frac{1}{\sqrt{N}} \sum_{n=0}^{N-1} f(n) e^{-2\pi i \frac{m n}{N}} \ket{m} = \sum_{m=0}^{N-1} \hat{f}(m) \ket{m}$$
Ovvero se uno stato ha funzione d’onda $f$, applicando la trasformata di Fourier quantistica otteniamo uno stato che ha funzione d’onda $\hat{f}$, cioè la trasformata discreta di $f$.
La cosa utile della trasformata di Fourier quantistica è che può essere implementata in maniera efficiente. In linea di massima, per implementare un operatore unitario generico su uno spazio con $N=2^k$ stati sono necessarie un numero di operazioni esponenziale in $k$ e queste operazioni unitarie sono perciò costose da implementare. Il vantaggio della trasformata di Fourier è che può essere implementata in un circuito quantistico con $k^2$ operazioni, il che è molto efficiente. Ciò non dovrebbe sorprenderci: per la trasformata discreta classica esiste un algoritmo efficiente, la trasformata veloce, e molti dei trucchi usati in quel caso si possono esportare a quello quantistico.