Algoritmo di Shor

Ora ci occuperemo del problema della fattorizzazione dei numeri interi e vedremo come può essere risolto in modo efficiente su un computer quantistico utilizzando la stima di fase. L'algoritmo che otterremo è l' algoritmo di Shor per la fattorizzazione dei numeri interi. Shor non ha descritto il suo algoritmo specificamente in termini di stima di fase, ma è un modo naturale e intuitivo per spiegarne il funzionamento.

Inizieremo discutendo un problema intermedio noto come problema di ricerca dell'ordine e vedremo come la stima di fase fornisca una soluzione a questo problema. Vedremo poi come una soluzione efficiente al problema della ricerca degli ordini ci dia una soluzione efficiente al problema della fattorizzazione degli interi. (Quando la soluzione di un problema fornisce una soluzione a un altro problema di questo tipo, si dice che il secondo problema si riduce al primo, quindi in questo caso stiamo riducendo la fattorizzazione degli interi alla ricerca di ordini) Questa seconda parte dell'algoritmo di Shor non fa affatto uso dell'informatica quantistica, ma è completamente classica. Il calcolo quantistico è necessario solo per risolvere la ricerca di ordini.

---

Il problema della ricerca degli ordini

Alcuni concetti fondamentali di teoria dei numeri

Per spiegare il problema della ricerca dell'ordine e il modo in cui può essere risolto utilizzando la stima di fase, sarà utile iniziare con un paio di concetti di base della teoria dei numeri e introdurre alcune notazioni utili lungo il percorso.

Per cominciare, per ogni dato numero intero positivo $N$, definiamo l’insieme $\mathbb{Z}_N$ nel modo seguente.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

Per esempio, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ e così via.

Si tratta di insiemi di numeri, ma possiamo considerarli come qualcosa di più di semplici insiemi. In particolare, possiamo considerare le operazioni aritmetiche su $\mathbb{Z}_N$, come l'addizione e la moltiplicazione — e se concordiamo di considerare sempre i risultati modulo $N$ (cioè, dividere per $N$ e considerare il resto come risultato), rimarremo sempre all'interno di questo insieme quando eseguiamo queste operazioni. Le due operazioni specifiche dell’addizione e della moltiplicazione, entrambe considerate modulo $N$, trasformano $\mathbb{Z}_N$ in un anello, che è un tipo di oggetto di fondamentale importanza in algebra.

Ad esempio, $3$ e $5$ sono elementi di $\mathbb{Z}_7$, e se li moltiplichiamo tra loro otteniamo $3\cdot 5 = 15$, che, diviso per $7$, lascia un resto pari a $1$. A volte lo esprimiamo come segue.

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

Ma possiamo anche scrivere semplicemente “ $3 \cdot 5 = 1$ ”, a condizione che sia stato chiarito che stiamo lavorando in “ $\mathbb{Z}_7$ ”, proprio per mantenere la nostra notazione il più semplice possibile.

A titolo di esempio, ecco le tabelline dell’addizione e della moltiplicazione per $\mathbb{Z}_6$.

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

Tra gli elementi $N$ di $\mathbb{Z}_N$, gli elementi $a\in\mathbb{Z}_N$ che soddisfano $\gcd(a,N) = 1$ sono speciali. Spesso l'insieme che contiene questi elementi viene indicato con un asterisco, in questo modo.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

Se concentriamo la nostra attenzione sull'operazione della moltiplicazione, l'insieme $\mathbb{Z}_N^{\ast}$ forma un gruppo — in particolare un gruppo abeliano — che rappresenta un altro importante tipo di oggetto in algebra. È un fatto fondamentale relativo a questi insiemi (e ai gruppi finiti in generale) che, se si sceglie un elemento qualsiasi $a\in\mathbb{Z}_N^{\ast}$ e si moltiplica ripetutamente $a$ per se stesso, alla fine si otterrà sempre il numero $1$.

Come primo esempio, prendiamo $N=6$. Si ha che $5\in\mathbb{Z}_6^{\ast}$ poiché $\gcd(5,6) = 1$, e se moltiplichiamo $5$ per se stesso otteniamo $1$, come conferma la tabella sopra riportata.

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

