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 intero positivo $N,$ definiamo l'insieme $\mathbb{Z}_N$ in questo modo.

$$\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 più che insiemi. In particolare, possiamo pensare a operazioni aritmetiche su $\mathbb{Z}_N$ come l'addizione e la moltiplicazione - e se accettiamo di prendere sempre le nostre risposte modulo $N$ (cioè dividere per $N$ e prendere il resto come risultato), rimarremo sempre all'interno di questo insieme quando eseguiamo queste operazioni. Le due operazioni specifiche di addizione e moltiplicazione, entrambe prese modulo $N,$ trasformano $\mathbb{Z}_N$ in un anello, che è un tipo di oggetto di fondamentale importanza in algebra.

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

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

Ma possiamo anche scrivere semplicemente $3 \cdot 5 = 1,$, purché sia chiaro che stiamo lavorando in $\mathbb{Z}_7,$, per mantenere la notazione più semplice possibile.

A titolo di esempio, ecco le tabelle di addizione e moltiplicazione di $\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 $N$ elementi di $\mathbb{Z}_N,$ sono speciali gli elementi $a\in\mathbb{Z}_N$ che soddisfano $\gcd(a,N) = 1$. Spesso l'insieme che contiene questi elementi viene indicato con una stella, come in questo caso.

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

Se concentriamo la nostra attenzione sull'operazione di moltiplicazione, l'insieme $\mathbb{Z}_N^{\ast}$ forma un gruppo - in particolare un gruppo abeliano - che è un altro importante tipo di oggetto in algebra. È un fatto fondamentale di questi insiemi (e dei gruppi finiti in generale), che se scegliamo un elemento qualsiasi $a\in\mathbb{Z}_N^{\ast}$ e moltiplichiamo ripetutamente $a$ a se stesso, alla fine otterremo sempre il numero $1.$

Per un primo esempio, prendiamo $N=6.$ Abbiamo che $5\in\mathbb{Z}_6^{\ast}$ perché $\gcd(5,6) = 1,$ e se moltiplichiamo $5$ a se stesso otteniamo $1,$ come conferma la tabella precedente.

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

Come secondo esempio, prendiamo $N = 21.$ Se scorriamo i numeri da $0$ a $20,$ quelli che hanno GCD uguale 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 il numero a una potenza intera positiva per ottenere $1.$ Ecco le potenze più piccole per le quali funziona:

$$\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, in termini di notazione appena introdotta sopra, ci viene dato $a \in \mathbb{Z}_N^{\ast},$ e stiamo cercando il più piccolo intero positivo $r$ tale che $a^r = 1.$ Questo numero $r$ è chiamato ordine di $a$ modulo $N.$

Per collegare il problema dell'order-finding alla stima della fase, pensiamo all'operazione definita su un sistema i cui stati classici corrispondono a $\mathbb{Z}_N,$ dove moltiplichiamo 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 essere chiari, stiamo facendo la moltiplicazione in $\mathbb{Z}_N,$, quindi è implicito che stiamo prendendo il prodotto modulo $N$ all'interno del ket sul lato destro dell'equazione.

Ad esempio, se prendiamo $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 a condizione che $\gcd(a,N)=1;$ rimescoli gli elementi della base standard $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ quindi come matrice è una matrice di permutazione. È evidente dalla sua definizione che questa operazione è deterministica e un modo semplice per vedere che è invertibile è pensare all'ordine $r$ di $a$ modulo $N,$ e 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 pensare all'inverso che non richiede alcuna conoscenza di $r$ (che, dopo tutto, è ciò che stiamo cercando di calcolare). Per ogni elemento $a\in\mathbb{Z}_N^{\ast}$ c'è sempre un unico elemento $b\in\mathbb{Z}_N^{\ast}$ che soddisfa $ab=1.$ Questo elemento $b$ viene indicato con $a^{-1},$ e può essere calcolato in modo efficiente; un'estensione dell'algoritmo GCD di Euclide 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.

Ora pensiamo agli autovettori e agli autovalori dell'operazione $M_a,$ assumendo che $a\in\mathbb{Z}_N^{\ast}.$ Come appena argomentato, questa ipotesi ci dice che $M_a$ è unitario.

Ci sono $N$ autovalori di $M_a,$ che possono includere lo stesso autovalore ripetuto più volte, e in generale c'è una certa libertà nella selezione degli autovalori corrispondenti - ma non dovremo preoccuparci di tutte le possibilità. Iniziamo in modo semplice e identifichiamo un solo autovettore 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 nel resto della lezione. L'autovalore associato a questo autovalore è $1$ perché non viene modificato quando si moltiplica 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$$

