Algoritmo di Shor

Per questo modulo di Qiskit in Classrooms, gli studenti devono disporre di un ambiente Python funzionante con i seguenti pacchetti installati:

• qiskit v2.1.0 o successivo
• qiskit-ibm-runtime v0.40.1 o successivo
• qiskit-aer v0.17.0 o successivo
• qiskit.visualization
• numpy
• pylatexenc

Per configurare e installare i pacchetti indicati, consulta la guida Installare Qiskit. Per eseguire job su veri computer quantistici, gli studenti dovranno creare un account IBM Quantum® seguendo i passaggi descritti nella guida Configura il tuo account IBM Cloud.

Questo modulo è stato testato e ha utilizzato tre secondi di tempo QPU. Si tratta di una stima indicativa. Il consumo effettivo può variare.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introduzione

All'inizio degli anni '90 cresceva l'entusiasmo attorno al potenziale dei computer quantistici di risolvere problemi difficili per i computer classici. Alcuni talentuosi informatici avevano ideato algoritmi che dimostravano la potenza del calcolo quantistico per problemi di nicchia e artificiosi, ma nessuno aveva ancora trovato la "killer app" definitiva del calcolo quantistico, destinata a rivoluzionare il settore. Fino al 1994, quando Peter Shor formulò quello che oggi è chiamato algoritmo di Shor per la fattorizzazione di numeri grandi.

Era noto all'epoca che trovare i fattori primi di un numero grande fosse estremamente difficile per un computer classico. I protocolli di sicurezza su Internet si basavano proprio su questa difficoltà. Shor trovò un modo per trovare questi fattori in modo esponenzialmente più efficiente, delegando alcune delle operazioni più complesse a un futuro, teorico computer quantistico.

In questo modulo esploreremo l'algoritmo di Shor. Prima forniremo un po' di contesto sull'algoritmo, formalizzando il problema che risolve e spiegandone la rilevanza per la cybersecurity. Poi daremo un'introduzione alla matematica modulare e a come applicarla al problema della fattorizzazione, mostrando come la fattorizzazione si riduca a un altro problema chiamato "ricerca dell'ordine". Mostreremo come entrino in gioco la Quantum Fourier Transform e la Quantum Phase Estimation, studiate in un modulo precedente, e come usarle per risolvere il problema della ricerca dell'ordine.

Infine, eseguiremo l'algoritmo di Shor su un vero computer quantistico! Tieni presente, però, che questo algoritmo sarà davvero utile solo quando avremo a disposizione un grande computer quantistico fault-tolerant, che è ancora a qualche anno di distanza. Quindi, fattorizzeremo soltanto un numero piccolo per dimostrare il funzionamento dell'algoritmo.

Il problema della fattorizzazione

L'obiettivo del problema della fattorizzazione è trovare i fattori primi di un numero $N$. Per alcuni numeri $N$ questo è piuttosto semplice. Ad esempio, se $N$ è pari, uno dei suoi fattori primi sarà 2. Se $N$ è una potenza di un primo, cioè $N=p^k$ per qualche numero primo $p$, è anche abbastanza facile trovare $p$: basta approssimare la radice $k^{\text{esima}}$ di $N$ e cercare i numeri primi vicini che potrebbero essere $p$.

Il punto in cui i computer classici faticano, però, è quando $N$ è dispari e non è una potenza di un primo. Questo è il caso che l'algoritmo di Shor affronta. L'algoritmo trova due fattori $p$ e $q$ tali che $N=pq$. Può essere applicato ricorsivamente finché tutti i fattori non sono primi. Nelle sezioni successive vedremo come affrontare questo problema.

Rilevanza per la cybersecurity

Molti schemi crittografici sono stati costruiti basandosi sul fatto che fattorizzare numeri grandi è difficile, tra cui uno ampiamente usato oggi, chiamato RSA. In RSA, una chiave pubblica viene creata moltiplicando due grandi numeri primi per ottenere $N = p\cdot q$. Chiunque può usare questa chiave pubblica per cifrare dati. Ma solo chi possiede la chiave privata, cioè $p$ e $q$, può decifrare quei dati.