Come secondo esempio, prendiamo $N = 21$. Se esaminiamo i numeri da $0$ a $20$, quelli con MCD pari a $1$ con $21$ sono i seguenti.

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

Per ciascuno di questi elementi, è possibile elevare tale numero a una potenza intera positiva per ottenere un numero di tipo “ $1$ ”. Ecco le potenze minime per le quali ciò è possibile:

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

Naturalmente, per tutte queste equazioni lavoriamo all'interno di $\mathbb{Z}_{21}$, che non ci siamo presi la briga di scrivere: lo consideriamo implicito per non appesantire le cose. Continueremo a farlo nel resto della lezione.

Descrizione del problema e collegamento alla stima di fase

Ora possiamo enunciare il problema della ricerca dell'ordine.

Input: numeri interi positivi $N$ e $a$ soddisfacenti $\gcd(N,a) = 1$\ Output: il più piccolo intero positivo $r$ tale che $a^r \equiv 1$ $(\textrm{mod } N)$

In alternativa, utilizzando la notazione appena introdotta, ci viene dato un numero $a \in \mathbb{Z}_N^{\ast}$ e dobbiamo trovare il più piccolo numero intero positivo $r$ tale che $a^r = 1$. Questo numero $r$ è chiamato ordine di $a$ modulo $N$.

Per collegare il problema della ricerca dell'ordine alla stima di fase, consideriamo l'operazione definita su un sistema i cui stati classici corrispondono a $\mathbb{Z}_N$, dove si moltiplica per un elemento fisso $a\in\mathbb{Z}_N^{\ast}$.

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

Per chiarezza, stiamo effettuando la moltiplicazione in un sistema di coordinate di tipo “ $\mathbb{Z}_N$ ”, quindi è implicito che stiamo calcolando il prodotto modulo “ $N$ ” all’interno del ket che si trova sul lato destro dell’equazione.

Ad esempio, se consideriamo $N = 15$ e $a=2$, l’azione di $M_2$ sulla base standard $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ è la seguente.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

Si tratta di un'operazione unitaria, purché $\gcd(a,N)=1$; essa rimescola gli elementi della base standard $\{\vert 0\rangle,\ldots,\vert N-1\rangle\}$, quindi, come matrice, è una matrice di permutazione. Dalla sua definizione risulta evidente che questa operazione è deterministica, e un modo semplice per dimostrare che è invertibile consiste nel considerare l’ordine $r$ di $a$ modulo $N$, e nel riconoscere che l’inverso di $M_a$ è $M_a^{r-1}$.

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

C'è un altro modo di concepire l'inverso che non richiede alcuna conoscenza dell' $r$ o (che, dopotutto, è proprio ciò che stiamo cercando di calcolare). Per ogni elemento $a\in\mathbb{Z}_N^{\ast}$ esiste sempre un elemento unico $b\in\mathbb{Z}_N^{\ast}$ che soddisfa $ab=1$. Indichiamo questo elemento $b$ con $a^{-1}$, che può essere calcolato in modo efficiente; un’estensione dell’algoritmo di Euclide per il MCD lo fa con un costo quadratico in $\operatorname{lg}(N)$. E quindi

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

Quindi, l'operazione $M_a$ è sia deterministica che invertibile. Ciò implica che è descritto da una matrice di permutazione e quindi è unitario.

Consideriamo ora gli autovettori e gli autovalori dell'operazione $M_a$, supponendo che $a\in\mathbb{Z}_N^{\ast}$. Come appena dimostrato, questa supposizione ci indica che $M_a$ è unitaria.

Esistono $N$ autovalori di $M_a$, tra cui potrebbe figurare lo stesso autovalore ripetuto più volte, e in generale vi è una certa libertà nella scelta dei vettori propri corrispondenti — ma non sarà necessario considerare tutte le possibilità. Cominciamo in modo semplice e identifichiamo un solo vettore proprio di $M_a$.

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

