Algoritmo di Shor

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

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

Per configurare e installare i pacchetti sopra indicati, consultare la guida Installazione di Qiskit. Per eseguire lavori su computer quantistici reali, gli studenti dovranno creare un account seguendo i passaggi indicati IBM Quantum® nella guida Configura il tuo IBM Cloud account.

Questo modulo è stato testato e ha utilizzato tre secondi di tempo QPU. Si tratta solo di una stima. L'utilizzo effettivo può variare.

# 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 del 1990s, cresceva l'entusiasmo per il potenziale dei computer quantistici nel risolvere problemi difficili per i computer classici. Alcuni talentuosi scienziati informatici avevano ideato algoritmi che dimostravano la potenza dell'informatica quantistica per alcuni problemi di nicchia e artificiosi, ma nessuno aveva trovato una singola "killer app" dell'informatica quantistica che potesse rivoluzionare il settore. Questo fino al 1994, quando Peter Shor ideò quello che oggi è conosciuto come algoritmo di Shor per la scomposizione in fattori di numeri grandi.

All'epoca era risaputo che trovare i fattori primi di un numero grande era estremamente difficile per un computer classico. Infatti, i protocolli di sicurezza Internet si basavano proprio su questa difficoltà. Shor ha trovato un modo per individuare questi fattori in modo esponenzialmente più efficiente, trasferendo alcuni dei passaggi più complessi su un futuro computer quantistico teorico.

In questo modulo esploreremo l'algoritmo di Shor. Per prima cosa, forniremo qualche informazione in più sull'algoritmo, formalizzando il problema che risolve e spiegandone la rilevanza per la sicurezza informatica. Successivamente, forniremo una panoramica sulla matematica modulare e su come applicarla al problema della scomposizione in fattori, mostrando come la scomposizione in fattori si riduca a un altro problema chiamato "ricerca dell'ordine" Mostreremo come entrano in gioco la trasformata di Fourier quantistica e la stima di fase quantistica che abbiamo appreso nel modulo precedente e come utilizzarle per risolvere il problema della ricerca dell'ordine.

Finalmente eseguiremo l'algoritmo di Shor su un vero computer quantistico! Tieni presente, però, che questo algoritmo sarà davvero utile solo quando avremo un computer quantistico grande e tollerante ai guasti, che è ancora lontano alcuni anni. Quindi, fattorizzeremo solo un numero piccolo per dimostrare come funziona l'algoritmo.

Il problema del factoring

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

Tuttavia, i computer classici incontrano difficoltà quando $N$ è dispari e non è una potenza prima. Questo è il caso trattato dall'algoritmo di Shor. L'algoritmo trova due fattori $p$ e $q$ tali che $N=pq$. Può essere applicato ricorsivamente fino a quando tutti i fattori sono primi. Nelle prossime sezioni vedremo come viene affrontato questo problema.

Rilevanza per la sicurezza informatica

Molti schemi crittografici sono stati sviluppati sulla base del fatto che la scomposizione in fattori di numeri grandi è difficile, compreso uno comunemente usato oggi, chiamato RSA. Nella crittografia RSA, una chiave pubblica viene creata moltiplicando due grandi numeri primi per ottenere $N = p\cdot q$. Quindi, chiunque può utilizzare questa chiave pubblica per crittografare i dati. Ma solo qualcuno in possesso della chiave privata, $p$ e $q$, può decriptare quei dati.

Se $N$ fosse facile da scomporre in fattori, allora chiunque sarebbe in grado di determinare quali sono $p$ $q$ e e violare la crittografia. Ma non è così. Questo è un problema notoriamente difficile. Infatti, i fattori primi di un numero chiamato RSA1024, lungo 1024 cifre binarie e 309 cifre decimali, non sono ancora stati trovati, nonostante nel 1991 fosse stato offerto un premio di 100.000 dollari per la sua scomposizione in fattori primi.

La soluzione di Shor

Nel 1994, Peter Shor si rese conto che un computer quantistico poteva scomporre 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. Faremo una breve introduzione all'aritmetica modulare, poi vedremo come possiamo usarla per scomporre in fattori $N$.

Aritmetica modulare