Questo accade perché $a^r = 1,$ quindi ogni stato base standard $\vert a^k \rangle$ viene spostato a $\vert a^{k+1} \rangle$ per $k\leq r-1,$ e $\vert a^{r-1} \rangle$ viene spostato di nuovo a $\vert 1\rangle.$ In termini informali, è come se stessimo mescolando lentamente $\vert \psi_0 \rangle,$ ma è già completamente mescolato, quindi non cambia nulla.

Ecco un altro esempio di autovettore di $M_a.$ Questo è più interessante nel contesto della ricerca dell'ordine e della stima della 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$$

In questo caso il numero complesso $\omega_r = e^{2\pi i/r}$ appare naturalmente, grazie al modo in cui la moltiplicazione per $a$ funziona modulo $N.$ Questa volta l'autovalore corrispondente è $\omega_r.$ Per vedere questo, possiamo prima calcolare come segue.

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

Allora, poiché $\omega_r^{-r} = 1 = \omega_r^0$ e $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle,$ vediamo 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,$$

così $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle.$

Utilizzando lo stesso ragionamento, possiamo identificare ulteriori coppie autovettore/autovalore 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 autovettore di $M_a$ il cui autovalore corrispondente è $\omega_r^j.$

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

Esistono altri autovettori di $M_a,$, ma non è il caso di occuparsene: ci concentreremo solo sugli autovettori $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ che abbiamo appena identificato.

---

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 della fase all'operazione $M_a.$

Per fare ciò, dobbiamo implementare in modo efficiente con un circuito quantistico non solo $M_a$, ma anche $M_a^2,$ $M_a^4,$ $M_a^8,$ e così via, spingendoci fino a dove è necessario per ottenere una stima sufficientemente precisa dalla procedura di stima della fase. Qui spiegheremo come si può fare e in seguito capiremo esattamente quanta precisione è necessaria.

Cominciamo con l'operazione $M_a$ da sola. Naturalmente, poiché stiamo lavorando con il modello dei circuiti quantistici, 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 necessari è

$$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 appare 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 il funzionamento di $M_a$ per $\vert 0\rangle,\ldots,\vert N-1\rangle,$, dobbiamo specificare come funziona per i restanti stati base standard di $2^n - N$ - e dobbiamo farlo in modo da ottenere un'operazione unitaria. Definendo $M_a$ in modo che non influisca sugli altri stati base standard, si ottiene questo risultato.

Utilizzando gli algoritmi per la moltiplicazione e la divisione di interi discussi nella lezione precedente, insieme alla metodologia per le loro implementazioni reversibili e prive di spazzatura, possiamo costruire un circuito quantistico che esegua $M_a,$ per qualsiasi scelta di $a\in\mathbb{Z}_N^{\ast},$ al costo $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. Si ottiene così un circuito di dimensioni $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 i qubit dello spazio di lavoro, ma alla fine vengono riportati allo stato inizializzato, il che ci permette di usare questi circuiti per la stima della fase. Il costo totale del circuito che otteniamo è $O(n^2).$

Per eseguire $M_a^2,$ $M_a^4,$ $M_a^8,$ e così via, possiamo usare esattamente lo stesso metodo, tranne che per il fatto che sostituiamo $a$ con $a^2,$ $a^4,$ $a^8,$ e così via, come elementi di $\mathbb{Z}_N^{\ast}.$ Cioè, per qualsiasi potenza $k$ che scegliamo, possiamo creare un circuito per $M_a^k$ non iterando $k$ per il circuito per $M_a,$, ma 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$ è il problema dell' esponenziazione modulare menzionato nella lezione precedente. Questo calcolo può essere eseguito in modo classico, utilizzando l'algoritmo per l'esponenziazione modulare citato nella lezione precedente (spesso chiamato algoritmo della potenza nella teoria dei numeri computazionali). In effetti, è necessario solo power-of-2 potenze di $a,$ in particolare $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast},$ e possiamo ottenere queste potenze con una quadratura iterativa di $m-1$ volte. Ogni quadratura può essere eseguita da un circuito booleano di dimensione $O(n^2).$

In sostanza, stiamo scaricando il problema dell'iterazione di $M_a$ fino a $2^{m-1}$ volte su un calcolo classico efficiente. Ed è una fortuna che questo sia possibile! Per una scelta arbitraria di un circuito quantistico nel problema della stima di fase, questo non è probabilmente possibile - e in tal caso il costo risultante per la stima di fase cresce esponenzialmente nel numero di qubit di controllo $m.$

Soluzione data un vettore proprio conveniente

