L'algoritmo di Shor

Ora rivolgeremo la nostra attenzione al problema della fattorizzazione intera, 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 intera. Shor non ha descritto il suo algoritmo specificamente in termini di stima di fase, ma è un modo naturale e intuitivo per spiegare come funziona.

Inizieremo discutendo un problema intermedio noto come il problema di ricerca dell'ordine e vedremo come la stima di fase fornisce una soluzione a questo problema. Vedremo poi come una soluzione efficiente al problema di ricerca dell'ordine ci fornisce una soluzione efficiente al problema della fattorizzazione intera. (Quando la soluzione a un problema fornisce una soluzione a un altro problema in questo modo, diciamo che il secondo problema si riduce al primo — quindi in questo caso stiamo riducendo la fattorizzazione intera alla ricerca dell'ordine.) Questa seconda parte dell'algoritmo di Shor non fa uso del calcolo quantistico; è completamente classica. Il calcolo quantistico è necessario solo per risolvere la ricerca dell'ordine.

Il problema di ricerca dell'ordine

Alcuni concetti base di teoria dei numeri

Per spiegare il problema di ricerca dell'ordine e come può essere risolto usando la stima di fase, sarà utile iniziare con un paio di concetti fondamentali di teoria dei numeri, e introdurre alcune notazioni pratiche lungo il percorso.

Per cominciare, per ogni intero positivo $N,$ definiamo l'insieme $\mathbb{Z}_N$ come segue.

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

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

Questi sono insiemi di numeri, ma possiamo pensarli come qualcosa di più di semplici insiemi. In particolare, possiamo pensare alle operazioni aritmetiche su $\mathbb{Z}_N$ come l'addizione e la moltiplicazione — e se concordiamo di prendere sempre i risultati modulo $N$ (cioè, dividiamo per $N$ e prendiamo 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 fondamentalmente importante in algebra.

Ad esempio, $3$ e $5$ sono elementi di $\mathbb{Z}_7,$ e se li moltiplichiamo otteniamo $3\cdot 5 = 15,$ che lascia un resto di $1$ quando diviso per $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,$ solo per mantenere la notazione il più semplice possibile.

Come esempio, ecco le tavole di addizione e 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 $N$ elementi di $\mathbb{Z}_N,$ gli elementi $a\in\mathbb{Z}_N$ che soddisfano $\gcd(a,N) = 1$ sono speciali. Spesso l'insieme contenente questi elementi è denotato con un asterisco come segue.

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

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

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

$$5^2 = 1 \quad \text{(lavorando all'interno di $\mathbb{Z}_6$)}$$

Come secondo esempio, prendiamo $N = 21.$ Se passiamo in rassegna i numeri da $0$ a $20,$ quelli con MCD 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 quel numero a una potenza intera positiva per ottenere $1.$ Ecco le potenze più piccole per cui questo 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 stiamo lavorando all'interno di $\mathbb{Z}_{21}$ per tutte queste equazioni, cosa che non abbiamo scritto — la consideriamo implicita per evitare di appesantire la notazione. Continueremo a farlo nel resto della lezione.

Enunciato del problema e connessione con la stima di fase

Ora possiamo enunciare il problema di ricerca dell'ordine.

Ricerca dell'ordine

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

In alternativa, in termini della notazione appena introdotta, ci vengono dati $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 di ricerca dell'ordine alla stima di 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{(per ogni $x\in\mathbb{Z}_N$)}$$

Per essere chiari, stiamo eseguendo 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,$ allora 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}$$

Questa è un'operazione unitaria purché $\gcd(a,N)=1;$ permuta 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 per pensare all'inverso che non richiede alcuna conoscenza di $r$ (che, dopotutto, è 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.$ Denotiamo questo elemento $b$ con $a^{-1},$ e può essere calcolato in modo efficiente; un'estensione dell'algoritmo di Euclide per il MCD lo fa con 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 è descritta da una matrice di permutazione, ed è quindi unitaria.

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

Ci sono $N$ autovalori di $M_a,$ eventualmente includendo lo stesso autovalore ripetuto più volte, e in generale c'è una certa libertà nella scelta degli autovettori corrispondenti — ma non avremo bisogno di preoccuparci di tutte le possibilità. Iniziamo semplicemente identificando 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 autovettore è $1$ perché non viene modificato quando 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$$

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

Ecco un altro esempio di autovettore di $M_a.$ Questo è più interessante nel contesto della ricerca 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 usando 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 il numero complesso $\omega_r = e^{2\pi i/r}$ apparire naturalmente, a causa del modo in cui la moltiplicazione per $a$ funziona modulo $N.$ Questa volta l'autovalore corrispondente è $\omega_r.$ Per verificarlo, 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$$

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

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

Usando lo stesso ragionamento, possiamo identificare ulteriori coppie autovettore/autovalore per $M_a.$ Per qualsiasi scelta di $j\in\{0,\ldots,r-1\}$ abbiamo 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$$

Ci sono altri autovettori di $M_a,$ ma non dobbiamo preoccuparcene — ci concentreremo esclusivamente sugli autovettori $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ che abbiamo appena identificato.

Trovare l'ordine tramite la 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 con un circuito quantistico non solo $M_a,$ 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 di fase. Qui spiegheremo come questo può essere fatto, e capiremo esattamente quanta precisione è necessaria in seguito.

Cominciamo con l'operazione $M_a$ da sola. Naturalmente, poiché lavoriamo con il modello del circuito quantistico, utilizzeremo 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.$$

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

E ora, ecco una definizione precisa di come $M_a$ è definita come operazione su $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 comunque specificare come si comporta per i restanti $2^n - N$ stati della base standard — e dobbiamo farlo in modo da ottenere comunque un'operazione unitaria. Definire $M_a$ in modo che non faccia nulla sui restanti stati della base standard raggiunge questo obiettivo.

Usando gli algoritmi per la moltiplicazione e la divisione di interi discussi nella lezione precedente, insieme alla metodologia per implementazioni reversibili e senza spazzatura, possiamo costruire un circuito quantistico che esegue $M_a,$ per qualsiasi scelta di $a\in\mathbb{Z}_N^{\ast},$ con costo $O(n^2).$ Ecco un modo in cui questo può essere fatto.

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

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

2. Scambiare i due sistemi da $n$ qubit usando $n$ swap gate per scambiare i qubit individualmente.

3. In modo analogo al primo passo, costruire 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 gli $n$ qubit inferiori e componendo i tre passi, 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 di lavoro, ma vengono riportati al loro stato inizializzato alla fine, il che ci permette di usare questi circuiti per la stima di fase. Il costo totale del circuito ottenuto è $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 sostituiamo $a$ con $a^2,$ $a^4,$ $a^8,$ e così via, come elementi di $\mathbb{Z}_N^{\ast}.$ In altre parole, 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 usando 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 classicamente, usando l'algoritmo per l'esponenziazione modulare menzionato nella lezione precedente (spesso chiamato algoritmo della potenza in teoria computazionale dei numeri). In realtà, richiediamo solo potenze di $a$ che siano potenze di 2, in particolare $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast},$ e possiamo ottenere queste potenze elevando iterativamente al quadrato $m-1$ volte. Ogni elevamento al quadrato può essere eseguito da un circuito booleano di dimensione $O(n^2).$

In sostanza, quello che stiamo effettivamente facendo qui è delegare il problema di iterare $M_a$ fino a $2^{m-1}$ volte a un efficiente calcolo classico. Ed è una fortuna che questo sia possibile! Per una scelta arbitraria di un circuito quantistico nel problema della stima di fase, questo probabilmente non sarà possibile — e in quel caso il costo risultante per la stima di fase cresce esponenzialmente nel numero di qubit di controllo $m.$

Soluzione dato un autovettore conveniente

Per capire come possiamo risolvere il problema della ricerca dell'ordine usando la stima di fase, cominciamo supponendo che eseguiamo la procedura di stima di fase sull'operazione $M_a$ usando l'autovettore $\vert\psi_1\rangle.$ Ottenere questo autovettore non è facile, come si vedrà, quindi questa non sarà la fine della storia — 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}}.$$

Ovvero, $\omega_r = e^{2\pi i \theta}$ con $\theta = 1/r.$ Quindi, se eseguiamo la procedura di stima di fase su $M_a$ usando l'autovettore $\vert\psi_1\rangle,$ otterremo un'approssimazione di $1/r.$ Calcolando il reciproco saremo in grado di apprendere $r$ — a condizione che la nostra approssimazione sia sufficientemente buona.

Più in dettaglio, quando eseguiamo la procedura di stima di fase usando $m$ qubit di controllo, quello che otteniamo è un numero $y\in\{0,\ldots,2^m-1\}.$ Prendiamo poi $y/2^m$ come stima per $\theta,$ che nel caso in esame è $1/r.$ Per capire qual è $r$ da questa approssimazione, la cosa naturale da fare è calcolare il reciproco della nostra approssimazione e arrotondare all'intero più vicino.

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

Per esempio, supponiamo che $r = 6$ e che eseguiamo la stima di fase su $M_a$ con l'autovettore $\vert\psi_1\rangle$ usando $m = 5$ bit di controllo. La migliore approssimazione a $5$ bit di $1/r = 1/6$ è $5/32,$ e abbiamo una buona probabilità (circa il $68\%$ in questo caso) di ottenere l'esito $y=5$ dalla stima di fase. Abbiamo

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

e arrotondando all'intero più vicino otteniamo $6,$ che è la risposta corretta.

D'altra parte, se non usiamo una precisione sufficiente, potremmo non ottenere la risposta giusta. Per esempio, se prendiamo $m = 4$ qubit di controllo nella stima di fase, potremmo ottenere la migliore approssimazione a $4$ bit di $1/r = 1/6,$ che è $3/16.$ Prendendo il reciproco si ottiene

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

e arrotondando all'intero più vicino si ottiene una risposta errata di $5.$

Quindi quanta precisione ci serve per ottenere la risposta giusta? Sappiamo che l'ordine $r$ è un intero, e intuitivamente quello di cui abbiamo bisogno è una precisione sufficiente per distinguere $1/r$ dalle possibilità vicine, incluse $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 scambiare $1/r$ per $1/(r+1),$ è sufficiente usare una precisione tale da garantire che la migliore approssimazione $y/2^m$ a $1/r$ sia più vicina a $1/r$ che 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)},$$

cosicché 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à, incluse $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)}.$$