L'aritmetica modulare è un sistema di conteggio ciclico, il che significa che, sebbene il conteggio inizi nel modo consueto, con i numeri interi 0, 1, 2, ecc., ad un certo punto, dopo un periodo $N$, il conteggio ricomincia da capo. Vediamo come funziona con un esempio. Supponiamo che il nostro periodo sia 5. Quindi, mentre contiamo, 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 equivale a 0. Diciamo che $5\bmod 5 \ = 0$. Infatti, tutti i multipli di 5 saranno equivalenti a $0\bmod 5$.

Verifica la tua comprensione

Utilizza l'aritmetica modulare per risolvere il seguente problema:

Parti per un lungo viaggio in treno transcontinentale alle 8 del mattino. Il viaggio in treno dura 60 ore. A che ora arrivi?

• 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, ovvero alle 8 di sera.

$\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 in un mondo "modulo- $N$ ". Ad esempio, quando stavamo contando 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 addizioni e moltiplicazioni (modulo $N$ ) sugli elementi in $\mathbb{Z}_N$, e il risultato di ciascuna di queste operazioni è anch'esso un elemento in $\mathbb{Z}_N$, rendendo $\mathbb{Z}_N$ un oggetto matematico chiamato anello.

Esiste un sottoinsieme speciale di $\mathbb{Z}_N$ che riveste particolare interesse per noi nell'ambito dell'algoritmo di Shor. Si tratta del sottoinsieme di numeri in $\mathbb{Z}_N$ tale che il massimo comune divisore tra ciascun elemento e $N$ è 1, quindi ciascun elemento è "coprimo" rispetto a $N$. Se prendiamo l'insieme di questi numeri insieme all'operazione di moltiplicazione modulare, si forma un altro oggetto matematico, chiamato gruppo. Chiamiamo questo gruppo $\mathbb{Z}_N^*$. Risulta che con $\mathbb{Z}_N^*$ (e con i gruppi finiti in generale), se scegliamo un elemento qualsiasi e moltiplichiamo $a \in \mathbb{Z}_N^*$ ripetutamente $a$ per se stesso, alla fine otterremo sempre il numero $1$. Il numero minimo di volte che bisogna moltiplicare $a$ per se stesso per ottenere $1$ è chiamato ordine di $a$. Questo fatto sarà molto importante per la nostra discussione su come scomporre i numeri in seguito.

Verifica la tua comprensione

Che 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 in $\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}$$

  Si noti che, sebbene siamo riusciti a trovare l'ordine dei numeri in $\mathbb{Z}_{15}^*$, questo NON è un compito facile in generale, per valori più grandi di $N$. Questo è il punto cruciale del problema della fattorizzazione e il motivo per cui abbiamo bisogno di un computer quantistico. Vedremo il perché man mano che procederemo con il resto del quaderno.

Applicare l'aritmetica modulare al problema della scomposizione in fattori

La chiave per trovare fattori $p$ e $q$ tali che $N=pq$ si riduce a trovare un altro numero intero $x$ tale che

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

In che modo trovare ci aiuta $x$ a trovare i fattori $p$ e $q$? Esaminiamo ora l'argomentazione. 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 un certo numero intero $l$,

$x^2 - 1 = l N$

Possiamo scomporre $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 è divisibile in modo uniforme né per $x+1$ né $x-1$ per. Quindi, i due fattori di $N$, $p$ e $q$ devono essere entrambi divisibili per $x-1$ e $x+1$. O $p$ è un fattore di $x-1$ e $q$ è un fattore di $x+1$, o viceversa. Pertanto, se calcoliamo i massimi comuni divisori (MCD) tra $N$ e sia $x-1$ che $x+1$, otterremo i fattori $p$ e $q$. Il calcolo del MCD tra due numeri è un'operazione classicamente facile che può essere eseguita, ad esempio, utilizzando l'algoritmo di Euclide.

Verifica la tua comprensione

Potrebbe essere difficile comprendere ogni fase della logica sopra descritta, quindi provate a seguirla con un esempio. Utilizzare $N=15$ e $x=11$. Innanzitutto, verificare che $x^2 \equiv 1 \text{mod}(N)$ e $x \not\equiv \pm 1 \bmod N$. Quindi continuare 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 un certo numero intero $l$. Ciò è verificabile quando inseriamo $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}$$

  Quindi, abbiamo trovato i nostri fattori di $15$!

L'algoritmo

Ora che abbiamo visto come trovare un numero intero $x$ tale che ci $x^2 \equiv 1\bmod N$ aiuta a scomporre $N$, possiamo passare all'algoritmo di Shor. In sostanza, si tratta di trovare $x$ :

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

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

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