Il numero $r$ è l'ordine di $a$ modulo $N$, qui e per tutto il resto della lezione. L'autovalore associato a questo autovettore è $1$ poiché rimane invariato quando lo moltiplichiamo per $a$.

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

Ciò accade perché $a^r = 1$, quindi ogni stato della base standard $\vert a^k \rangle$ viene spostato a $\vert a^{k+1} \rangle$ per $k\leq r-1$, mentre $\vert a^{r-1} \rangle$ torna a $\vert 1\rangle$. In parole povere, è come se stessimo mescolando lentamente $\vert \psi_0 \rangle$, ma poiché è già completamente mescolato, non cambia nulla.

Ecco un altro esempio di vettore proprio di $M_a$. Questo, in particolare, risulta più interessante nel contesto della determinazione dell'ordine e della stima di fase.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

In alternativa, possiamo scrivere questo vettore utilizzando una sommatoria come segue.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

Qui vediamo che il numero complesso $\omega_r = e^{2\pi i/r}$ emerge spontaneamente, a causa del modo in cui funziona la moltiplicazione per $a$ modulo $N$. Questa volta l'autovalore corrispondente è $\omega_r$. Per verificarlo, possiamo innanzitutto effettuare i seguenti calcoli.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

Quindi, poiché $\omega_r^{-r} = 1 = \omega_r^0$ e $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle$, si ha che

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

quindi $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle$.

Seguendo lo stesso ragionamento, possiamo individuare ulteriori coppie di vettori propri e autovalori per $M_a$. Per qualsiasi scelta di $j\in\{0,\ldots,r-1\}$, si ha che

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

è un vettore proprio di $M_a$ il cui valore proprio corrispondente è $\omega_r^j$.

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

Esistono altri vettori propri di $M_a$, ma non è necessario occuparsene: ci concentreremo esclusivamente sui vettori propri $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ che abbiamo appena individuato.

---

Ricerca dell'ordine tramite stima di fase

Per risolvere il problema della ricerca dell’ordine per una data scelta di $a\in\mathbb{Z}_N^{\ast}$, possiamo applicare la procedura di stima di fase all’operazione $M_a$.

Per farlo, dobbiamo implementare in modo efficiente non solo $M_a$ con un circuito quantistico, ma anche $M_a^2$, $M_a^4$, $M_a^8$ e così via, spingendoci quanto necessario per ottenere una stima sufficientemente precisa dalla procedura di stima della fase. Qui spiegheremo come farlo e in seguito stabiliremo esattamente quale livello di precisione sia necessario.

Cominciamo con l'operazione " $M_a$ " di per sé. Naturalmente, dato che stiamo lavorando con il modello del circuito quantistico, useremo la notazione binaria per codificare i numeri compresi tra $0$ e $N-1$. Il numero più grande che dobbiamo codificare è $N-1$, quindi il numero di bit di cui abbiamo bisogno è

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

Ad esempio, se $N = 21$, abbiamo $n = \operatorname{lg}(N-1) = 5$. Ecco come si presenta la codifica degli elementi di $\mathbb{Z}_{21}$ come stringhe binarie di lunghezza $5$.

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

Ed ecco una definizione precisa di come $M_a$ sia definito come un'operazione $n$ -qubit.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

Il punto è che, sebbene ci interessi solo come funziona l’ $M_a$ e per $\vert 0\rangle,\ldots,\vert N-1\rangle$, dobbiamo comunque specificare come funziona per i restanti stati della base standard $2^n - N$ — e dobbiamo farlo in modo tale da ottenere comunque un’operazione unitaria. Ciò si ottiene definendo l’ $M_a$ e in modo tale che non abbia alcun effetto sugli stati rimanenti della base standard.

Utilizzando gli algoritmi per la moltiplicazione e la divisione di numeri interi illustrati nella lezione precedente, insieme alla metodologia per la loro implementazione reversibile e senza "garbage", possiamo costruire un circuito quantistico che esegua l'operazione " $M_a$ ", per qualsiasi scelta di " $a\in\mathbb{Z}_N^{\ast}$ ", con un costo pari a " $O(n^2)$ ". Ecco un modo per farlo.

