In questo articolo consideriamo il problema di trovare il periodo di una funzione utilizzando un computer quantistico. L’algoritmo usa la trasformata di Fourier quantistica, che abbiamo visto in un precedente articolo, e lo utilizzeremo in seguito come parte dell’algoritmo di Shor per fattorizzare i numeri interi.
Supponiamo di voler determinare il periodo di una funzione $f : \Z_N \to Y$ dove $Y$ è un qualche insieme e $\Z_N = \{0,1,2,\ldots,N-1\}$ come prima. Più precisamente, il problema è il seguente. Supponiamo che ci sia data una funzione $f : \Z_N \to Y$ che è periodica con periodo ignoto $r$, cioè $f(n+r)=f(n)$. Perché ciò abbia senso, dobbiamo avere $r | N$, cioè che il periodo divida $N$, perciò supponiamo che ciò sia vero. Supponiamo inoltre che all’interno di ogni periodo, $f$ sia iniettiva, perciò in particolare se $0 \leq n_1, n_2 \leq r-1$ allora $f(n_1) \neq f(n_2)$. Il problema è determinare il periodo $r$ con errore al massimo di $1-\epsilon$ indipendente da $N$.
Da un punto di vista classico, il problema si risolve nella maniera seguente. Calcoliamo $f(n)$ per $n=0,1,2,\ldots$; appena troviamo $f(n) = f(0)$ allora sappiamo che la funzione $f$ ha periodo $n$ (questo perché $f$ è supposta iniettiva all’interno del periodo). Poiché $r$ divide $N$ e il massimo divisore di $N$ è minore o uguale di $\sqrt{N}$, nel caso peggiore dovremmo chiamare $f$ circa $\sqrt{N}$ volte, che è la complessità computazionale dell’algoritmo.
Nel caso quantistico procediamo nella maniera seguente. Partiamo dallo stato $\frac{1}{\sqrt{N}} \sum_{x} \ket{x}$, che per $N=2^k$ può essere realizzato applicando delle porte di Hadamard (come abbiamo visto in un precedente articolo) e può essere in ogni caso realizzato in qualche maniera. Poi, come nell’algoritmo di Deutsch-Josza, applichiamo l’operatore unitario $U_f$ a questo stato (con un qubit ausiliario che poi scartiamo) per ottenere lo stato
$$\ket{f} \equiv \frac{1}{\sqrt{N}} \sum_{x} \ket{x} \ket{f(x)}$$
dove ora lo spazio di Hilbert è il prodotto tensoriale dello spazio precedente $\C^N$ con lo spazio i cui elementi di base sono gli elementi di $Y$, cioè $\C^{\abs{Y}}$.
Ora effettuiamo una misurazione sullo spazio di Hilbert $\C^{\abs{Y}}$ e otteniamo come risultato un qualche $y \in Y$ uniformemente a caso. Ora scriviamo $A = N/r$, cioè il numero di periodi. Inoltre chiamiamo $x_0$ il più piccolo $x \in \Z_N$ tale che $f(x)=y$. Chiaramente non conosciamo né $x_0$ né $A$, ma soltanto $y$ che abbiamo misurato. Per le ipotesi su $f$, sappiamo che esistono esattamente $A$ input che danno come risultato $y$ e questi sono $x_0, x_0+r, \ldots x_0 + (A-1)r$. Perciò dopo la misurazione lo stato $\ket{f}$ collassa,
$$\ket{f} \to \ket{\mathrm{miao}}\equiv\pqty{\frac{1}{\sqrt{A}} \sum_{k=0}^{A-1} \ket{x_0+kr}} \ket{f(x_0)}$$
Ora $\ket{f(x_0)}$ è superfluo e non è più aggrovigliato agli stati dello spazio di Hilbert originale $\C^N$ e quindi lo scartiamo. Ora applichiamo la trasformata di Fourier quantistica allo stato $\mathrm{miao}$ ottenendo,
$$\mathcal{F} \ket{\mathrm{miao}} = \frac{1}{\sqrt{AN}} \sum_{k=0}^{A-1} \sum_{m=0}^{N-1} e^{-2\pi i \frac{(x_0+kr)m}{N}} \ket{m} = \frac{1}{\sqrt{AN}} \sum_{m=0}^{N-1} e^{-2\pi i \frac{x_0 m}{N}} \pqty{\sum_{k=0}^{A-1} e^{-2\pi i \frac{krm}{N}} } \ket{m}$$
La somma tra parentesi è uguale a zero a meno che $e^{-2\pi i \frac{rm}{N}}=1$, ovvero quando $rm/N$ è un intero. Sostituiamo perciò $m = \frac{N}{r} j$ per $j$ intero, ottenendo
$$\mathcal{F} \ket{\mathrm{miao}} = \sqrt{\frac{A}{N}} \sum_{j=0}^{r-1} e^{-2\pi i \frac{x_0 j}{r}} \ket{\frac{N}{r} j }$$
Il limite superiore della somma è $r-1$ perché $m \leq N-1$ e quindi effettuando la sostituzione, $j \leq r (1-1/N)$ e poiché $j$ è intero, ciò è equivalente a $j \leq r-1$. In altre parole, la trasformata di Fourier ha spostato $x_0$ dall’etichetta dello stato all’esponente della trasformata.
Ora possiamo di nuovo misurare lo stato $\ket{\mathrm{miao}}$ e otterremo come risultato uno degli stati $C=\frac{N}{r}j_0$ per un qualche $j=0,1,\ldots,r-1$ con probabilità uniforme. Quest’ultima equazione può essere riscritta come
$$\frac{j_0}{r} = \frac{C}{N}$$
Se $j_0$ ed $r$ fossero coprimi tra loro, allora per trovare $r$ basterebbe considerare la frazione $\frac{C}{N}$ di cui conosciamo numeratore e denominatore, ridurla ai minimi termini, et voilà, il denominatore $\widetilde{r}$ della frazione ridotta sarà uguale ad $r$. (Notiamo in particolare che questa operazione non richiede di fattorizzare i due numeri, ma può essere effettuata in maniera efficiente tramite l’algoritmo di Euclide).
Tuttavia non sappiamo se $j_0$ è coprimo con $r$. Supponiamo che non lo sia. In tal caso $j_0$ ed $r$ avranno dei fattori in comune, e quindi riducendo la frazione $C/N$ avremo eliminato troppi fattori, perciò $\widetilde{r} < r$ (e inoltre $\widetilde{r} | r$). Perciò possiamo controllare se $f(0)=f(\widetilde{r})$. Se sono uguali allora sappiamo che $\widetilde{r}=r$ (perché $\widetilde{r} < r$ e $f$ è iniettiva dentro ogni periodo), se invece non lo sono allora sappiamo che $j_0$ ed $r$ non sono coprimi. Abbiamo comunque imparato che $r$ ha un fattore $\widetilde{r}$ ma dovremmo ripetere di nuovo l’algoritmo per trovare il valore esatto.
Il motivo per cui questo algoritmo funziona è che effettivamente la probabilità che i due elementi siano coprimi non è malaccio. Il numero di elementi minori di $r$ coprimi con $r$ è dato dalla funzione di Eulero $\phi(r)$, che asintoticamente va come $\phi(r) \sim \frac{r}{\log{\log{r}}}$. Poiché $j_0$ potrebbe essere un numero qualsiasi, la probabilità che sia coprimo con $r$ è circa $\frac{1}{\log{\log{r}}} > \frac{1}{\log{\log{N}}}$. Perciò la probabilità di ottenere la risposta esatta al primo colpo va a zero per $N \to \infty$, ma ciò vuol dire che se vogliamo ottenere un algoritmo che ha errore costante dovremo ripetere la procedura circa $\log{\log{N}}$ volte. Ad ogni ciclo impariamo cose nuove: sappiamo che $\widetilde{r}$ divide $r$ che divide $N$, perciò l’errore in media decresce ad ogni ciclo. Perciò in realtà è anche possibile ottenere errore costante con un numero fisso di cicli indipendente da $N$, ma non dimostriamo esattamente come.
La complessità computazionale dell’algoritmo in questo caso è comunque polinomiale in $\log{N}$. Ciò perché sia la trasformata di Fourier quantistica, sia l’algoritmo Euclideo sono polinomiali in $\log{N}$ (il numero di cifre di $N$). L’applicazione di $f$ è meno importante, perché la applichiamo due volte per ciclo: una volta sullo stato quantistico e una volta alla fine per controllare, ma il numero di cicli è $\log{\log{N}}$ e quindi questo effetto è meno importante.
Se scriviamo $N \sim 2^k$ dove $k$ è il numero di cifre, l’algoritmo classico ha complessità esponenziale $\sim 2^{k/2}$, mentre l’algoritmo quantistico è polinomiale in $\log{N} \sim k$ e quindi è esponenzialmente più veloce.