Per capire come si può risolvere il problema dell'order-finding utilizzando la stima di fase, iniziamo supponendo che eseguiamo la procedura di stima della fase sull'operazione $M_a$ utilizzando l'autovettore $\vert\psi_1\rangle.$ Mettere le mani su questo autovettore non è facile, quindi la storia non finisce qui, ma è utile iniziare 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 della fase su $M_a$ utilizzando l'autovalore $\vert\psi_1\rangle,$ otterremo un'approssimazione a $1/r.$ Calcolando il reciproco saremo in grado di imparare $r$ - a patto che la nostra approssimazione sia sufficientemente buona.

Più in dettaglio, quando si esegue la procedura di stima della fase utilizzando i qubit di controllo di $m$, si ottiene un numero $y\in\{0,\ldots,2^m-1\}.$ Prendiamo quindi $y/2^m$ come ipotesi per $\theta,$, che nel caso in esame è $1/r$. Per capire qual è $r$ 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$ ed eseguiamo la stima di fase su $M_a$ con l'autovettore $\vert\psi_1\rangle$ utilizzando i bit di controllo di $m = 5$. La migliore approssimazione $5$ -bit a $1/r = 1/6$ è $5/32,$ e abbiamo una buona probabilità (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 usiamo abbastanza precisione, potremmo non ottenere la risposta giusta. Per esempio, se prendiamo $m = 4$ qubit di controllo nella stima della fase, potremmo ottenere la migliore approssimazione di $4$ -bit a $1/r = 1/6,$ che è $3/16.$ Prendendo il reciproco si ottiene

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

e arrotondando al numero intero più vicino si ottiene una risposta errata di $5.$

Di quanta precisione abbiamo bisogno 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 essere sicuri di non confondere $1/r$ con $1/(r+1),$, è sufficiente utilizzare una precisione sufficiente a garantire che una migliore approssimazione tra $y/2^m$ e $1/r$ sia più vicina a $1/r$ di quanto non lo sia a $1/(r+1).$ Se usiamo una precisione tale da garantire 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),$ allora $y/2^m$ sarà 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}$$

Siamo a meno di $1/2$ da $r,$ quindi, come previsto, otterremo $r$ quando arrotonderemo.

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 dell'autovettore $\vert \psi_1 \rangle$ di $M_a,$ possiamo imparare $r$ attraverso la stima di fase, a patto di utilizzare un numero di qubit di controllo sufficiente per farlo con sufficiente precisione. Purtroppo non è facile mettere le mani sull'autovettore $\vert\psi_1\rangle,$ e quindi dobbiamo capire come procedere.

Supponiamo momentaneamente di procedere come sopra, ma con 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 pensare. Il risultato che si ottiene dalla procedura di stima della fase sarà un'approssimazione

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

Partendo dal presupposto che non conosciamo né $k$ né $r,$, questo potrebbe o meno permetterci di identificare $r.$ Ad esempio, se $k = 0$ otteniamo un'approssimazione da $y/2^m$ a $0,$ che purtroppo non ci dice nulla. Questo, tuttavia, è un caso insolito; per altri valori di $k,$ saremo almeno in grado di imparare qualcosa 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.

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

Se abbiamo un'approssimazione molto stretta di $y/2^m$ a $k/r,$ ed eseguiamo l'algoritmo della frazione continua per $N$ e $\alpha = y/2^m,$ otterremo $u$ e $v,$ come sono descritti nel fatto. L'analisi del fatto ci permette di concludere che

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

Si noti in particolare che non impariamo necessariamente $k$ e $r,$ ma solo $k/r$ nei termini più bassi.

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

È tutt'altro che ovvio, ma è vero che se abbiamo la capacità di imparare $u$ e $v$ per $u/v = k/r$ per $k\in\{0,\ldots,r-1\}$ scelti uniformemente a caso, allora è molto probabile che siamo in grado di recuperare $r$ dopo pochi campioni. In particolare, se la nostra ipotesi per $r$ è il multiplo meno comune di tutti i valori del denominatore $v$ che osserviamo, avremo ragione con alta probabilità. Intuitivamente, alcuni valori di $k$ non vanno bene perché condividono fattori comuni con $r,$ e questi fattori comuni ci vengono nascosti quando impariamo a conoscere $u$ e $v.$ Ma le scelte casuali di $k$ non possono nascondere a lungo i fattori di $r$ e la probabilità di non indovinare $r$ correttamente prendendo il minimo comune multiplo dei denominatori osservati diminuisce esponenzialmente con il 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!