1. Costruire un circuito per eseguire l'operazione

$$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

Dove

$$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

utilizzando il metodo descritto nella lezione precedente. Questo ci dà un circuito di dimensione $O(n^2)$.

2. Scambiare i due sistemi $n$ -qubit utilizzando le porte di scambio $n$ per scambiare i qubit individualmente.

3. In modo simile al primo passo, costruite un circuito per l'operazione

$$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

dove $a^{-1}$ è l'inverso di $a$ in $\mathbb{Z}_N^{\ast}$.

Inizializzando i qubit del fondo $n$ e componendo i tre passaggi, otteniamo questa trasformazione:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

Il metodo richiede qubit dello spazio di lavoro, ma questi vengono riportati al loro stato iniziale al termine del processo, il che ci permette di utilizzare questi circuiti per la stima di fase. Il costo totale del circuito che otteniamo è $O(n^2)$ o.

Per eseguire $M_a^2$, $M_a^4$, $M_a^8$ e così via, possiamo utilizzare esattamente lo stesso metodo, con la sola differenza di sostituire $a$ con $a^2$, $a^4$, $a^8$ e così via, come elementi di $\mathbb{Z}_N^{\ast}$. Cioè, per qualsiasi potenza $k$ scegliamo, possiamo creare un circuito per $M_a^k$ non iterando $k$ volte il circuito per $M_a$, ma invece calcolando $b = a^k \in \mathbb{Z}_N^{\ast}$ e poi utilizzando il circuito per $M_b$.

Il calcolo delle potenze $a^k \in \mathbb{Z}_N$ corrisponde al problema dell'esponenziazione modulare menzionato nella lezione precedente. Questo calcolo può essere effettuato in modo classico, utilizzando l'algoritmo per l'esponenziazione modulare menzionato nella lezione precedente (spesso denominato " algoritmo delle potenze" nella teoria computazionale dei numeri). Infatti, ci servono solo le potenze di power-of-2 relative a $a$, in particolare $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast}$, e possiamo ottenere queste potenze elevando al quadrato $m-1$ volte in modo iterativo. Ogni elevazione al quadrato può essere eseguita da un circuito booleano di dimensione $O(n^2)$.

In sostanza, ciò che stiamo effettivamente facendo qui è trasferire il problema di iterare su $M_a$ per un numero di volte pari a $2^{m-1}$ a un calcolo classico efficiente. Ed è una fortuna che ciò sia possibile! Se si sceglie un circuito quantistico a caso nel problema della stima di fase, è improbabile che ciò sia possibile — e in tal caso il costo risultante per la stima di fase cresce in modo esponenziale con il numero di qubit di controllo $m$.

Soluzione data un vettore proprio conveniente

Per capire come risolvere il problema della determinazione dell’ordine utilizzando la stima di fase, partiamo dal presupposto che si esegua la procedura di stima di fase sull’operazione $M_a$ utilizzando l’autovettore $\vert\psi_1\rangle$. Ottenere questo autovettore non è facile, a quanto pare, quindi la storia non finisce qui — ma è utile partire da qui.

L'autovalore di $M_a$ corrispondente all'autovettore $\vert \psi_1\rangle$ è

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

Cioè, $\omega_r = e^{2\pi i \theta}$ per $\theta = 1/r$. Quindi, se eseguiamo la procedura di stima di fase su $M_a$ utilizzando l’autovettore $\vert\psi_1\rangle$, otterremo un’approssimazione di $1/r$. Calcolando il reciproco saremo in grado di ricavare $r$ — a condizione che la nostra approssimazione sia sufficientemente accurata.

Più in dettaglio, quando eseguiamo la procedura di stima della fase utilizzando i qubit di controll $m$, otteniamo un numero $y\in\{0,\ldots,2^m-1\}$. Prendiamo quindi $y/2^m$ come valore stimato per $\theta$, che nel caso in esame è $1/r$. Per determinare il valore di $r$ a partire da questa approssimazione, la cosa più naturale da fare è calcolare il reciproco della nostra approssimazione e arrotondare al numero intero più vicino.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