3. Controlla se l'ordine è pari

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

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

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

Questi saranno fattori non banali di $N$.

5. Se necessario, fattorizzare ricorsivamente

• Se $p$ e/o non $q$ sono numeri primi, applicare l'algoritmo in modo ricorsivo per scomporli completamente.
• Una volta che tutti i fattori sono primi, il calcolo dei fattori è completo.

Sulla base di questa procedura, potrebbe non essere ovvio il motivo per cui sia necessario un computer quantistico per completare questa operazione. È necessario perché il passaggio 2, trovare l'ordine di $a$ modulo $N$, è classicamente un problema molto difficile. La complessità cresce in modo esponenziale con il numero $N$. Ma con un computer quantistico, basta utilizzare la stima della fase quantistica per risolverlo. Il quarto passo, trovare il MCD di due numeri interi, è in realtà piuttosto facile da fare in modo classico. Quindi, l'unico passaggio che richiede effettivamente la potenza di un computer quantistico è quello della ricerca dell'ordine. Diciamo che il problema del factoring "si riduce" al problema della ricerca dell'ordine.

La parte difficile: trovare l'ordine

Ora vedremo come utilizzare un computer quantistico per la ricerca. Innanzitutto, chiariamo cosa intendiamo per "ordine" Naturalmente, vi ho già spiegato il significato matematico dell'ordine: è il primo numero intero diverso da $r$ zero tale che $a^r = 1 \pmod N.$ Ma vediamo se riusciamo a comprendere meglio questo concetto.

Per valori sufficientemente piccoli $N$, possiamo semplicemente determinare l'ordine calcolando ogni potenza di $a$, prendendo il modulo $N$ di quel numero, quindi 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? Queste sono funzioni periodiche! E l'ordine $r$ è lo stesso del periodo! Quindi, trovare l'ordine equivale a trovare il periodo.

I computer quantistici sono particolarmente adatti per trovare il periodo delle funzioni. A tal fine, possiamo utilizzare una subroutine algoritmica denominata Quantum Phase Estimation (Stima della fase quantistica). Nel modulo precedente abbiamo discusso della QPE e della sua relazione con la trasformata di Fourier quantistica. Per un ripasso dettagliato, consulta il modulo QFT o la lezione di John Watrous sulla stima della fase quantistica nel suo corso sugli algoritmi quantistici. Ora esamineremo i punti salienti della procedura:

Nella stima della fase quantistica (QPE), si parte da un operatore unitario $U$ e da uno stato proprio di tale operatore unitario $|\psi\rangle$. Quindi, si utilizza la QPE per approssimare il corrispondente autovalore che, poiché l'operatore è unitario, avrà la forma $e^{2\pi i \theta}$. Quindi, trovare l'autovalore equivale a trovare il valore di $\theta$ nella funzione periodica. Il circuito ha questo aspetto:

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

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

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

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

Ora, dobbiamo capire uno stato proprio di questa unitaria. Se abbiamo iniziato dallo stato $|1\rangle$, possiamo vedere che ogni applicazione successiva di $U$ moltiplicherà lo stato del nostro registro per $a \pmod N$, e dopo $r$ applicazioni arriveremo nuovamente allo $|1\rangle$ stato. Ad esempio con $a = 3$ e $N = 35$ :

Quindi 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 stati propri di $M_a$. (Esistono altri stati propri oltre a questi. Ma a noi interessano solo quelli della forma sopra indicata.)

Verifica la tua comprensione

Trova uno stato proprio 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 stati propri che ci interessano saranno una sovrapposizione uguale di tutti gli stati che sono stati ciclicamente ripetuti 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 essere riusciti a inizializzare lo stato del nostro qubit in uno di questi stati propri (spoiler: non ci siamo riusciti). O almeno, non facilmente. Spiegheremo tra poco perché e cosa possiamo fare invece). Quindi potremmo usare QPE per stimare l'autovalore corrispondente, $\omega_j = e^{2 \pi i \theta_j}$ dove $\theta_j = \frac{j}{r}$. Quindi, saremo in grado di determinare l'ordine $r$ tramite la semplice equazione:

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

Ma ricordate, ho detto che si tratta di stime QPE $\theta_j$ — non ci forniscono un valore esatto. Abbiamo bisogno che la stima sia sufficientemente accurata da poter distinguere tra $r$ e $r+1$. Maggiore è il numero di qubit di controllo a nostra $m$ disposizione, migliore sarà la stima. Nei problemi alla fine della lezione, ti verrà chiesto di determinare il minimo $m$ necessario per scomporre un numero $N$.