Si eseguirà invece la procedura di stima della fase sullo stato $\vert 1\rangle,$, intendendo con questo termine la codifica binaria a $n$ bit del numero $1,$ al posto di un autovettore $\vert\psi\rangle$ di $M_a.$ Finora abbiamo parlato solo di eseguire la procedura di stima della fase su un particolare autovettore, ma nulla ci impedisce di eseguire la procedura su uno stato di ingresso che non sia un autovettore di $M_a,$ ed è quello che stiamo facendo qui con lo stato $\vert 1\rangle.$ (Questo non è un autovettore di $M_a$, a meno che $a=1,$ non sia una scelta 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.

In dettaglio, immaginiamo di eseguire la procedura di stima della fase con lo stato $\vert 1\rangle$ al posto di uno degli autovettori $\vert\psi_k\rangle.$ Dopo aver eseguito la trasformata quantistica inversa di Fourier, si ottiene 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 controllata-unitaria $M_a^k$ è $O(n^2).$ Ci sono $m$ operazioni controllate-unitarie, e abbiamo $m = O(n),$ quindi il costo totale per le operazioni controllate-unitarie è $O(n^3).$ Inoltre, abbiamo $m$ porte di Hadamard (che contribuiscono $O(n)$ al costo) e la trasformata quantistica di Fourier inversa contribuisce $O(n^2)$ al costo. In questo modo, il costo delle operazioni controllate-unitarie domina il costo dell'intera procedura - che quindi è $O(n^3).$

Oltre al circuito quantistico stesso, ci sono alcuni calcoli classici che devono essere eseguiti lungo il percorso. Questo include il calcolo delle potenze $a^k$ in $\mathbb{Z}_N$ per $k = 2, 4, 8, \ldots, 2^{m-1},$, necessarie per creare le porte unitarie controllate, nonché l'algoritmo della frazione continua che converte le approssimazioni di $\theta$ in frazioni. Queste computazioni possono essere eseguite da circuiti booleani con un costo totale di $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. In particolare, possiamo concentrarci sul compito di dividere $N,$, che significa trovare due interi $b,c\geq 2$ per i quali è un numero primo $N = bc.$ Questo non è possibile se $N$ è un numero primo, ma possiamo verificare in modo efficiente se $N$ è primo usando prima un algoritmo di verifica della primalità, e se $N$ non è primo proveremo a dividerlo. Una volta diviso $N,$ possiamo semplicemente ricorreggere su $b$ e $c$ fino a quando tutti i nostri fattori sono primi e otteniamo la fattorizzazione prima di $N.$

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

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

È bene poter fare entrambe le cose, perché la ricerca dell'ordine non ci aiuterà a fattorizzare i numeri pari o le potenze prime, dove il numero $s$ è un numero primo. Se $N$ è dispari e non è una potenza prima, tuttavia, la ricerca dell'ordine ci permette di dividere $N.$

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

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

3. Se $d > 1$, allora emette $b = d$ e $c = N/d$ e si ferma. Altrimenti, proseguire con il passo successivo sapendo che $a\in\mathbb{Z}_N^{\ast}.$

4. Sia $r$ l'ordine di $a$ modulo $N.$ (qui è necessario trovare un ordine)

5. Se $r$ è pari:

   5.1 Calcolo di $x = a^{r/2} - 1$ modulo $N$ \ 5.2 Calcolare $d = \gcd(x,N).$ \ 5.3 Se $d>1$, allora produce $b=d$ e $c = N/d$ e si ferma.

6. Se si raggiunge questo punto, l'algoritmo non è riuscito a trovare un fattore di $N.$

Un'esecuzione di questo algoritmo può fallire nel trovare un fattore di $N.$ In particolare, ciò accade in due situazioni:

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

Utilizzando la teoria dei numeri di base si può dimostrare che, per una scelta casuale di $a,$ con probabilità almeno $1/2$, nessuno di questi eventi si verifica. Infatti, la probabilità che si verifichi uno dei due eventi è al massimo $2^{-(m-1)}$ per $m$ che è il numero di fattori primi distinti di $N,$ ed è per questo che è necessaria l'ipotesi che $N$ non sia una potenza prima. (Perché questo fatto sia vero è necessaria anche l'ipotesi che $N$ sia dispari)

Ciò significa che ogni esecuzione ha almeno il 50% di probabilità di dividere $N.$ Pertanto, se eseguiamo l'algoritmo $t$ volte, scegliendo casualmente $a$ ogni volta, riusciremo a dividere $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 conclude 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 la definizione di ordine - che è un altro modo di dire che $N$ divide uniformemente $a^r - 1.$ Ciò significa che $N$ divide uniformemente 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.