Quando prendiamo il reciproco otteniamo

$$\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 limitare 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 arrotondiamo.

Purtroppo, poiché non sappiamo ancora cosa sia $r,$ non possiamo usarlo per dirci quanta precisione ci serve. Quello che possiamo fare invece è usare il fatto che $r$ deve essere minore di $N$ per assicurarci di usare una precisione sufficiente. In particolare, se usiamo una precisione tale da 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. Prendere $m = 2\operatorname{lg}(N)+1$ garantisce una buona probabilità di ottenere una stima con questa precisione usando il metodo descritto in precedenza. (Prendere $m = 2\operatorname{lg}(N)$ è sufficiente se si è soddisfatti di un limite inferiore del 40% sulla probabilità di successo.)

Soluzione generale

Come abbiamo appena visto, se abbiamo l'autovettore $\vert \psi_1 \rangle$ di $M_a,$ possiamo apprendere $r$ tramite la stima di fase, a patto di usare un numero sufficiente di qubit di controllo per farlo con la precisione necessaria. Purtroppo, non è facile ottenere l'autovettore $\vert\psi_1\rangle,$ 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 considerare. Il risultato che otteniamo dalla procedura di stima di fase sarà un'approssimazione

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

Assumendo di non conoscere né $k$ né $r,$ questo potrebbe o meno permetterci di identificare $r.$ Per esempio, se $k = 0$ otterremo un'approssimazione $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 usare un algoritmo noto come algoritmo delle frazioni continue per trasformare la nostra approssimazione $y/2^m$ in frazioni vicine — inclusa $k/r$ se l'approssimazione è sufficientemente buona. Non spiegheremo qui l'algoritmo delle frazioni continue. Invece, ecco un enunciato di un fatto noto su questo algoritmo.