Ora dobbiamo risolvere un problema. Tutte le spiegazioni sopra riportate su come trovare $r$ iniziano con la preparazione dello stato proprio $|\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 sapere già cosa $r$ sia. La logica è circolare. Abbiamo bisogno di un modo per stimare l'autovalore senza inizializzare lo stato proprio.

Invece di iniziare con uno stato proprio di $M_a$, possiamo preparare lo stato iniziale nello stato $n$ a -qubit corrispondente a $|1\rangle$ in binario (come in ) $|000...01\rangle$. Sebbene questo stato non sia ovviamente uno stato proprio di $M_a$, è una sovrapposizione di tutti gli stati propri $|\psi_k\rangle$ :

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

Verifica la tua comprensione

Verifica che $|1\rangle$ sia equivalente alla sovrapposizione sugli stati propri che hai trovato per $N=15$ e $a=2$ nella domanda di controllo precedente.

• Risposta

  I quattro stati propri 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}$$

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

Implementare in Qiskit

Come abbiamo detto prima, il nostro hardware non è ancora in grado di elaborare numeri enormi come RSA1024. Facciamo solo un piccolo calcolo per dimostrare come funziona l'algoritmo. Per questa demo, useremo una versione semplificata del codice presentato nel tutorial sull'algoritmo di Shor. Per ulteriori dettagli, consulta il tutorial.

Eseguiremo l'algoritmo utilizzando il nostro framework standard per la risoluzione di problemi quantistici, chiamato Qiskit patterns framework. Si tratta di quattro passaggi:

1. Mappare il problema su un circuito quantistico
2. Ottimizzare il circuito da eseguire su hardware quantistico
3. Esegui il tuo circuito sul computer quantistico
4. Post-elaborazione delle misurazioni

1. Mappa

Facciamo il fattorizzazione $N=15$, scegliendo $a=2$ come nostro numero intero coprimo.

In primo luogo, dobbiamo costruire il circuito che implementerà l'unità di moltiplicazione modulare. $M_a$ Questa è in realtà la parte più complessa dell'intera implementazione e può essere molto onerosa dal punto di vista computazionale, a seconda di come viene eseguita. Per questo, bareremo un po': sappiamo che stiamo iniziando dallo stato $|1\rangle$, e da una domanda precedente,

Quindi, costruiremo un'unità che esegua le operazioni corrette su questi quattro stati, ma lasci tutti gli altri stati invariati. Questo è un imbroglio perché stiamo usando la nostra conoscenza dell'ordine di $2\bmod 15$ per semplificare l'unitario. Se stessimo effettivamente cercando di scomporre un numero i cui fattori ci sono sconosciuti, non saremmo in grado di farlo.

Verifica la tua comprensione

Conoscendo il modo in cui $M_2$ l'operatore trasforma gli stati sopra indicati, costruisci l'operatore a partire da una serie di porte SWAP, che scambiano gli stati di due qubit. (Suggerimento: scrivere ogni stato $|i\rangle$ in binario ti aiuterà.)

• 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 eseguita con un semplice SWAP. $M_2|0001\rangle$ si ottiene scambiando gli stati dei qubit $0$ e $1$. $M_2|0010\rangle$ si ottiene scambiando gli stati dei qubit $1$ e $2$. E così via. Quindi, possiamo scomporre la $M_2$ matrice nella seguente serie di porte 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}$$

Ora possiamo codificare 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

Quindi, creiamo $M_2$ l'operatore:

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)

Output:

L'algoritmo QPE utilizza un gate $U$ controllato. Quindi, ora che abbiamo un $M_2$ circuito, dobbiamo renderlo un circuito $M_2$* controllato* :

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)

Output:

Ora abbiamo il nostro gate $U$ controllato. Ma per eseguire l'algoritmo di stima della fase quantistica, avremo bisogno di controllato- $U^2$, controllato- $U^4$, fino a controllato- $U^{2^{m-1}}$, dove $m$ è il numero di qubit utilizzati per stimare la fase. Più qubit ci sono, più precisa sarà la stima della fase. Utilizzeremo qubit $m=8$ di controllo per la nostra procedura di stima di fase. Quindi, abbiamo bisogno di:

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)