Ad esempio, supponiamo che $r = 6$ e che si esegua la stima di fase su $M_a$ con il vettore proprio $\vert\psi_1\rangle$ utilizzando $m = 5$ bit di controllo. La migliore approssimazione a $5$ -bit di $1/r = 1/6$ è $5/32$, e abbiamo una probabilità piuttosto elevata (circa $68\%$ in questo caso) di ottenere il risultato $y=5$ dalla stima di fase. Abbiamo

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

e arrotondando al numero intero più vicino si ottiene $6$, che è la risposta corretta.

D'altra parte, se non utilizziamo una precisione sufficiente, potremmo non ottenere la risposta corretta. Ad esempio, se consideriamo un numero di qubit di controllo pari a $m = 4$ e nella stima di fase, potremmo ottenere la migliore approssimazione a $4$ bit di $1/r = 1/6$, ovvero $3/16$. Calcolando il reciproco si ottiene

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

e arrotondando al numero intero più vicino si ottiene un risultato errato pari a $5$.

Quindi, quanta precisione ci serve per ottenere la risposta giusta? Sappiamo che l'ordine $r$ è un numero intero e, intuitivamente, ciò di cui abbiamo bisogno è una precisione sufficiente per distinguere $1/r$ dalle possibilità vicine, tra cui $1/(r+1)$ e $1/(r-1)$. Il numero più vicino a $1/r$ di cui dobbiamo preoccuparci è $1/(r+1)$, e la distanza tra questi due numeri è

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

Quindi, se vogliamo assicurarci di non confondere $1/r$ con $1/(r+1)$, è sufficiente utilizzare una precisione tale da garantire che la migliore approssimazione $y/2^m$ di $1/r$ sia più vicina a $1/r$ che a $1/(r+1)$. Se utilizziamo una precisione tale che

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

in modo che l'errore sia inferiore alla metà della distanza tra $1/r$ e $1/(r+1)$; in tal caso, $y/2^m$ risulterà più vicino a $1/r$ che a qualsiasi altra possibilità, comprese $1/(r+1)$ e $1/(r-1)$.

Possiamo verificarlo come segue. Supponiamo che

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

per $\varepsilon$ che soddisfa

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

Prendendo il reciproco si ottiene

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

Massimizzando al numeratore e minimizzando al denominatore, possiamo stabilire quanto siamo lontani da $r$ come segue.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

Mancano meno di $1/2$ a $r$, quindi, come previsto, arrotondando otterremo $r$.

Sfortunatamente, poiché non sappiamo ancora cosa sia $r$, non possiamo usarlo per dirci di quanta precisione abbiamo bisogno. Si può invece utilizzare il fatto che $r$ deve essere più piccolo di $N$ per assicurarsi di utilizzare una precisione sufficiente. In particolare, se utilizziamo un'accuratezza sufficiente a garantire che la migliore approssimazione $y/2^m$ a $1/r$ soddisfi

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