Se $N$ fosse facile da fattorizzare, chiunque sarebbe in grado di determinare $p$ e $q$ e rompere la cifratura. Ma non è così. Si tratta di un problema notoriamente difficile. In effetti, i fattori primi di un numero chiamato RSA1024, lungo 1024 bit e 309 cifre decimali, non sono stati ancora trovati, nonostante un premio di $100.000 fosse stato offerto per la sua fattorizzazione già nel 1991.

La soluzione di Shor

Nel 1994, Peter Shor si rese conto che un computer quantistico avrebbe potuto fattorizzare un numero grande in modo esponenzialmente più efficiente rispetto a un computer classico. La sua intuizione si basava sulla relazione tra questo problema di fattorizzazione e l'aritmetica modulare. Daremo una breve introduzione all'aritmetica modulare, poi vedremo come usarla per fattorizzare $N$.

Aritmetica modulare

L'aritmetica modulare è un sistema di conteggio ciclico: il conteggio inizia nel modo consueto, con gli interi 0, 1, 2, ecc., ma a un certo punto, dopo un periodo $N$, ricomincia da capo. Vediamolo con un esempio. Supponiamo che il periodo sia 5. Allora, nel conteggio, dove normalmente arriveremmo a 5, ricominciamo invece da 0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

Questo perché nel "mondo modulo-5", 5 è equivalente a 0. Si dice che $5\bmod 5 \ = 0$. In effetti, tutti i multipli di 5 saranno equivalenti a $0\bmod 5$.

Metti alla prova la tua comprensione

Leggi la/le domanda/e qui sotto, pensa alla risposta, poi fai clic sul triangolo per rivelare la soluzione.

Usa l'aritmetica modulare per risolvere il seguente problema:

Parti per un lungo viaggio in treno transcontinentale alle 8:00. Il viaggio dura 60 ore. A che ora arrivi a destinazione?

Risposta:

Il periodo è 24, poiché ci sono 24 ore in un giorno. Quindi, questo problema può essere scritto in aritmetica modulare come:

$(8+60)\text{mod}(24) = 20$

Quindi arriveresti a destinazione alle 20:00.

$\mathbb{Z}_N$ e $\mathbb{Z}_N^*$

Spesso è utile introdurre due insiemi, $\mathbb{Z}_N$ e $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ è semplicemente l'insieme dei numeri che esistono nel "mondo modulo-$N$". Ad esempio, quando contavamo modulo-5, l'insieme sarebbe $\mathbb{Z}_5=\{0,1,2,3,4\}$. Un altro esempio: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. Possiamo eseguire addizione e moltiplicazione (modulo $N$) sugli elementi di $\mathbb{Z}_N$, e il risultato di ciascuna di queste operazioni è anch'esso un elemento di $\mathbb{Z}_N$, rendendo $\mathbb{Z}_N$ un oggetto matematico chiamato anello.

Esiste un sottoinsieme speciale di $\mathbb{Z}_N$ di particolare interesse per l'algoritmo di Shor. Si tratta del sottoinsieme dei numeri in $\mathbb{Z}_N$ tali che il massimo comune divisore tra ciascun elemento e $N$ sia 1, cioè ogni elemento è "coprimo" con $N$. Se prendiamo l'insieme di questi numeri insieme all'operazione di moltiplicazione modulare, otteniamo un altro oggetto matematico, chiamato gruppo. Chiamiamo questo gruppo $\mathbb{Z}_N^*$. Si scopre che con $\mathbb{Z}_N^*$ (e con i gruppi finiti in generale), se scegliamo un qualsiasi elemento $a \in \mathbb{Z}_N^*$ e lo moltiplichiamo ripetutamente per se stesso, otterremo sempre il numero $1$. Il numero minimo di volte in cui occorre moltiplicare $a$ per se stesso per ottenere $1$ è chiamato ordine di $a$. Questo fatto sarà molto importante nella nostra discussione su come fattorizzare numeri.

Metti alla prova la tua comprensione

Leggi la/le domanda/e qui sotto, pensa alla risposta, poi fai clic sul triangolo per rivelare la soluzione.

Cos'è $\mathbb{Z}_{15}^*$?

Risposta:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

Abbiamo escluso i seguenti numeri:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

Qual è l'ordine di ciascuno degli elementi di $\mathbb{Z}_{15}^*$?