Fatto

Dato un intero $N\geq 2$ e un numero reale $\alpha\in(0,1),$ esiste al più una scelta di interi $u,v\in\{0,\ldots,N-1\}$ con $v\neq 0$ e $\gcd(u,v)=1$ che soddisfa $\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 $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 descritti nel fatto. Un'analisi del fatto ci permette di concludere che

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

Si noti in particolare che non necessariamente apprendiamo $k$ e $r,$ ma solo $k/r$ nella sua forma ridotta ai minimi termini.

Per esempio, e come abbiamo già notato, non impareremo nulla da $k=0.$ Ma questo è l'unico valore di $k$ per cui accade. 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 abbiamo la capacità di apprendere $u$ e $v$ per $u/v = k/r$ con $k\in\{0,\ldots,r-1\}$ scelto uniformemente a caso, allora è molto probabile che riusciamo a recuperare $r$ dopo solo pochi campionamenti. In particolare, se la nostra ipotesi per $r$ è il minimo comune multiplo di tutti i valori del denominatore $v$ che osserviamo, avremo ragione con alta probabilità. Intuitivamente, alcuni valori di $k$ non sono buoni perché condividono fattori comuni con $r,$ e quei fattori comuni ci rimangono nascosti quando apprendiamo $u$ e $v.$ Ma le scelte casuali di $k$ non sono portate a nascondere fattori di $r$ a lungo, e la probabilità che non indoviniamo correttamente $r$ prendendo il minimo comune multiplo dei denominatori che osserviamo decresce esponenzialmente nel numero di campionamenti.

Resta da affrontare il problema di come otteniamo un autovettore $\vert\psi_k\rangle$ di $M_a$ su cui eseguire la procedura di stima di fase. Come risulta, in realtà non abbiamo bisogno di crearlo!