allora avremo una precisione sufficiente per determinare correttamente $r$ quando prendiamo il reciproco. L'utilizzo di $m = 2\operatorname{lg}(N)+1$ garantisce un'alta probabilità di ottenere una stima con questa precisione con il metodo descritto in precedenza. (L'assunzione di $m = 2\operatorname{lg}(N)$ è sufficiente se ci sentiamo a nostro agio con un limite inferiore del 40% sulla probabilità di successo)

Soluzione generale

Come abbiamo appena visto, se disponiamo del vettore proprio $\vert \psi_1 \rangle$ di $M_a$, possiamo determinare $r$ tramite la stima di fase, a condizione di utilizzare un numero sufficiente di qubit di controllo per eseguire questa operazione con adeguata precisione. Purtroppo non è facile ottenere l'autovettore $\vert\psi_1\rangle$, quindi dobbiamo capire come procedere.

Supponiamo per un attimo di procedere esattamente come sopra, ma sostituendo l'autovettore $\vert\psi_k\rangle$ al posto di $\vert\psi_1\rangle$, per qualsiasi scelta di $k\in\{0,\ldots,r-1\}$ che decidiamo di prendere in considerazione. Il risultato che otterremo dalla procedura di stima di fase sarà un'approssimazione

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

Partendo dal presupposto che non conosciamo né $k$ né $r$, questo potrebbe permetterci o meno di identificare $r$. Ad esempio, se $k = 0$, otterremo un'approssimazione $y/2^m$ di $0$, che purtroppo non ci dice nulla. Si tratta, tuttavia, di un caso insolito; per altri valori di $k$, potremo almeno ricavare qualche informazione su $r$.

Possiamo utilizzare un algoritmo noto come algoritmo della frazione continua per trasformare la nostra approssimazione $y/2^m$ in frazioni vicine, inclusa $k/r$ se l'approssimazione è sufficientemente buona. Non spiegheremo qui l'algoritmo della frazione continua. Invece, ecco una dichiarazione di un fatto noto su questo algoritmo.

Dati un numero intero $N\geq 2$ e un numero reale $\alpha\in(0,1)$, esiste al massimo una scelta di numeri interi $u,v\in\{0,\ldots,N-1\}$ tali che $v\neq 0$ e $\gcd(u,v)=1$ soddisfino $\vert \alpha - u/v\vert < \frac{1}{2N^2}$. Dati $\alpha$ e $N$, l' algoritmo delle frazioni continue trova $u$ e $v$, oppure segnala che non esistono. Questo algoritmo può essere implementato come circuito booleano di dimensione $O((\operatorname{lg}(N))^3)$.

Se disponiamo di un'approssimazione molto vicina, $y/2^m$, a $k/r$, ed eseguiamo l'algoritmo delle frazioni continue per $N$ e $\alpha = y/2^m$, otterremo $u$ e $v$, come descritto nel fatto. Un'analisi dei fatti ci permette di concludere che

$$\frac{u}{v} = \frac{k}{r}.$$

Si noti in particolare che non si imparano necessariamente le espressioni “ $k$ ” e “ $r$ ”, ma solo “ $k/r$ ” nella forma più semplice.

Ad esempio, e come abbiamo già notato, non impareremo nulla da $k=0$. Ma questo è l'unico caso in cui ciò accade su $k$. Quando $k$ è diverso da zero, potrebbe avere fattori comuni con $r$, ma il numero $v$ che otteniamo dall’algoritmo delle frazioni continue deve almeno dividere $r$.

Non è affatto ovvio, ma è vero che se siamo in grado di imparare $u$ e $v$ per $u/v = k/r$ per $k\in\{0,\ldots,r-1\}$, scelti in modo uniformemente casuale, allora è molto probabile che riusciremo a recuperare $r$ già dopo pochi campioni. In particolare, se la nostra ipotesi per $r$ è il minimo comune multiplo di tutti i valori del denominatore $v$ che osserviamo, avremo ragione con elevata probabilità. Intuitivamente, alcuni valori di $k$ non sono validi perché hanno fattori comuni con $r$, e tali fattori comuni ci sfuggono quando analizziamo $u$ e $v$. Tuttavia, è improbabile che scelte casuali di $k$ riescano a nascondere a lungo i fattori di $r$, e la probabilità di non indovinare correttamente $r$ calcolando il minimo comune multiplo dei denominatori osservati diminuisce in modo esponenziale all’aumentare del numero di campioni.

Rimane da affrontare il problema di come mettere le mani su un autovettore $\vert\psi_k\rangle$ di $M_a$ su cui eseguire la procedura di stima della fase. In realtà non abbiamo bisogno di crearli!

Quello che faremo invece è applicare la procedura di stima di fase allo stato $\vert 1\rangle$, ovvero la codifica binaria a $n$ bit del numero $1$, al posto di un vettore proprio $\vert\psi\rangle$ di $M_a$. Finora abbiamo parlato solo di applicare la procedura di stima di fase a un particolare vettore proprio, ma nulla ci impedisce di applicare la procedura a uno stato di ingresso che non sia un vettore proprio di $M_a$, ed è proprio quello che stiamo facendo qui con lo stato $\vert 1\rangle$. (Questo non è un vettore proprio di $M_a$ a meno che $a=1$, il che non è un caso che ci interessa.)

La ragione per cui si sceglie lo stato $\vert 1\rangle$ al posto di un autovettore di $M_a$ è che la seguente equazione è vera.

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

Un modo per verificare questa equazione è quello di confrontare i prodotti interni dei due lati con ogni stato base standard, utilizzando le formule menzionate in precedenza nella lezione per aiutare a valutare i risultati per il lato destro. Di conseguenza, otterremo esattamente gli stessi risultati di misurazione che avremmo ottenuto se avessimo scelto $k\in\{0,\ldots,r-1\}$ in modo uniformemente casuale e utilizzato $\vert\psi_k\rangle$ come autovalore.

Più in dettaglio, immaginiamo di eseguire la procedura di stima di fase utilizzando lo stato $\vert 1\rangle$ al posto di uno degli autovettori $\vert\psi_k\rangle$. Una volta eseguita la trasformata di Fourier quantistica inversa, otteniamo lo stato

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

Dove

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle.$$

Il vettore $\vert\gamma_k\rangle$ rappresenta lo stato dei qubit top $m$ dopo che su di essi è stata eseguita l'inversa della trasformata quantistica di Fourier.

Quindi, in virtù del fatto che $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ è un insieme ortonormale, troviamo che una misura dei qubit superiori $m$ produce un'approssimazione al valore dove è scelto in modo uniforme e casuale produce un'approssimazione $y/2^m$ al valore $k/r$ dove $k\in\{0,\ldots,r-1\}$ è scelto uniformemente a caso. Come abbiamo già detto, questo ci permette di imparare $r$ con un alto grado di confidenza dopo diverse esecuzioni indipendenti, che era il nostro obiettivo.

Costo totale

Il costo per l'implementazione di ogni operazione unitaria controllata $M_a^k$ è pari a $O(n^2)$. Le operazioni unitarie controllate sono $m$ e abbiamo $m = O(n)$, quindi il costo totale delle operazioni unitarie controllate è pari a $O(n^3)$. Inoltre, abbiamo $m$ porte di Hadamard (che contribuiscono al costo con $O(n)$ ) e la trasformata di Fourier quantistica inversa contribuisce al costo con $O(n^2)$. Pertanto, il costo delle operazioni unitarie controllate incide in modo determinante sul costo dell’intera procedura — che risulta quindi pari a $O(n^3)$.

Oltre al circuito quantistico vero e proprio, ci sono alcuni calcoli classici che devono essere eseguiti nel corso del processo. Ciò comprende il calcolo delle potenze $a^k$ in $\mathbb{Z}_N$ per $k = 2, 4, 8, \ldots, 2^{m-1}$, necessarie per creare i gate unitari controllati, nonché l’algoritmo delle frazioni continue che converte le approssimazioni di $\theta$ in frazioni. Questi calcoli possono essere eseguiti da circuiti booleani con un costo totale pari a $O(n^3)$.

Come è tipico, tutti questi limiti possono essere migliorati utilizzando algoritmi asintoticamente veloci; questi limiti presuppongono l'utilizzo di algoritmi standard per le operazioni aritmetiche di base.

---

Factoring su ordine trovato

L'ultima cosa da discutere è il modo in cui la soluzione del problema della ricerca dell'ordine ci aiuta a fattorizzare. Questa parte è completamente classica e non ha nulla a che fare con l'informatica quantistica.

Ecco l'idea di base. Vogliamo fattorizzare il numero $N$, e possiamo farlo in modo ricorsivo. Nello specifico, possiamo concentrarci sul compito di scomporre $N$, il che significa trovare due numeri interi qualsiasi $b,c\geq 2$ tali che $N = bc$. Ciò non è possibile se $N$ è un numero primo, ma possiamo prima verificare in modo efficiente se $N$ è primo utilizzando un algoritmo di verifica della primalità e, se $N$ non è primo, proveremo a scomporlo. Una volta scomposto $N$, possiamo semplicemente applicare la ricorsione su $b$ e $c$ fino a quando tutti i nostri fattori non saranno primi e otterremo la scomposizione in fattori primi di $N$.

Dividere i numeri interi pari è facile: basta stampare $2$ e $N/2$.

È anche facile scomporre potenze perfette, ovvero numeri della forma $N = s^j$ per interi $s,j\geq 2$, semplicemente approssimando le radici $N^{1/2}$, $N^{1/3}$, $N^{1/4}$ e così via, e verificando gli interi vicini come possibili candidati per $s$. Non è necessario andare oltre i $\log(N)$ passi di questa sequenza, poiché a quel punto la radice scende al di sotto di $2$ e non rivelerà ulteriori candidati.

È positivo che possiamo fare entrambe le cose, perché la ricerca dell’ordine non ci aiuterà a scomporre i numeri pari né nel caso delle potenze di numeri primi, dove il numero $s$ risulta essere primo. Se però $N$ è dispari e non è una potenza di un numero primo, la determinazione dell’ordine ci permette di scomporre $N$.

1. Scegli a caso $a\in\{2,\ldots,N-1\}$.

2. Calcola $d=\gcd(a,N)$.

3. Se $d > 1$, allora visualizza $b = d$ e $c = N/d$ e termina. Altrimenti, passa alla fase successiva sapendo che $a\in\mathbb{Z}_N^{\ast}$.

4. Sia $r$ l'ordine di $a$ modulo $N$. (È qui che ci serve la ricerca degli ordini.)

5. Se $r$ è pari:

   5.1 Calcola$x = a^{r/2} - 1$ modulo$N$

   5.2
   Calcola$d = \gcd(x,N)$ . 5.3
   Se$d>1$ , allora stampa$b=d$ e$c = N/d$ e termina.

6. Se si giunge a questo punto, significa che l’algoritmo non è riuscito a trovare un fattore di $N$.

L'esecuzione di questo algoritmo potrebbe non riuscire a trovare un fattore di $N$. Nello specifico, ciò accade in due casi:

• L'ordine di $a$ modulo $N$ è dispari.
• L'ordine di $a$ modulo $N$ è pari e $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1$.

Ricorrendo alla teoria elementare dei numeri, si può dimostrare che, per una scelta casuale di un numero $a$, con probabilità almeno pari a $1/2$ nessuno dei due eventi si verifica. Infatti, la probabilità che si verifichi uno dei due eventi è al massimo pari a $2^{-(m-1)}$, dove $m$ è il numero di fattori primi distinti di $N$, motivo per cui è necessaria l’ipotesi che $N$ non sia una potenza di un numero primo. (Affinché questo fatto sia vero, è necessario anche che $N$ sia dispari.)

Ciò significa che ogni esecuzione ha almeno il 50% di probabilità di suddividere $N$. Pertanto, se eseguiamo l'algoritmo $t$ volte, scegliendo casualmente $a$ ogni volta, riusciremo a suddividere $N$ con una probabilità di almeno $1 - 2^{-t}$.

L'idea di base dell'algoritmo è la seguente. Se abbiamo una scelta di $a$ per la quale l'ordine $r$ di $a$ modulo $N$ è pari, allora $r/2$ è un intero e possiamo considerare i numeri

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

Utilizzando la formula $Z^2 - 1 = (Z+1)(Z-1)$, si deduce che

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

Ora, sappiamo che $a^r \; (\textrm{mod}\; N) = 1$ per definizione dell’ordine — il che equivale a dire che $N$ divide esattamente $a^r - 1$. Ciò significa che $N$ divide esattamente il prodotto

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

Perché questo sia vero, tutti i fattori primi di $N$ devono essere anche fattori primi di $a^{r/2} - 1$ o $a^{r/2} + 1$ (o di entrambi) - e per una selezione casuale di $a$ risulta improbabile che tutti i fattori primi di $N$ dividano uno dei termini e nessuno divida l'altro. Altrimenti, se alcuni dei fattori primi di $N$ dividono il primo termine e alcuni dividono il secondo termine, saremo in grado di trovare un fattore non banale di $N$ calcolando il GCD con il primo termine.