Risposta:

L'ordine $r$ è il numero più basso tale che $a^r\text{mod}(15)=1$ per ogni elemento $a$.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

Nota che, sebbene siamo riusciti a trovare l'ordine dei numeri in $\mathbb{Z}_{15}^*$, questo NON è un compito facile in generale, per $N$ più grandi. Questo è il punto cruciale del problema della fattorizzazione e il motivo per cui abbiamo bisogno di un computer quantistico. Lo vedremo man mano che percorreremo il resto del notebook.

Applicare l'aritmetica modulare al problema della fattorizzazione

La chiave per trovare i fattori $p$ e $q$ tali che $N=pq$ consiste nel trovare un altro intero $x$ tale che

$x^2 \equiv 1 \bmod N$ e $x \not\equiv \pm 1 \bmod N.$

Come ci aiuta trovare $x$ a trovare i fattori $p$ e $q$? Vediamo il ragionamento. Poiché $x^2 \equiv 1 \bmod N$, ciò significa che $x^2 - 1 \equiv 0 \bmod N$. In altre parole, $x^2 - 1$ è un multiplo di $N$. Quindi, per qualche intero $l$,

$x^2 - 1 = l N$

Possiamo fattorizzare $x^2 - 1$ per ottenere:

$(x+1)(x-1) = l N$

Dalle nostre ipotesi iniziali sappiamo che $x \not\equiv \pm 1 \bmod N$, quindi $N$ non divide esattamente né $x+1$ né $x-1$. Pertanto, i due fattori di $N$, $p$ e $q$, devono ciascuno dividere $x-1$ e $x+1$. O $p$ è un fattore di $x-1$ e $q$ è un fattore di $x+1$, o viceversa. Quindi, se calcoliamo il massimo comune divisore (MCD) tra $N$ e sia $x-1$ che $x+1$, otterremo i fattori $p$ e $q$. Calcolare il MCD tra due numeri è un compito classicamente semplice che può essere svolto, ad esempio, con l'algoritmo di Euclide.

Metti alla prova la tua comprensione

Leggi la/le domanda/e qui sotto, pensa alla risposta, poi fai clic sul triangolo per rivelare la soluzione.

Potrebbe non essere facile seguire ogni passaggio logico di cui sopra, quindi prova a ragionare con un esempio. Usa $N=15$ e $x=11$. Prima, verifica che $x^2 \equiv 1 \text{mod}(N)$ e $x \not\equiv \pm 1 \bmod N$. Poi continua a verificare ogni passaggio. Infine, calcola $\text{GCD}(11\pm1,15)$ e verifica che siano i fattori di $15$.

Risposta:

$11^2 = 121$, che è $15*8 + 1$, quindi $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, che non è equivalente a $0\bmod 15$. $\checkmark$

$11 + 1 = 12$, che non è equivalente a $0\bmod 15$. $\checkmark$

Ora sappiamo che $(x+1)(x-1) = l N$ per qualche intero $l$. Ciò si verifica inserendo $x$ e $N$: $(12)(10) = l 15$ quando $l = 8$. $\checkmark$

Ora dobbiamo calcolare $\text{GCD}(12,15)$ e $\text{GCD}(10,15)$.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

Abbiamo trovato i fattori di $15$!

L'algoritmo

Ora che abbiamo visto come trovare un intero $x$ tale che $x^2 \equiv 1\bmod N$ ci aiuti a fattorizzare $N$, possiamo descrivere l'algoritmo di Shor. Essenzialmente si riduce a trovare $x$:

1. Scegli un intero casuale Scegli un intero casuale $a$ tale che $1 < a < N$.

• Calcola $\text{GCD}(a, N)$ in modo classico.
  • Se $\text{GCD}(a, N) > 1$, hai già trovato un fattore. Fermati.
  • Altrimenti, continua.

2. Trova l'ordine $r$ di $a$ modulo $N$ Trova il più piccolo intero positivo $r$ che soddisfa $a^r \equiv 1 \pmod N$.

3. Verifica se l'ordine è pari

• Se $r$ è dispari, torna al passaggio 1 e scegli un nuovo $a$.
• Se $r$ è pari, continua al passaggio 4.