Quello che faremo invece è eseguire la procedura di stima di fase sullo stato $\vert 1\rangle,$ intendendo con ciò 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 di fase su un particolare autovettore, ma nulla ci impedisce di eseguire la procedura su uno stato di ingresso che non è 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,$ che non è una scelta che ci interesserà.)

La motivazione per scegliere 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 è confrontare i prodotti interni dei due lati con ogni stato della base standard, usando le formule menzionate in precedenza nella lezione per valutare i risultati del lato destro. Di conseguenza, otterremo esattamente gli stessi risultati di misura come se avessimo scelto $k\in\{0,\ldots,r-1\}$ uniformemente a caso e usato $\vert\psi_k\rangle$ come autovettore.

In maggior dettaglio, immaginiamo di eseguire la procedura di stima di fase con lo stato $\vert 1\rangle$ al posto di uno degli autovettori $\vert\psi_k\rangle.$ Dopo che la trasformata di Fourier quantistica inversa è stata eseguita, questo ci lascia con 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 degli $m$ qubit superiori dopo che la trasformata di Fourier quantistica inversa è stata eseguita su di essi.

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

Costo totale

Il costo per implementare ogni unitaria controllata $M_a^k$ è $O(n^2).$ Ci sono $m$ operazioni unitarie controllate, e abbiamo $m = O(n),$ quindi il costo totale per le operazioni unitarie controllate è $O(n^3).$ Inoltre, abbiamo $m$ gate di Hadamard (che contribuiscono $O(n)$ al costo), e la trasformata di Fourier quantistica inversa contribuisce $O(n^2)$ al costo. Pertanto, il costo delle operazioni unitarie controllate 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 durante il processo. Questo include 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 di $O(n^3).$

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

Fattorizzare tramite la ricerca dell'ordine

L'ultimissima cosa che dobbiamo discutere è come la soluzione al problema della ricerca dell'ordine ci aiuti a fattorizzare. Questa parte è completamente classica — non ha nulla che riguardi specificamente il calcolo quantistico.

Ecco l'idea di base. Vogliamo fattorizzare il numero $N,$ e possiamo farlo ricorsivamente. Nello specifico, possiamo concentrarci sul compito di dividere $N,$ che significa trovare due interi qualsiasi $b,c\geq 2$ per cui $N = bc.$ Questo non è possibile se $N$ è un numero primo, ma possiamo verificare in modo efficiente se $N$ è primo usando prima un algoritmo di test di primalità, e se $N$ non è primo cercheremo di dividerlo. Una volta diviso $N,$ possiamo semplicemente ricorrere su $b$ e $c$ fino a quando tutti i nostri fattori sono primi e otteniamo la fattorizzazione in fattori primi di $N.$

Dividere i numeri pari è semplice: basta restituire $2$ e $N/2.$

È anche facile dividere le 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 controllando gli interi vicini come candidati per $s.$ Non occorre andare oltre $\log(N)$ passi in questa sequenza, perché a quel punto la radice scende sotto $2$ e non rivelerà ulteriori candidati.

È positivo che riusciamo a fare entrambe queste cose, perché la ricerca dell'ordine non ci aiuterà a fattorizzare i numeri pari né le potenze di numeri primi, dove il numero $s$ è primo. Se $N$ è dispari e non è una potenza di primo, tuttavia, la ricerca dell'ordine ci permette di dividere $N.$

Algoritmo probabilistico per dividere un intero dispari composito N che non è una potenza di primo

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

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

3. Se $d > 1$ allora restituire $b = d$ e $c = N/d$ e fermarsi. Altrimenti continuare al passo successivo sapendo che $a\in\mathbb{Z}_N^{\ast}.$

4. Sia $r$ l'ordine di $a$ modulo $N.$ (Qui è dove abbiamo bisogno della ricerca dell'ordine.)

5. Se $r$ è pari:

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

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

Un'esecuzione di questo algoritmo potrebbe non riuscire a trovare un fattore di $N.$ In particolare, questo 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.$

Usando la teoria elementare dei numeri si può dimostrare che, per una scelta casuale di $a,$ con probabilità almeno $1/2$ nessuno di questi eventi si verifica. In realtà, la probabilità che uno dei due eventi si verifichi è al più $2^{-(m-1)}$ dove $m$ è il numero di fattori primi distinti di $N,$ ed è per questo che è necessaria l'assunzione che $N$ non sia una potenza di primo. (Anche l'assunzione che $N$ sia dispari è necessaria affinché questo fatto sia vero.)

Questo 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 probabilità almeno $1 - 2^{-t}.$

L'idea di base dell'algoritmo è la seguente. Se abbiamo una scelta di $a$ per cui 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{e} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

Usando la formula $Z^2 - 1 = (Z+1)(Z-1),$ concludiamo 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).$$

Affinché 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, fintanto che 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 MCD con il primo termine.