Output:

[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à. Quindi, dobbiamo solo costruire un'altra matrice, $M_4.$

Nota: questa semplificazione funziona solo qui perché l'ordine di $2 \bmod 15$ è $4$. Una volta che $k=2$ (quindi $2^k = 4$ ), ogni potenza successiva dell'operatore è l'identità. In generale, per numeri più grandi $N$ o scelte diverse di $a$, non è possibile saltare la costruzione delle potenze superiori. Questo è uno dei motivi per cui questo è considerato un esempio banale : 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)

Output:

E come prima, lo rendiamo un operatore $M_4$* controllato* :

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)

Output:

Ora possiamo mettere tutto insieme per trovare l'ordine di $2\bmod 15$ con un circuito quantistico, utilizzando la stima di 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)

Output:

2. Ottimizzare

Ora che abbiamo mappato il nostro circuito, il passo successivo è ottimizzarlo per poterlo eseguire su un particolare computer quantistico. Per prima cosa dobbiamo caricare il backend.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Se non hai tempo disponibile sul tuo account o desideri utilizzare un simulatore per qualsiasi motivo, puoi eseguire la cella sottostante per configurare un simulatore che imiterà il dispositivo quantistico 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)

Output:

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

3. Eseguire

# 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))

Output:

Vediamo quattro picchi evidenti a 00000000, 01000000, 10000000 e 11000000, con alcuni conteggi in altre stringhe di bit dovuti al rumore nel computer quantistico. Ignoreremo questi e manterremo solo i quattro dominanti imponendo una soglia: solo i conteggi superiori a questa soglia saranno considerati un segnale reale 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 eseguito in modo classico. Quindi, inseriremo il resto nella fase di "post-elaborazione", dopo aver ottenuto le nostre misurazioni dal computer quantistico. Ciascuna delle misurazioni sopra riportate può essere convertita in numeri interi che, dopo averli divisi per $2^m$, costituiscono le nostre approssimazioni per $\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} ***")

Output:

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 completato il modulo, potresti rimanere colpito da un nuovo apprezzamento per la genialità di Peter Shor, che ha ideato un algoritmo così ingegnoso. Ma speriamo che anche voi abbiate raggiunto un nuovo livello di comprensione della sua semplicità ingannevole. Sebbene l'algoritmo possa sembrare incredibilmente (o intimidatoriamente) complesso, se lo scomponi in ogni singolo passaggio logico e lo esegui lentamente, anche tu sarai in grado di eseguire l'algoritmo di Shor.

Sebbene siamo ancora lontani dall'utilizzare questo algoritmo per scomporre numeri come RSA1024, i nostri computer quantistici migliorano ogni giorno e, una volta raggiunta una soglia chiamata tolleranza ai guasti, algoritmi come questi saranno presto disponibili. È un momento entusiasmante per imparare qualcosa sul quantum computing!

Problemi

Concetti fondamentali:

• I moderni sistemi crittografici si basano sulla classica difficoltà di scomporre grandi numeri interi in fattori primi.
• L'aritmetica modulare — comprese le strutture $\mathbb{Z}_N$ e $\mathbb{Z}_N^*$ — fornisce le basi matematiche per l'algoritmo di Shor.
• Il problema della fattorizzazione di un numero intero $N$ può essere ridotto 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 quindi calcola in modo classico i fattori dal risultato.

Vero/Falso:

1. Vero/Falso L'efficienza dell'algoritmo di Shor minaccia la sicurezza della crittografia RSA.
2. Vero/Falso L'algoritmo di Shor può essere eseguito in modo efficiente su qualsiasi computer quantistico moderno.
3. T/F L'algoritmo di Shor utilizza la stima della fase quantistica (QPE) come subroutine chiave.
4. Vero/Falso La parte classica dell'algoritmo di Shor prevede il calcolo del massimo comune divisore (MCD).
5. Vero/Falso L'algoritmo di Shor funziona solo per la fattorizzazione dei numeri pari.
6. Vero/Falso 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 scomporre un numero nell'algoritmo di Shor?

Problemi di sfida:

1. Quanti qubit di controllo $m$ sono necessari per un dato numero $N$ che si sta cercando di scomporre per ottenere la precisione nel QPE necessaria per trovare il valore corretto dell'ordine $r$?

2. Seguendo la procedura che abbiamo descritto qui per scomporre il 15, ora prova a scomporre il 21.