4. Calcola $x = a^{r/2} \bmod N$

• Verifica che $x \not\equiv 1 \pmod N$ e $x \not\equiv -1 \pmod N$.
  • Se $x \equiv \pm 1 \pmod N$, torna al passaggio 1 e scegli un nuovo $a$.
• Altrimenti, calcola i MCD per estrarre i fattori:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

Questi saranno fattori non banali di $N$.

5. Fattorizza ricorsivamente se necessario

• Se $p$ e/o $q$ non sono primi, applica l'algoritmo ricorsivamente per fattorizzarli completamente.
• Una volta che tutti i fattori sono primi, la fattorizzazione è completa.

In base a questa procedura, potrebbe non essere ovvio perché sia necessario un computer quantistico per completare il compito. È necessario perché il passaggio 2, trovare l'ordine di $a$ modulo $N$, è classicamente un problema molto difficile. La complessità cresce esponenzialmente con $N$. Ma con un computer quantistico, dobbiamo solo usare la Quantum Phase Estimation per risolverlo. Il passaggio 4, trovare il MCD di due interi, è in realtà un'operazione abbastanza semplice da fare in modo classico. Quindi, l'unico passaggio che richiede davvero la potenza di un computer quantistico è quello della ricerca dell'ordine. Si dice che il problema della fattorizzazione si "riduce" al problema della ricerca dell'ordine.

La parte difficile: la ricerca dell'ordine

Ora vedremo come usare un computer quantistico per la ricerca dell'ordine. Prima di tutto, chiariamo cosa intendiamo per "ordine". Naturalmente, ti ho già spiegato il significato matematico dell'ordine: è il primo intero non nullo $r$ tale che $a^r = 1 \pmod N.$ Ma vediamo se riusciamo a sviluppare un po' più di intuizione per questo concetto.

Per $N$ abbastanza piccoli, possiamo determinare l'ordine semplicemente calcolando ogni potenza di $a$, prendendo il modulo $N$ di quel numero, poi fermandoci quando troviamo la potenza $r$ che soddisfa $a^r = 1 \text{mod}(N)$. È quello che abbiamo fatto con il nostro esempio, $N=15$, sopra. Diamo un'occhiata ad alcuni grafici di queste potenze modulari per alcuni valori campione di $a$ e $N$:

Noti qualcosa? Sono funzioni periodiche! E l'ordine $r$ è uguale al periodo! Quindi, la ricerca dell'ordine è equivalente alla ricerca del periodo.

I computer quantistici sono particolarmente adatti a trovare il periodo delle funzioni. Per questo, possiamo usare una subroutine algoritmica chiamata Quantum Phase Estimation. Abbiamo discusso della QPE e della sua relazione con la Quantum Fourier Transform nel modulo precedente. Per un ripasso dettagliato, vai al modulo sulla QFT o alla lezione di John Watrous sulla Quantum Phase Estimation nel suo corso di Algoritmi Quantistici. Qui riassumiamo il procedimento:

Nella Quantum Phase Estimation (QPE), partiamo da un unitario $U$ e da un autostato di quell'unitario $|\psi\rangle$. Poi usiamo QPE per approssimare l'autovalore corrispondente, che, poiché l'operatore è unitario, sarà della forma $e^{2\pi i \theta}$. Quindi, trovare l'autovalore è equivalente a trovare il valore di $\theta$ nella funzione periodica. Il circuito ha questo aspetto:

dove il numero di qubit di controllo (gli $m$ qubit superiori nella figura sopra) determina la precisione dell'approssimazione.

Nell'algoritmo di Shor, usiamo QPE sull'operatore unitario $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

Qui, $|y\rangle$ denota uno stato della base computazionale del registro multi-qubit, dove il valore binario dei qubit corrisponde all'intero $y$. Ad esempio, se $N=15$ e $y = 2$, allora $|y\rangle$ è rappresentato dallo stato della base a quattro qubit $|0010\rangle$, poiché quattro qubit sono necessari per codificare numeri fino a 15. (Se questo concetto non è familiare, consulta il modulo introduttivo di Qiskit in classrooms per un ripasso sulla codifica binaria degli stati quantistici.)

Ora dobbiamo trovare un autostato di questo unitario. Se partiamo dallo stato $|1\rangle$, possiamo vedere che ogni successiva applicazione di $U$ moltiplicherà lo stato del nostro registro per $a \pmod N$, e dopo $r$ applicazioni torneremo allo stato $|1\rangle$. Ad esempio con $a = 3$ e $N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

Quindi le sovrapposizioni degli stati in questo ciclo ($|\psi_j\rangle$) della forma:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

sono tutti autostati di $M_a$. (Ci sono più autostati di questi. Ma a noi interessano solo quelli della forma precedente.)

Metti alla prova la tua comprensione

Leggi la/le domanda/e qui sotto, pensa alla risposta, poi fai clic sul triangolo per rivelare la soluzione.

Trova un autostato dell'unitario corrispondente a $a=2$ e $N = 15$.

Risposta:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

Quindi, l'ordine è $r=4$. Gli autostati che ci interessano saranno una sovrapposizione uguale di tutti gli stati attraversati sopra, con varie fasi:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Supponiamo di riuscire a inizializzare il nostro stato di qubit in uno di questi autostati (spoiler — non è possibile. O almeno non facilmente. Spiegheremo perché e cosa possiamo fare in alternativa a breve). Potremmo quindi usare QPE per stimare l'autovalore corrispondente, $\omega_j = e^{2 \pi i \theta_j}$ dove $\theta_j = \frac{j}{r}$. Poi saremo in grado di determinare l'ordine $r$ con la semplice equazione:

$r = \frac{j}{\theta_j}.$

Ma ricorda, ho detto che QPE stima $\theta_j$ — non ci dà un valore esatto. La stima deve essere sufficientemente buona da distinguere tra $r$ e $r+1$. Più qubit di controllo $m$ abbiamo, migliore sarà la stima. Nei problemi alla fine della lezione ti verrà chiesto di determinare il minimo $m$ necessario per fattorizzare un numero $N$.

Ora dobbiamo affrontare un problema. Tutta la spiegazione precedente su come trovare $r$ inizia preparando l'autostato $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Ma non sappiamo come farlo senza già conoscere $r$. Il ragionamento è circolare. Abbiamo bisogno di un modo per stimare l'autovalore senza inizializzare l'autostato.

Invece di partire da un autostato di $M_a$, possiamo preparare lo stato iniziale nello stato a $n$ qubit corrispondente a $|1\rangle$ in binario (cioè, $|000...01\rangle$). Sebbene questo stato non sia ovviamente un autostato di $M_a$, è una sovrapposizione di tutti gli autostati $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

Metti alla prova la tua comprensione

Leggi la/le domanda/e qui sotto, pensa alla risposta, poi fai clic sul triangolo per rivelare la soluzione.

Verifica che $|1\rangle$ sia equivalente alla sovrapposizione degli autostati che hai trovato per $N=15$ e $a=2$ nella domanda di verifica precedente.

Risposta:

I quattro autostati erano:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Quindi,

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

Come ci permette questo di trovare l'ordine $r$? Poiché lo stato iniziale è una sovrapposizione di tutti gli autostati della forma elencata sopra, l'algoritmo QPE stima simultaneamente ciascuno dei $\theta_k$ corrispondenti a questi autostati. Quindi, la misurazione degli $m$ qubit di controllo alla fine produrrà un'approssimazione del valore $k/r$, dove $k \in \{0,1,2,...,r-1\}$ è uno degli autovalori scelto casualmente. Se ripetiamo questo circuito alcune volte e otteniamo alcuni campioni con valori diversi di $k$, saremo in grado di dedurre rapidamente $r$.

Implementazione in Qiskit

Come accennato in precedenza, l'hardware attuale non è ancora in grado di fattorizzare numeri enormi come RSA1024. Fattorizzeremo quindi un numero piccolo per dimostrare come funziona l'algoritmo. Per questa demo useremo una versione semplificata del codice presentato nel tutorial sull'algoritmo di Shor. Se desideri maggiori dettagli, visita il tutorial.

Eseguiremo l'algoritmo usando il nostro framework standard per la risoluzione di problemi quantistici, il framework Qiskit patterns. Questo consiste in quattro passi:

1. Mappare il problema su un circuito quantistico
2. Ottimizzare il circuito per l'esecuzione sull'hardware quantistico
3. Eseguire il circuito sul computer quantistico
4. Post-elaborare le misurazioni

1. Mappatura

Fattorizziamo $N=15$, scegliendo $a=2$ come intero coprimo.

Per prima cosa, dobbiamo costruire il circuito che implementa l'unitario di moltiplicazione modulare $M_a$. Questa è in realtà la parte più difficile dell'intera implementazione e può essere computazionalmente molto costosa, a seconda di come viene eseguita. Per questo, barereremo un po': sappiamo che iniziamo nello stato $|1\rangle$ e da una domanda di verifica precedente,

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

Costruiremo quindi un unitario che esegue le operazioni corrette su questi quattro stati, lasciando invariati tutti gli altri. Questo è un trucco perché stiamo usando la nostra conoscenza dell'ordine di $2\bmod 15$ per semplificare l'unitario. Se stessimo davvero cercando di fattorizzare un numero i cui fattori ci sono sconosciuti, non potremmo farlo.

Verifica della comprensione

Leggi la/le domanda/e seguenti, pensa alla tua risposta, poi clicca il triangolo per scoprire la soluzione.

Con la tua conoscenza di come l'operatore $M_2$ trasforma gli stati di cui sopra, costruisci l'operatore a partire da una serie di gate SWAP, che scambiano gli stati di due qubit. (Suggerimento: scrivere ogni stato $|i\rangle$ in binario può aiutare.)

Risposta:

Riscriviamo l'azione di $M_2$ sugli stati in binario:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

Ciascuna di queste azioni può essere realizzata con un semplice SWAP. $M_2|0001\rangle$ si ottiene scambiando gli stati del qubit $0$ e $1$. $M_2|0010\rangle$ si ottiene scambiando gli stati del qubit $1$ e $2$. E così via. Possiamo quindi decomporre la matrice $M_2$ nella seguente serie di gate SWAP:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

Ricordando che gli operatori agiscono da destra a sinistra, verifichiamo che questo abbia l'effetto desiderato su ciascuno degli stati:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

Possiamo ora programmare il circuito equivalente a questo operatore in Qiskit.

Per prima cosa, importiamo i pacchetti necessari:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

Poi, costruiamo l'operatore $M_2$:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

L'algoritmo QPE usa un gate controlled-$U$. Ora che abbiamo un circuito $M_2$, dobbiamo renderlo un circuito controlled-$M_2$:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Abbiamo ora il nostro gate controlled-$U$. Ma per eseguire l'algoritmo di Quantum Phase Estimation, avremo bisogno di controlled-$U^2$, controlled-$U^4$, fino a controlled-$U^{2^{m-1}}$, dove $m$ è il numero di qubit usati per stimare la fase. Più qubit ci sono, più precisa sarà la stima della fase. Useremo $m=8$ qubit di controllo per la nostra procedura di stima della fase. Abbiamo quindi bisogno di:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

dove l'indice $k$, con $0 \le k \le m-1 = 7$, corrisponde al qubit di controllo. Ora calcoliamo $a^{2^k}\bmod N$ per ogni valore di $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

Poiché $a^{2^k} \bmod N = 1$ per $k \ge 2$, tutti gli operatori corrispondenti ($M_8$ e superiori) sono equivalenti all'identità. Dobbiamo quindi costruire solo un'altra matrice, $M_4.$

Nota: Questa semplificazione funziona qui solo perché l'ordine di $2 \bmod 15$ è $4$. Una volta raggiunto $k=2$ (cioè $2^k = 4$), ogni potenza successiva dell'operatore è l'identità. In generale, per numeri $N$ più grandi o diverse scelte di $a$, non è possibile saltare la costruzione delle potenze superiori. Questo è uno dei motivi per cui si tratta di un esempio giocattolo: i numeri piccoli consentono scorciatoie che non funzionerebbero per casi più grandi.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

E come in precedenza, lo rendiamo un operatore controlled-$M_4$:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Ora possiamo mettere tutto insieme per trovare l'ordine di $2\bmod 15$ con un circuito quantistico, usando la stima della fase:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. Ottimizzazione

Ora che abbiamo mappato il nostro circuito, il passo successivo è ottimizzarlo per l'esecuzione su un particolare computer quantistico. Prima dobbiamo caricare il backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Se non hai tempo disponibile sul tuo account o vuoi usare un simulatore per qualsiasi motivo, puoi eseguire la cella seguente per configurare un simulatore che imita il dispositivo quantistico che abbiamo selezionato sopra:

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. Esecuzione

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

Vediamo quattro picchi chiari in corrispondenza di 00000000, 01000000, 10000000 e 11000000, con alcuni conteggi in altre stringhe di bit dovuti al rumore del computer quantistico. Li ignoreremo e terremo solo i quattro dominanti imponendo una soglia: solo i conteggi sopra questa soglia sono considerati un segnale vero al di sopra del rumore.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. Post-elaborazione

Per l'algoritmo di Shor, gran parte dell'algoritmo viene eseguita classicamente. Quindi, metteremo il resto nel passo di "post-elaborazione", dopo aver ottenuto le misurazioni dal computer quantistico. Ciascuna delle misurazioni di cui sopra può essere convertita in interi che, dopo la divisione per $2^m$, sono le nostre approssimazioni di $\frac{k}{r}$, dove $k$ è casuale ogni volta.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

Conclusione

Dopo aver percorso il modulo, potresti aver maturato una nuova ammirazione per la brillantezza di Peter Shor nell'aver ideato un algoritmo così ingegnoso. Ma speriamo che tu abbia anche raggiunto un livello più profondo di comprensione della sua semplicità ingannevole. Anche se l'algoritmo può sembrare impressionantemente (o intimidatoriamente) complesso, se lo scomponi in ogni singolo passaggio logico e lo affronti con calma, anche tu sarai in grado di eseguire l'algoritmo di Shor.

Sebbene siamo ancora lontani dall'usare questo algoritmo per fattorizzare numeri come RSA1024, i nostri computer quantistici migliorano ogni giorno e, una volta raggiunta una soglia chiamata tolleranza ai guasti, algoritmi come questi seguiranno presto. È un momento entusiasmante per imparare il calcolo quantistico!

Problemi

Concetti fondamentali:

• I moderni sistemi crittografici si basano sulla difficoltà classica di fattorizzare interi di grandi dimensioni.
• L'aritmetica modulare — incluse le strutture $\mathbb{Z}_N$ e $\mathbb{Z}_N^*$ — fornisce la base matematica per l'algoritmo di Shor.
• Il problema della fattorizzazione di un intero $N$ può essere ricondotto al problema di trovare l'ordine di un numero modulo $N$.
• La ricerca dell'ordine quantistico utilizza tecniche di stima della fase quantistica per determinare il periodo della funzione $a^x \mod N$.
• L'algoritmo di Shor consiste in un flusso di lavoro ibrido classico-quantistico che seleziona una base, esegue la ricerca dell'ordine quantistico e poi calcola classicamente i fattori dal risultato.

Vero/Falso:

1. V/F L'efficienza dell'algoritmo di Shor minaccia la sicurezza della crittografia RSA.
2. V/F L'algoritmo di Shor può essere eseguito efficientemente su qualsiasi computer quantistico moderno.
3. V/F L'algoritmo di Shor utilizza la stima della fase quantistica (QPE) come subroutine chiave.
4. V/F La parte classica dell'algoritmo di Shor prevede il calcolo del massimo comune divisore (MCD).
5. V/F L'algoritmo di Shor funziona solo per la fattorizzazione di numeri pari.
6. V/F Un'esecuzione riuscita dell'algoritmo di Shor garantisce sempre i fattori corretti.

Risposta breve:

1. Perché l'algoritmo di Shor è considerato una potenziale minaccia futura per la crittografia RSA?
2. Perché trovare il periodo, o ordine, di una funzione esponenziale modulare è utile per fattorizzare un numero nell'algoritmo di Shor?

Problemi avanzati:

1. Di quanti qubit di controllo $m$ abbiamo bisogno per un dato numero $N$ che stiamo cercando di fattorizzare, al fine di ottenere la precisione nella QPE necessaria a trovare il valore corretto dell'ordine $r$?

2. Seguendo la procedura che abbiamo illustrato qui per fattorizzare 15, prova ora a fattorizzare 21.