Indice

1 Introduzione 3

2 Descrizione dei sistemi quantistici 42.1 Richiami di Algebra Lineare . . . . . . . . . . . . . . . . . . . 42.2 I Postulati della Meccanica Quantistica . . . . . . . . . . . . . 6

2.2.1 Definizione . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.2 Evoluzione . . . . . . . . . . . . . . . . . . . . . . . . . 62.2.3 Misurazione di osservabili quantistiche e riduzione del

pacchetto donda . . . . . . . . . . . . . . . . . . . . . 62.2.4 Composizione . . . . . . . . . . . . . . . . . . . . . . . 7

3 Il Qubit 83.1 Rappresentazione . . . . . . . . . . . . . . . . . . . . . . . . . 8

3.1.1 Sistemi a un qubit . . . . . . . . . . . . . . . . . . . . 83.1.2 Sistemi a n Qubit . . . . . . . . . . . . . . . . . . . . . 93.1.3 Rappresentazione vettoriale della base computazionale

estesa . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.1.4 Rappresentazione della base computazionale estesa at-

traverso lo sviluppo binario . . . . . . . . . . . . . . . 103.2 Stati Entangled . . . . . . . . . . . . . . . . . . . . . . . . . . 113.3 Operatori a singolo bit . . . . . . . . . . . . . . . . . . . . . . 11

3.3.1 Identita` . . . . . . . . . . . . . . . . . . . . . . . . . . 123.3.2 Negazione . . . . . . . . . . . . . . . . . . . . . . . . . 123.3.3 Shift di fase . . . . . . . . . . . . . . . . . . . . . . . . 133.3.4 Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . 133.3.5 Operatore pi/8 . . . . . . . . . . . . . . . . . . . . . . . 13

3.4 Operatori a n bit . . . . . . . . . . . . . . . . . . . . . . . . . 143.4.1 CNOT . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.4.2 Hadamard a n qubit . . . . . . . . . . . . . . . . . . . 143.4.3 Operatore di Fredkin . . . . . . . . . . . . . . . . . . . 153.4.4 Operatori entangling . . . . . . . . . . . . . . . . . . . 15

1

3.4.5 Proiezione . . . . . . . . . . . . . . . . . . . . . . . . . 153.5 Operatori di Toffoli ed operatori reversibili . . . . . . . . . . . 163.6 Porte quantistiche universali . . . . . . . . . . . . . . . . . . . 163.7 Misurazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4 Trasformata di Fourier 194.1 Trasformata quantistica . . . . . . . . . . . . . . . . . . . . . 19

4.1.1 Implementazione . . . . . . . . . . . . . . . . . . . . . 204.1.2 Costi e complessita` . . . . . . . . . . . . . . . . . . . . 22

5 Fattorizzazione classica 235.1 Brute force . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235.2 Metodo di Fermat . . . . . . . . . . . . . . . . . . . . . . . . . 245.3 Metodo delle curve ellittiche . . . . . . . . . . . . . . . . . . . 255.4 Number Field Sieve . . . . . . . . . . . . . . . . . . . . . . . . 25

6 Algoritmo di Shor 276.1 Order finding . . . . . . . . . . . . . . . . . . . . . . . . . . . 276.2 Panoramica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286.3 Probabilita` di successo . . . . . . . . . . . . . . . . . . . . . . 296.4 Algoritmo di Euclide . . . . . . . . . . . . . . . . . . . . . . . 316.5 Order finding su un calcolatore quantistico . . . . . . . . . . . 316.6 Metodo delle frazioni continue . . . . . . . . . . . . . . . . . . 336.7 Complessita` . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

6.7.1 Probabilita` di terminazione . . . . . . . . . . . . . . . 346.7.2 Costo di una singola iterazione dellalgoritmo . . . . . 36

6.8 Esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

2

Capitolo 1

Introduzione

Oggigiorno vengono eseguite miliardi di transazioni via internet in cui ven-gono scambiati dati di ogni genere, tra cui dati personali e riservati. Questetransazioni sono sicure? e se lo sono ora, lo saranno anche in futuro? Gliattuali metodi crittografici si basano quasi esclusivamente sulla difficolta` diinvertire alcune funzioni, con cui sono stati cifrati i dati da inviare. Perinvertire i calcoli di queste funzioni e` necessaria una potenza di calcolo mo-struosa che non e` quasi alla portata di nessuno. Dato che i nostri calcolatoridiventano sempre piu` veloci secondo una legge esponenziale, ovvero la leggedi Moore, anche i metodi crittografici diventano sempre piu` complessi. Finoad oggi la crittografia e` riuscita a mantenere il passo in modo tale che la po-tenza di calcolo non fosse mai sufficiente a decrittare i suoi messaggi. Cosasuccederebbe se invece venisse creato un algoritmo capace di decifrare talimessaggi in tempi brevi senza avere bisogno di enormi potenze computazio-nali? Ovvero un algoritmo che potrebbe funzionare tranquillamente su uncomputer di fascia bassa che ormai si trova in ogni casa?Da alcuni anni si e` iniziato a parlare di Calcolatori Quantistici, ovvero com-puter che per il loro funzionamento si basano su bit quantistici, detti ancheQubit. Il vantaggio di tali calcolatori e` che riescono a creare un parallelismonei calcoli fino ad ora mai visto portando alla scoperta di nuovi e interessantialgoritmi per la risoluzione dei problemi piu` comuni quali ricerca e ordina-mento. Tra i tanti algoritmi e` ne e` comparso uno che e` riuscito a mostrarele deboleze dei nostri attuali metodi crittografici. Tale algoritmo si chiamaAlgoritmo di Shor.La peculiarita` di tale algoritmo e` la capacita` di poter facilmente fattoriz-zare un numero molto grande, problema irrisolto da millenni. Il metodo dicrittografia piu` usato, ovvero lRSA si basa proprio sulla difficolta` di po-ter fattorizzare un numero velocemente. Se fossimo in grado di costruirecalcolatori quantistici anche piuttosto semplici potremmo quindi decifrare i

3

messaggi che viaggiano sul web ottenendo una quantita` infinita di informa-zioni private. Fortunatamente o sfortunatamente, a seconda del punto divista adottato, tali calcolatori sono ancora in uno stato larvale e servirannoancora diversi anni prima di poter avere un calcolatore quantistico capace difattorizzare i numeri usati nella crittografia RSA. Inoltre non si e` nemmenosicuri di poter costruire calcolatori quantistici sufficientemente potenti, datoche esistono molti problemi a livello di implementazione fisica. Sono staticostruiti dei primi modelli di calcolatori quantistici a poche decine di qubitsu cui e` stato testato lalgoritmo di Shor con successo.

4

Capitolo 2

Descrizione dei sistemiquantistici

2.1 Richiami di Algebra Lineare

Definizione 2.1 (Spazio di Hilbert). Uno spazio di Hilbert e` una coppia(H, < , >) dove H e` uno spazio vettoriale complesso e < , > e` unprodotto scalare (o una forma hermitiana) su H, tale che, detta d la distanzada esso indotta su H, lo spazio metrico (H, d) sia completo.Definizione 2.2 (Autovettori e Autovalori). Sia A : H H un operatorelineare. Un vettore |v 6= 0 H si dice autovettore di A se A |v = |v,dove e` un numero complesso detto autovalore di |v.Definizione 2.3 (Operatori Aggiunti). Sia A : H H un operatore lineare.Allora esiste un unico operatore A su H, detto operatore aggiunto di A, taleche

|v , |w C |v | A |w = A |v | |wSe loperatore A e` Hermitiano o autoaggiunto, cioe` coincide con il suo

aggiuntoA = A, (2.1)

allora ogni autovalore R.Definizione 2.4 (Operatori Normali). Un operatore A : H H si dicenormale se commuta con il suo aggiunto, ovvero se:

AA = AA

Teorema 2.1.1 (Teorema Spettrale). Un operatore A e` diagonalizzabile see solo se e` normale.

5

Definizione 2.5 (Operatori unitari fra spazi di Hilbert). Un operatoreU : H H si dice unitario se

U U = I. (2.2)

Si osserva che lapplicazione di un operatore unitario U ad un vettore inuno spazio di Hilbert ne lascia invariata la sua norma.

Definizione 2.6 (a - Prodotto Tensoriale ). Siano V e W spazi vettorialicomplessi di dimensioni finite, m e n, rispettivamente. Si definisce prodottotensoriale lo spazio vettoriale complesso nm-dimensionale K = V W (silegga V tensore W ), i cui elementi sono combinazioni lineari, a coefficienticomplessi, dei simboli |v |w con |v V e |w W e per cui valgono leseguenti relazioni:

1. Per un arbitrario scalare z C, |v V e |w W ,

z(|v |w) = (z |v) |w = |v (z |w)

2. Per |v1 , |v2 V e |w W ,

(|v1+ |v2) |w = |v1 |w+ |v2 |w

3. Per |v V e |w1 , |w2 W ,

|v (|w1+ |w2) = |v |w1+ |v |w2

Una definizione piu` intuitiva del prodotto tensoriale e` la seguente:

Definizione 2.7 (b - Prodotto Tensoriale ). Siano V e W spazi vettoriali conbasi rispettivamente {v1, v2, . . . , vm}, {w1, w2, . . . , wn}. Si definisce V W lospazio vettoriale K che ha come basi vi wj i m, j nDefinizione 2.8 (Prodotto Tensoriale tra operatori). Sia f : V V eg : W W operatori lineari tra spazi vettoriali. Si definisce

f g : V W V W |v1 |w1 7 |f(v1) |g(w1)

Nel caso in cui V e V siano spazi di Hilbert, allora f g e` unitario se fe g sono unitari a loro volta.

6

2.2 I Postulati della Meccanica Quantistica

2.2.1 Definizione

Postulato 1. Lo spazio degli stati di un sistema fisico S e` uno spazio diHilbert complesso HS . Lo stato del sistema fisico S al tempo t e` descrittounivocamente da un vettore di stato |(t) H : (t) = 1, con H spaziodi Hilbert. Due vettori di stato si dicono equivalenti se appartengono allastessa classe di equivalenza rispetto alla relazione :

v v C : v = v v, v H/ {0}

Quindi due vettori di stato descrivono lo stesso stato se e solo se sonouguali o differiscono a meno di una fase, che equivale alla moltiplicazione perei con R.

2.2.2 Evoluzione

Postulato 2. In un sistema quantistico isolato S, la transizione da uno stato|(t1) a uno stato |(t2) avviene tramite un operatore unitario U(t2, t1)dipendente solamente dal sistema S e dai due istanti di tempo (t1, t2)

|(t2) = U(t2, t1) |(t1)

In modo analogo e` del tutto equivalente affermare che il sistema evolva se-condo lequazione di Schrodinger

i~d

dt|(t) = H |(t) (2.3)

dove H e` un operatore autoaggiunto noto come Hamiltoniana del sistema e~ h/2pi, con h costante di Planc. La relazione fra loperatore unitariodevoluzione U(t1, t2) e lhamiltoniana H e` data da U(t2, t1) = e

iH(t2t1).

Dato che la equazione di Schrodinger e` lineare vale il principio di sovrap-posizione degli effetti.

2.2.3 Misurazione di osservabili quantistiche e riduzio-ne del pacchetto donda

Postulato 3. a - Osservabili e misurazioni - Un osservabile quantisti-ca di un sistema S e` descritta da un operatore autoaggiunto A sullo spazio

7

di Hilbert HS associato al sistema. Gli unici risultati possibili di una mi-surazione dellosservabile A sono gli autovalori (reali) delloperatore A. Piu`precisamente, se consideriamo lequazione agli autovalori per A

A |i = ai |i (2.4)dove |i e` una base ortonormale di autovettori delloperatore A ed espandiamoil vettore di stato in questa base

|(t) =i

ci(t) |i , (2.5)

allora la probabilita` che una misura dellosservabile A al tempo t forniscarisultato ai e` data da

pi(t) = p(a = ai|t) = | i|(t) |2 = |ci(t)|2 (2.6)b - Riduzione del pacchetto donda - Inoltre, se allistante t0 un sistemasi trova nello stato |(t0) e si misura un osservabile A, ottenendo risultatoai, allora immediatamente dopo la misurazione lo stato del sistema e` datoda:

Pi |(t0)(t0)|Pi |(t0) , (2.7)dove Pi e` loperatore di proiezione sul sottospazio corrispondente allautova-lore ai.

Dato che il vettore | ha norma unitaria, coerentemente con la defini-zione di probabilita`, abbiamo:

i

pi(t) =i

|ci(t)|2 = 1

2.2.4 Composizione

Postulato 4. Lo spazio degli stati di un sistema fisico S formato dai sotto-sistemi S1,S2, . . . ,Sn e` dato dal prodotto tensoriale degli spazi degli stati deisistemi fisici che lo compongono:

HS = HS1 HS2 HSnE utile notare che che se H = H1 H2 allora esistono vettori (e quindi

vettori di stato) che non si possono scrivere nella forma decomposta |v =|v1 |v2 con |Vi Hi. Tali stati prendono il nome di stati Entangled.Questo argomento verra` ridiscusso in modo piu` approfondito in seguito.

8

Capitolo 3

Il Qubit

Classicamente un singolo bit di informazione puo` assumere i due valori 0 o 1.In sistemi quantistici questa rappresentazione non e` piu` sufficiente in quantoun singolo qubit puo` assumere contemporaneamente i valori 0 e 1. Quandoun qubit si trova in un tale stato si dice che esso e` in una sovrapposizionedi 0 e 1. Questa e` la caratteristica fisica che permette un grande speedupcomputazionale, ma che pone grandi problemi tecnologici in quanto lo statodi un sistema di qubit e` estremamente fragile. Per risolvere questi problemisono state intraprese due differenti soluzioni:

1. Cercare di rendere lo stato di un qubit il piu` stabile possibile, riducendole interazioni con lambiente, attraverso mezzi tecnologici avanzati qualiEPR o ION TRAP.

2. Cercare di costruire sistemi tolleranti agli errori usando metodi dicorrezione.

Queste nozioni verranno ripresentate nei prossimi paragrafi in modo piu`dettagliato.

3.1 Rappresentazione

3.1.1 Sistemi a un qubit

Come garantito dal primo postulato della meccanica quantistica e` possibilerappresentare lo stato di un qubit attraverso un vettore | C2. Questovettore e` della forma | = |1 + |2, con , C : ||2 + ||2 = 1 e|1 , |2 ortonormali. Nel nostro caso verranno scelti come vettori ortonor-mali |0 e |1 in analogia ai bit della computazione classica, ma e` possibile

9

scegliere qualsiasi altra coppia di vettori ortonormali in uno spazio di Hilbert.Questi due vettori possono essere rappresentati nel seguente modo:

|0 =[

10

](3.1)

|1 =[

01

]. (3.2)

Con questa base, detta base computazionale, e` possibile rappresentare ognistato di un singolo qubit come combinazione lineare di questi due vettori:| = |0+ |1 , C

3.1.2 Sistemi a n Qubit

Un sistema con n qubit puo` essere rappresentato sempre attraverso un vet-tore, in una nuova base ottenuta tramite il prodotto tensoriale fra le basi deisingoli Qubit. Se chiamiamo H lo spazio di Hilbert di un sistema a un qubit,allora grazie al postulato della composizione e` possibile descrivere lo spaziodegli stati di un sistema a n qubit come nH. Nel nostro caso avendo sceltoper ogni Qubit la base |0 , |1 otteniamo che un generico vettore | puo`essere scritto come:

| = ( |0+ |1) (2 |0+ 2 |1) (n |0+ n |1)che per comodita` di notazione scriveremo come:

| = 1 |0000000 . . . 0+ 2 |0000000 . . . 1+ + n |1111111 . . . 1Questi nuovi vettori rappresentano una base per lo spazio n-dimensionale delsistema chiamata base computazionale estesa dove i1i2 . . . in| | := i1| | in| |.

3.1.3 Rappresentazione vettoriale della base computa-zionale estesa

E possibile rappresentare n qubits introducendo un isomorfismo fra (C2)ne C2n , detto rappresentazione vettoriale, nel seguente modo ricorsivo.

Per un sistema a due qubit |a e |b:

|a |b =[a1a2

][b1b2

]

a1 b1a1 b2a2 b1a2 b2

, (3.3)10

ed essendo poi |c lo stato di un sistema a (n1) qubits (quindi, un elementodi Hn1 isomorfo, per induzione, a C2n1) e |d un singolo qubit si puo`scrivere il vettore 2n dimensionale che rappresenta uno stato in Hn come

|c |d =

c1c2...

cn1

[d1d2

]

c1 d1c1 d2

...cn1 d1cn1 d2

. (3.4)Si prendano ad esempio due qubit nello stato |0, il sistema da essi

composto ha una rappresentazione in C4 cos` definita

|0 |0 =[

10

][

10

]

1000

; (3.5)e componendo il sistema ottenuto con un terzo qubit nello stato |1 si ottiene

|0 |0 |1

1000

[ 01]

01000000

. (3.6)

3.1.4 Rappresentazione della base computazionale este-sa attraverso lo sviluppo binario

Una rappresentazione piu` compatta si puo` ottenere notando che qualsiasivettore della base computazionale estesa puo` essere interpretato come unnumero binario nel seguente modo:

|0 := |00 . . . 0 := |0 |0 |0|1 := |0 . . . 01 := |0 |0 |1|2 := |0 . . . 10 := |0 |1 |0.

.

.

|2n 1 := |11 . . . 1 := |1 |1 |1 ,

11

Grazie a questo accorgimento possiamo riscrivere un vettore generico | nelseguente modo:

| =2n1i=0

ci |i (3.7)

con la condizione di normalizzazione

2n1i=0

|ci|2 = 1

Questa notazione verra` ripresa in seguito per rappresentare in modo compat-to la trasformata quantistica di Fourier.

3.2 Stati Entangled

Grazie alle notazioni acquisite e` possibile esprimere ogni vettore di statotramite gli stati dei singoli qubit nel sistema. Esistono pero` alcuni stati nonesprimibili in tale modo;vediamo un esempio: lo stato

|00+ |11 , = = 12

non puo` essere rappresentato come prodotto tensoriale di due qubits:

1 |0+ 1 |1), (2 |0+ 2 |1)

Questo accade poiche`:

(1 |0+ 1 |1) (2 |0+ 2 |1) = |00+ |11

(1 |0+1 |1)(2 |0+2 |1) = 11 |00+12 |01+21 |10+22 |11ma in questo caso 12 = 0 implica che 12 = 0 oppure 12 = 0 e quindinon e` possibile scomporre lo stato iniziale.

3.3 Operatori a singolo bit

Come nei calcolatori classici esistono delle porte logiche quantistiche per po-ter eseguire le operazioni classiche della logica proposizionale quali AND,NOTe OR. Verranno qui presentate le piu` comuni e quelle che servono per la corret-ta comprensione dellalgoritmo di Shor presentato in seguito. E importante

12

notare che tutte le porte logiche quantistiche eseguono azioni reversibili datoche vogliamo mantenere i vettori di stato di norma unitaria. Si consideri unqubit nello stato

| = a |0+ b |1 a, b C, |a|2 + |b|2 = 1,

unoperazione su di esso , per esempio lazione di una porta quantistica,deveessere intesa come evoluzione del sistema quantistico qubit e pertanto (comeindicato dal secondo postulato) rappresentata da una matrice U , 22, taleche

U U = I,

condizione che ne esprime lunitarieta`.

3.3.1 Identita`

Questa risulta loperatore piu` semplice in quanto restituisce in uscita il qubitricevuto in ingresso.

I : |0 |0|1 |1

Loperatore puo` essere espresso in forma matriciale nel seguente modo:

I =

[1 00 1

]

3.3.2 Negazione

Questo operatore riproduce in uscita il singolo qubit in ingresso negato.

X : |0 |1

|1 |0Loperatore puo` essere espresso in forma matriciale nel seguente modo:

X =

[0 11 0

]

13

3.3.3 Shift di fase

Questo operatore ruota di pi2

la fase del qubit in ingresso.

Z : |0 |0

|1 |1Loperatore puo` essere espresso in forma matriciale nel seguente modo:

Z =

[1 00 1

]

3.3.4 Hadamard

Questo operatore porta un singolo qubit in una sovrapposizione di |0 e |1.Tale caratteristica lo rende ampiamente usato nella costruzione di circuiti incalcolatori quantistici.

H |0 = 12

(|0+ |1) |+ , (3.8)

H |1 = 12

(|0 |1) | . (3.9)

Nei circuiti viene rappresentato nel seguente modo:

Figura 3.1: Porta di Hadamard

3.3.5 Operatore pi/8

Tale operatore prende il suo nome dal fatto che puo` essere scritto nellaseguente forma:

T = eipi/8[eipi/8 0

0 eipi/8

]. (3.10)

Espresso in notazione matriciale avremo il seguente risultato:

T =

[1 00 eipi/4

]. (3.11)

14

3.4 Operatori a n bit

3.4.1 CNOT

Il comportamento della porta Controlled-not e` il seguente:

CNOT (|x |y) = |x |x yE possibile rappresentare, utilizzando la base introdotta precedentemente,tale operatore nella seguente forma matriciale:

CNOT =

1 0 0 00 1 0 00 0 0 10 0 1 0

.Si puo` facilmente notare, come gia` evidenziato precedentemente, che tale ope-ratore e` reversibile. Il primo qubit viene spesso definito bit di controllo, men-tre il secondo prende il nome di bit bersaglio. Nei circuiti viene rappresentatonel seguente modo:

Figura 3.2: Porta CNOT

3.4.2 Hadamard a n qubit

Loperatore Hadamard a un qubit precedentemente visto puo` essere facilmen-te esteso a n qubit, utilizzando la notazione binaria precedentemente vista,nel seguente modo:

(H H H) |000 . . . 0 =12n

((|0+ |1) (|0+ |1) (|0+ |1)) =

12n

2n1x=0

|x

E importante notare come questo operatore, applicato a n qubit, generi unasovrapposizione di tutti gli 2n 1 stati possibili.

15

3.4.3 Operatore di Fredkin

Loperatore S, detto operatore di Fredkin(o switch), applicato a due qubitscambia lo stato di essi nel seguente modo:

|a |b |a |a b |a (a b) |a b = |b |a b |b |(a b) b = |b |a , (3.12)

Si nota quindi che esso e` implementabile attravero la applicazione di treporte CNOT consecutivamente.

3.4.4 Operatori entangling

Definizione 3.1 (Operatore Entangling). Un operatore unitario a due qubit

V : C2 C2 C2 C2

si dice entangling, cioe` capace di generare il fenomeno dellentanglement seesistono |u , |v H ' C2 tali che

V (|u |v),

non e` decomponibile, cioe` non puo` essere scritto nella forma

|u |v .

3.4.5 Proiezione

Dato un vettore di stato | = ( |x1 + 2 |x2 + + n |xn) H, sidefinisce loperatore di proiezione P sul sottospazio H0 H,di dimensionem come:

P : ( |x1+2 |x2+ +n |xn) ( |x1+2 |x2+ +0 |xi+ +0 |xi+mn+ +n |xn)

ovvero tale operatore annulla m n componenti del vettore |. Inoltre taleoperatore risulta autoaggiunto tenendo conto che H = H0 H0, in quanto:

< w,Pv >=< w0+w0, v0 >=< w0, v0 >=< w0, v0+v0 >=< w0, v >=< Pw, v >

(3.13)Grazie a questo fatto questo operatore puo` essere realizzato fisicamente.

16

3.5 Operatori di Toffoli ed operatori reversi-

bili

Gli operatori visti in precedenza sono tutti reversibili e facilmente compa-rabili agli operatori della logica classica. E importante notare che tutti glioperatori quantistici sono per loro natura reversibili; viene quindi spontaneala domanda se sia possibile esprimere ogni funzione logica classica attraversooperatori quantistici. E facile osservare che nella logica classica esistono deglioperatori non reversibili come lo XOR o il NAND. Ad esempio lo XOR clas-sico viene quantisticamente simulato attraverso lutilizzo della porta CNOTnella base computazionale proiettato sul qubit bersaglio. In generale abbia-mo che si possono simulare tutte le porte logiche classiche su circuiti quan-tistici mediante operatori particolari e proiezioni. Un importante strumentomediante il quale ogni circuito classico puo` essere implementato con portequantistiche e` la porta di Toffoli. Tale operatore ha tre qubits in input, dicui due utilizzati come qubits di controllo e un terzo come bersaglio:

|a |b |c |a |b |c ab a, b, c {0, 1}. (3.14)A seconda degli input la porta di Toffoli puo` simulare svariate porte classicheirreversibili. Si parla di simulazione perche` loperatore non realizza esatta-mente la funzione corrispondente ma una analoga in versione quantistica.Tale operatore viene rappresentato nel seguente modo:

Figura 3.3: Toffoli gate

3.6 Porte quantistiche universali

Una caratteristica molto importante dei calcolatori classici e` lesistenza diinsiemi di porte logiche che possono essere utilizzate per comporre qualsiasifunzione (ad esempio linsieme composto da AND, OR e NOT), questi insiemisono chiamati universali. Vogliamo mostrare che un concetto analogo esisteanche nel campo dei calcolatori quantistici; definiamo intanto

Definizione 3.2. (Insiemi universali)1. Un insieme di porte logiche classiche (rispettivamente, quantistiche) G si

17

dice strettamente universale se ogni porta logica classica (rispettivamente,quantistica) U ad un numero arbitrario di bits (rispettivamente, di qubits),si scrive come composizione di un numero finito (dipendente da U) di portein G.2. Un insieme di porte logiche quantistiche G si dice universale se per ogniporta logica quantistica ad un numero arbitario di qubits, cioe` per ogni ope-ratore unitario U di CN , con N intero positivo arbitario, e per ogni > 0esiste un numero finito G1, G2, ..., Gn di operatori unitari in G tali che

||U G1G2 Gn|| < .Nella definizione precedente

||F || := sup{|F (u)| |u CN , |u| = 1}, per ogni operatore lineareF : CN CN ; se G e` una porta (operatore) in G e G opera su n-bits (o qubits), non

facciamo distinzione tra G e la sua estensione ad una porta (opera-tore) a N bits (o qubits), ottenuta inserendo,in tutti i modi possibili,lidentita` sui restanti (N n) bits (o qubits).

E ben noto che le porte AND, OR e NOT costituiscono un insieme (fi-nito) strettamente universale di porte classiche. Nel caso quantistico, poiche`il gruppo delle matrici unitarie U(N) e` non numerabile, non puo` esistere uninsieme finito strettamente universale di porte logiche quantistiche. E tut-tavia possibile individuare alcuni insiemi finiti, ciascuno universale, di portelogiche quantistiche. Enunciamo intanto il seguente teorema

Teorema 3.6.1 (Brylinsky,brylinsky). Sia

V : C2 C2 C2 C2un operatore a 2 qubits e sia U(C2) linsieme di tutti gli operatori unitariC2 C2. Sia

GV := {V, U(C2)}allora sono fatti equivalenti

GV e` un insieme universale di porte quantistiche GV e` un insieme strettamente universale di porte quantistiche V e` entangling

Corollario 3.6.2. Linsieme GCNOT e` un insieme strettamente universaledi porte quantistiche.

Unaltro insieme universale per il calcolo quantistico e` composto dalleseguenti porte: Hadamard, Shift di fase, CNOT, pi/8;

18

3.7 Misurazione

Come visto in precedenza e` noto che misurare un vettore di stato quantisticoequivale a proiettare tale vettore ssu unautospazio dellosservabile quanti-stica che stiamo misurando. Dopo questa azione il nostro vettore di stato sitrovera` nello stato misurato. Cosa succederebbe se invece volessimo misura-re piu` volte uno stato ignoto del tipo | = |0 + |1? con tale metodoquesto risulta impossibile. Dovremmo eseguire tante copie di tale stato emisurarlo ripetute volte. Questo fatto porta ad un noto teorema che mostrala impossiblita` di clonare uno stato ignoto:

Teorema 3.7.1 (Teorema del No-Cloning). Non e` possibile costruire un di-spositivo quantistico che implementi un operatore lineare unitario che copi ilgenerico stato di un qubit.

Dimostrazione. Supponiamo di avere un operatore lineare U che implementiloperazione di clonazione nel seguente modo: U |x0 = |xx per ogni vettoredi stato |x. In particolare, possiamo prendere due vettori |a e |b :

U |a0 = |aa , U |b0 = |bb a| |b 6= 0 (3.15)consideriamo |c = 1

2(|a+ |b) Per la linearita` di U otteniamo:

U |c0 = 12

(U |a0+ U |b0) = 12

(|aa+ |bb) (3.16)

ma se U clonasse allora

U |c0 = |cc = 12

(|aa+ |ab+ |ba+ |bb) (3.17)

che non risulta uguale a 12(|aa+ |bb).

E importante rimarcare il fatto che si parla di stati ignoti, in quanto unostato noto puo` essere replicato a piacere.

Questo e` un limite intrinseco ai sistemi quantistici che contrasta le grandipotenzialita` computazionali possibili. La maggiore potenzialita` di tali siste-mi deriva dal fatto che se applichiamo un operatore lineare U a uno statoche si trova in una sovrapposizione, allora U verra` applicato a tutti i vettoriche compongono la base di tale stato contemporaneamente, generando unanuova superposizione dello stato di ingresso. Se potessimo misurare tuttele componenti della base avremmo un incremento di prestazioni esponenzia-le, ma come visto in precedenza questo ci risulta impossibile per via dellerestrizioni che ci impone loperazione di misura e di clonazione.

19

Capitolo 4

Trasformata di Fourier

In generale una trasformata di Fourier mappa una funzione nel dominiodel tempo in una funzione nel dominio della frequenza. Esistono diversetrasformate di fourier, ma nel nostro caso useremo le seguenti:

Trasformata di Fourier continua (FT) Trasformata di Fourier discreta (QFT)Nel nostro caso ci interessa la trasformata quantistica di Fourier (QFT)

che risulta molto simile alla trasformata di Fourier discreta. Vediamo primacome funziona la trasformata di fourier discreta: Questo operatore prendein ingresso N campioni xn, associati a una divisione N-regolare di [0, 2pi), diuna funzione e genera una funzione che ha come dominio gli interi tra 0 eN 1. Tale operazione puo` essere schematizzata nel seguente modo:

Xk =N1n=0

xne 2pii

Nkn (4.1)

Se la funzione campionata in ingresso e` periodica di periodo r, allora lafunzione che si ottera` attraverso la DFT avra` valori diversi da 0 solo neimultipli di N

r. Nel caso in cui la funzione in ingresso non sia periodica, la

funzione in uscita approssimera` la funzione in ingresso con valori diversi da0 nelle vicinanze degli interi N

r.

4.1 Trasformata quantistica

La QFT risulta analoga alla DFT precedentemente descritta, con lunicadifferenza che N deve essere una potenza di 2.

x

g(x) |x =c

G(c) |c (4.2)

20

dove G(c) e` la trasformata quantistica di g(x) e x e c sono numeri binarinellintervallo [0, N 1] con N potenza di 2. Se si misura lo stato di unsistema dopo aver applicato la trasformata si avra` come risultato lo stato |ccon probabilita` |G(c)|2. Questo porta al seguente risultato:

c

|G(c)|2 = 1 (4.3)

Se applichiamo la trasformata di Fourier quantistica ad una funzione g(x)periodica di periodo r ci aspettiamo di ottenere

cG(c) |c, con G(c) diver-

so da 0 nei multipli di Nr

. Quindi se misuriamo lo stato ottenuto dovremmoottenere qualcosa del tipo jN

r, con j R. Questo pero` non avviene se non si

ha un periodo multipilo di 2, ovvero che divide N.In generale la trasformata quantistica di Fourier UQFT , con N = 2

m, puo` es-sere espressa nel seguente modo, usando lo sviluppo binario precedentementedescritto:

UQFT : |x 12m

2m1c=0

e2piicx2m |c (4.4)

Maggiore viene scelta la potenza di 2, maggiore sara` la precisione con cui latrasformata approssima la funzione.

4.1.1 Implementazione

Per poter implementare efficentemente la QFT sono necessari due operatori.Il primo e` loperatore di Hadamard, percedentemente descritto. Denoteremocon Hj loperatore di applicato al j-esimo qubit. Il secondo operatore operasu due qubit nel seguente modo:

Rj,k =

1 0 0 00 1 0 00 0 1 00 0 1 eijk

(4.5)con jk = pi2jk . Con questi due operatori e` possibile implementare in modoefficente la trasformata quantistica. Vediamo piu` in dettaglio come sia possi-bile costruire un circuito a partire dagli operatori precedenti che implementa

21

tale trasformata tenendo conto che N = 2m:

|x 7 12m/2

N1c=0

e2piixc/N |c

=1

2m/2

1c1=0

...1

cm=0

e2piix(ml=1 cl2

l) |c1...cm (4.6)

=1

2m/2

1c1=0

...1

cm=0

nl=1

e2piixcl2l |cl (4.7)

=1

2m/2

ml=1

[1

cl=0

e2piixcl2l |cl

](4.8)

=1

2m/2

ml=1

[|0+ 22piix2l |1] (4.9)=

12

(|0+ e2pii0xm |1) 12

(|0+ e2pii0xn1xm |1) . . .

12

(|0+ e2pii0x1x2...xm |1). (4.10)

tenendo conto della notazione:

0x0x1x2 . . . xn =x0

2n+1+x12n

+ + xn2

(4.11)

Si nota dallultimo passaggio come siano sufficienti i due operatori prece-dentemente descritti. Grazie a questa decomposizione e` possibile costruire ilcircuito per calcolare la QFT nel seguente modo:

Figura 4.1: Circuito che realizza la trasformata quantistica di Fourier. Sonoomessi i fattori 1/

2 di normalizzazione.

dove j1 . . . jn sono i singoli qubit. Si deve notare pero` che tale circuitogenera i qubit in ordine inverso e quindi avremo bisogno di uno swap finale

22

per riordinare il nostro risultato.La trasformata quantistica inversa f1(|c) e` data da:

f1(|c) = 12n

2n1k=0

e2piick2n |k (4.12)

4.1.2 Costi e complessita`

Il primo qubit deve attraversare una porta di Hadamard e n 1 shift difase per un totale di n porte. Il secondo qubit deve attraversare una portadi Hadamard e n 1 shift di fase per un totale di n 1 porte. Conti-nuando fino alln-esimo qubit otteniamo che il numero di porte necessarie adimplementare la QFT e`:

n+ (n 1) + + (n n+ 1) = n(n 1)2

(4.13)

Considerando anche il numero, (n), di swap necessari a riordinare il risul-tato otteniamo una complessita` di (n2). Questo risulta gia` un notevoleguadagno dato che lalgoritmo piu` veloce per il calcolo della DFT, ovvero laFast Fourier Transform, ha una complessita` di (2n). E fondamentale no-tare che senza questo risultato non sarebbe possibile ottenere nellalgoritmodi Shor una complessita` minore di quella esponenziale, dato che con la FFTnormale abbiamo gia` una complessita` tale.

23

Capitolo 5

Fattorizzazione classica

Problema (Fattorizzazione in numeri primi). Dato un intero positivo com-posto N , si vuole sapere quali sono i numeri primi che moltiplicati tra lorodiano come risultato N .

Dati due numeri a e b e` molto semplice controllare se essi sono i fattoridi un numero N . Con il miglior algoritmo si ha una complessita` (n1,465..),ma risulta estremamente complicato trovare a e b dato il numero N . Connumeri piccoli tale problema e` facilmente approcciabile, ma quando i numerisuperano le 100 cifre il problema diventa spesso intrattabile. Oggigiornotale fatto viene sruttato in diversi metodi di crittografia quale lRSA, unodei metodi piu` comuni. Se fosse possibile fattorizzare grandi numeri in pocotempo non sarebbe piu` possibile usare tali metodi di crittografia per eseguiretransazioni sicure.

5.1 Brute force

Il metodo forza bruta e` un algoritmo di risoluzione di un problema che con-siste nel verificare tutte le soluzioni teoricamente possibili fino a che si trovaquella effettivamente corretta. Il suo principale fattore positivo e` che con-sente teoricamente sempre di trovare la soluzione corretta, ma per contro e`sempre la soluzione piu` lenta o dispendiosa. In ambito crittografico, avereun algoritmo che puo` essere decifrato solo usando un metodo a forza bruta e`una ottima cosa, in quanto i costi per la decifrazione sono solitamente spro-porzionati. Prendiamo anche il solo semplice esempio di dover trovare unacombinazione di una semplice serratura a combinazione. Supponiamo che cisiano 10 rondelle numerate con i numeri da 0 a 9. In questo caso dovrem-mo provare 1010 combinazioni. Se tentassimo manualmente di forzare taleserratura ci impiegheremmo probabilmente tutta la vita.

24

5.2 Metodo di Fermat

Il metodo di fattorizzazione di Fermat e` un algoritmo ideato da Pierre deFermat per fattorizzare dei numeri interi nei suoi fattori primi. Si basa sullarappresentazione di un numero come differenza di due quadrati, ed e` piu`efficace quando esistono due fattori del numero vicini tra loro. Vediamocome funziona tale algoritmo:

1. Sia n un numero dispari.

2. a = dne.3. Ripeti

(a) b = a2 n.(b) Se b non e` un quadrato perfetto a = a+ 1

4. finche` b non e` un quadrato perfetto.

5. b2 =b.

6. n = (a b)(a+ b).Spiegazione: Supponiamo che n sia un intero dispari, e che esistano due interia e b tali che n = ab (con a > b). Allora

n = (a+ b

2)2 (a b

2)2 (5.1)

Quindi n e` la differenza di due quadrati. Essendo n un intero dispari, anchea e b lo devono essere a loro volta: dunque i numeri d = a+b e c = ab sonopari e la loro semisomma e` un intero. Lespressione d2 c2 puo` quindi esserevista come (d c)(d+ c), e se d 6= c+1, si e` ottenuta una fattorizzazione nonbanale di n.Lalgoritmo consiste quindi nel calcolare i numeri a2 n finche`non si trova un quadrato perfetto; in tal caso

a2 n = b2 a2 b2 = n (5.2)Il calcolo dei quadrati successivi e` inoltre facilitato dal fatto che le differenzetra quadrati consecutivi formano una progressione aritmetica di ragione 2:(a + i)2 (a + i 1)2 = 2a + 2i + 1. Il riconoscimento dei quadrati puo`essere effettuato o attraverso metodi di aritmetica modulare (che eliminamolte possibilita` per i quadrati: ad esempio lultima cifra decimale non puo`essere solo 2, 3, 7 o 8) oppure attraverso apposite tavole dei quadrati. Questoalgoritmo ha un costo di (

n) dove n e` il numero da fattorizzare. Il costo

puo` essere facilmente dedotto dallalgoritmo stesso.

25

5.3 Metodo delle curve ellittiche

Il metodo delle curve ellittiche (ECM) e` un algoritmo di fattorizzazione diordine subesponenziale, ideato da H.W.Lenstra nel 1985. La particolarita` ditale algoritmo e` dovuta al fatto che la sua complessita` dipende fortementedal fattore primo piu` piccolo del numero da fattorizzare e non tanto dallalunghezza n del numero stesso. In termini di prestazioni tale algoritmo siposiziona al terzo posto dopo il Quadratic Sieve e il Number Field Sieve.Risulta ottimo per fattorizzare numeri che hanno fattori di 20-25 cifre, ovveroda 64 a 83 bits. In generale una curva ellittica viene descritta nel seguentemodo

E(Z/nZ) = {(x, y L2(Z/Zn), y2 x3 + ax+ b(modn)} (5.3)dove L2(Z/nZ) e` il piano proiettivo su (Z/nZ), a, b (Z/nZ) e lelementoneutro e` O = (0, 1), detto anche punto allinfinito. Definiamo KP = P +P + + P K volte dove + indica la operazione di somma tra curve ellittiche eP e` un punto su di una curva ellittica. Lalgoritmo si basa sul fatto che datauna curza ellittica y2 x3 + ax + b(modn) con n numero da fattorizzare,possiamo creare due curve ellittiche piu` piccole uguali, ma modulo p e q, conp e q fattori di n. Queste due curve, con una operazione di somma, possonoessere viste come gruppi. Se questi due gruppi hanno rispettivamente Np eNq elementi, allora per ogni punto P della curva di partenza si avra`, per ilteorema di Lagrange,che se KP = inf sulla curva modulo P , allora K divideNp. Utilizzando operazioni su gruppi e` quidi possibile risalire ad un fattorenon banale di n. Verranno tralasciati gli aspetti tecnici di tale metodo per iquali si rimanda a [Lenstra]

5.4 Number Field Sieve

Il Numer Field Sieve e` il piu` efficiente algoritmo classico conosciuto per fat-torizzare gli interi con pid`i 100 cifre. Euristicamente, la sua complessita`computazionale, per fattorizzare un intero n e`

(e(c+o(1))(logn)

13 (log logn)

23

)(5.4)

ove c e` una costante che dipende dalla variante dellalgoritmo utilizzata. IlNumber Field Sieve (sia generale che speciale) puo` essere considerato une-stensione del piu` semplice Rational Sieve. Per fattorizzare un intero granden, questultimo algoritmo ha bisogno di trovare numeri dello stesso ordine din che hanno fattori primi piccoli; la rarita` di questi numeri rende di fatto

26

inutilizzabile il rational sieve. Per ovviare a questo problema, i crivelli deicampi di numeri sposta il problema negli anelli degli interi di alcuni campidi numeri. Questa approccio, pur introducendo alcune complicazioni teori-che, rende sufficiente cercare gli interi con fattori primi piccoli tra i numeridi ordine n1/d, ove d e` un intero maggiore di 1. Dato che i numeri piu` pic-coli hanno generalmente fattori primi piu` piccoli, questa modifica aumentanotevolmente lefficienza del metodo. Si noti che log(n) e` essenzialmente ilnumero di cifre nella rappresentazione binaria di n e di conseguenza, nei casipeggiori, il tempo necessario per compiere una fattorizzazione e` piu` che po-linomiale (nel numero delle cifre). Per i dettagli tecnici di tale algoritmo sirimanda a [?].

27

Capitolo 6

Algoritmo di Shor

Questo algoritmo e` stato ideato per la difficolta` attuale di fattorizzare unnumero qualsiasi in poco tempo. Lo svolgimento puo` essere suddiviso indue fasi: nella prima fase viene mostrato come sia possibile ridurre il pro-blema della fattorizzazione di un numero, al problema di trovare il periododi una data funzione (order finding); nella seconda fase viene mostrato co-me sia possibile calcolare tale periodo efficientemente usando la trasformataquantistica di Fourier su un calcolatore quatistico. Lunico passaggio che de-ve essere implementato su un calcolatore quantistico e` proprio questultimo.Va specificato anche che questo algoritmo ha una natura probabilistica, inquanto il risultato corretto potrebbe non essere ottenuto immediatamente,ma solo dopo alcune esecuzioni del codice. Una volta trovato il periodo del-la funzione bastano alcuni semplici passaggi per determinare una possibilefattorizzazione.

6.1 Order finding

Problema. Siano x e N due interi positivi primi fra loro. Il problemadellorder finding consiste nel trovare il piu` piccolo numero r tale che

xr = 1 mod N. (6.1)

Supponendo che r sia pari, si puo` facilmente trovare un fattore del numeroN , sotto alcune ipotesi, nel seguente modo : Dato m N

mr = 1 mod N (6.2)

mr 1 = 0 mod N (6.3)(mr/2 1)(mr/2 + 1) = 0 mod N. (6.4)

28

(mr/2 1)(mr/2 + 1) = kN (6.5)per qualche intero k.

Se mr/2 = 1 mod N si ha banalmente k = 0.Questa condizione si riduce a mr/2 = 1 mod N poiche` mr/2 = 1 mod Nnon puo` essere vero perche` r e` lordine di m modulo N . Grazie allalgoritmodi Euclide e` possibile calcolare lintero d > 1 dato da d = gcd(mr/21, N) chee` un fattore non banale di N , al piu` si avra` che d = mr/21. Questo semplicealgoritmo verra` mostrato piu` dettagliatamente nel seguente paragrafo. E quiimportante notare che r deve essere un numero pari, altrimenti non e` possibileapplicare la procedura sopra descritta. Questa ipotesi non andra` ad influiresul buon esito dellalgoritmo in quanto cambiando il parametro m e` possibileottenere un nuovo valore di r. Iterando su valori casuali di m sara` facilmentepossibile ottenere r pari molto velocemente come vedremo nel dettaglio inseguito(si veda Sezione 6.3) E importante notare come tale problema sia deltutto equivalente e trovare il periodo r della funzione f(x) = ar mod N ,ovvero il valore di r tale che f(x + r) = f(x). Questo porta infatti allauguaglianza axar = ax mod N che implica ar = 1 mod N .

6.2 Panoramica

Vediamo ora quali sono i principali passaggi dellalgoritmo di Shor. Lo scopoe` quello di trovare un fattore di un numero N dato.

1 Si sceglie casualmente un intero positivo m e si utilizza lalgoritmodi Euclide (che opera in tempo polinomiale) per calcolare il massimocomune divisore fra m e N ; se gcd(m,N) 6= 1, allora abbiamo gia`trovato il fattore non banale, altrimenti si passa al punto 2.

2 Si utilizza un calcolatore quantistico per determinare lordine r dellin-tero m modulo N .

3 Se r e` dispari si torna al punto 1, altrimenti si passa al punto 4.

4 poiche` r e` pari si puo` arrivare alla seguente forma

(mr/2 1)(mr/2 + 1) = kN, k N (6.6)

attraverso i passaggi precedentemente descritti. Se mr/2 = 1 mod Nsi torna al punto 1 (poiche` risulterebbe k = 0), altrimenti si va al punto5. Questa condizione si riduce a mr/2 = 1 mod N dato che mr/2 6= 1mod N poiche` r e` lordine di m modulo N .

29

5 Si usa lalgoritmo di Euclide per calcolare lintero d > 1 dato da d =gcd(mr/21, N) che e` un fattore non banale di N , al piu` d = mr/21.

Il passaggio fondamentale che riduce la complessita` di questo algoritmorisiede nel passaggio numero 4 per il quale e` fondamentale lutilizzo di uncalcolatore quantistico. Si puo` notare che la natura probabilistica dellalgo-ritmo risiede nei passaggi 1 e 2. In seguito verra` analizzata la probabilita` disuccesso dellalgoritmo. Vediamo intanto quale e` la probabilita` di scegliereun m che soddisfi le condizioni richieste e lalgoritmo di euclide utilizzato alpunto 1.

6.3 Probabilita` di successo

Esistono tre fattori che portano lalgoritmo di Shor ad essere un algoritmoprobabilistico. Inizialmente si richiede la scelta di un numero casuale m, cheverra` utilizzato per trovare r, ordine di a rispetto ad N , numero da fatto-rizzare. Lordine di r potrebbe non essere un numero pari, oppure potrebbeessere che m

r2 = 1; in quel caso si dovrebbe ripetere lalgoritmo con un nuo-

vo numero casuale. Il terzo fattore verra` analizzato alla fine dellalgoritmo.Vale il seguente teorema grazie al quale e` possibile stimare la probabilita` disuccesso di tale scelta:

Teorema 6.3.1. Sia N = p11 . . . pkk la fattorizzazione in numeri primi di

un intero positivo dispari. Sia y un intero scelto a caso da ZN e sia r lordinedi y modulo N . Allora

p(r pari e yr/2 6= 1 mod N) 1 12k1

(6.7)

Dimostrazione. Sappiamo che yr 1 mod N e che r e` il piu` piccolo valoreper cui vale questa congruenza. Dato che y

r2 1 mod N e` impossibile

dimostreremo che:

p(r dispari o yr/2 1 mod N) 12k1

. (6.8)

Ora sappiamo che gcd(y, pii) 1, quindi sia ri lordine di y mod pii .

Possiamo quindi affermare che

yri 1 mod pii , i = 1, . . . , k. (6.9)Notare che r = mcm(r1, . . . , rk). Questo deriva dal fatto che y

r 1 mod Nimplica che yr 1 mod pii , dato che r e` un multiplo di ri ed r e` il valorepiu` piccolo che soddisfa tale condizione. Abbiamo anche che

yr2 1 mod N y r2 1 mod pii i (6.10)

30

Limplicazione verso destra e` ovvia dato che ogni pii divideN . Limplicazioneopposta invece si dimsotra grazie al teorema cinese dei resti, ovvero se = y

r2

allora il sistema di congruenze = 1 mod pii ha una unica soluzione = 1 mod N ( per la implicazione precedente). Scriviamo adesso

ri = si2ti , si dispari i (6.11)

dove s = mcm(s1, . . . , sk), t = max(t1, . . . , tk) e r = s2t. Possiamo ora

affermare cheyr2 1 mod pii ti = t (6.12)

Per dimostrare questa affermazione assumiamo che yr2 1 mod pii e che

ti < t. Quindi ri divider2, ma questo e` impossibile poiche` yri 1 mod pii

e yr2 1 mod pii per ipotesi. Inoltre r e` dispari se e solo se ogni ri e`

dispari, cosi che tutti gli ti sono uguali a 0. Dalle considerazioni precedentiotteniamo che

p(r dispari o yr/2 1 mod N) p(tutti gli ti uguali) (6.13)Per maggiorare tale probabilita` utilizziamo che p(tj = j) 12 i, j. Perdimostrare questa affermazione usiamo che il gruppo moltiplicativo modulopii e` ciclico. Gli elementi di tale insieme sono i numeri primi con esso e lacardinalita` di tale insieme e` (pii ).Sia g un generatore di tale gruppo, allora

g(pii ) 1 mod pii (6.14)

per il teorema di Eulero. Scriviamo (pii ) = 2 con dispari. Sempre per

il teorema di Eulero ogni ordine modulo pii divide 2 , quindi ti i.

Sia per ogni b dispari 2 lordine di gh mod pii , . Allora(gb)2

= gb2

= 1 (6.15)

e b e` dispari, quindi = . Ugualmente, se b e` pari, allora gb ha ordine 2

con 1. Quindi, escludendo i casi ovvi di pii = 2, (2) = 1, possiamonotare che ogni valore di puo` comparire al massimo la meta` dei numericoprimi con pii = 2, (2) = 1. Questo dimostra la affermazione precedente.Concludendo abbiamo che

p(tutti gli ti uguali) =j

ki=1

p(ti = j) =j

p(t1 = j) . . . p(tk = j) (6.16)

j

p(t1 = j)1

2k1=

1

2k1(6.17)

Questo ultimo risultato conclude la dimostrazione.

31

E possibile anche mostrare un risultato piu` forte, ovvero che:

p(r pari o xr/2 6= 1 mod N) 12

(6.18)

per tutti gliN che non sono della forma p o 2p, con p primo e N. Questomostra che iterando la scelta casuale di un valore x, si ottiene rapidamenteun valore che soddisfa le condizioni necessarie al buon esito dellalgoritmo diShor.

6.4 Algoritmo di Euclide

Questo algoritmo e` tr i piu` antichi conosciuti, essendo presente negli Elementidi Euclide intorno al 300 a.C Lo scopo e` quello di trovare il massimo comundivisiore (MCD) tra due numeri a e b. Il funzionamento e` il seguente:

Dati due numeri naturali a e b, si controlla se b e` zero. Se lo e`, a e` ilMCD. Se non lo e`, si divide a per b e si assegna ad r il resto della divisio-ne. Se r = 0 allora si puo` terminare affermando che b e` il MCD cercato,altrimenti occorre assegnare a = b e b = r e si ripete nuovamente la divisione.

Lalgoritmo puo` essere espresso in modo naturale utilizzando una semplicericorsione. Dopo questi 2 passaggi calcolabili su un calcolatore classico siarriva al nucleo dellalgoritmo di Shor per cui risulta necessario un calcolatorequantistico.

6.5 Order finding su un calcolatore quantisti-

co

Vediamo ora come sia possibile, con gli strumenti fino ad ora incontrati, risol-vere il problema dellorder finding su un calcolatore quantistico. Supponiamodi voler trovare lordine r di a rispetto ad N (ar = 1 mod N). Sono neces-sari due registri di qubit per ottenere il nostro risultato. Il primo registrodeve essere semplicemente inizializzato con tutti i numeri tra 0 e 2a1, di lun-ghezza m, dove m e` un numero che soddisfa la condizione N2 2m 2N2.Questa condizione e` necessaria per ottenere una precisione sufficiente nellaQFT. Il secondo registro viene invece inizializzato calcolando per ogni va-lore del primo registro la funzione f(x) = ax mod N . I nostri due registriavranno quindi, usandola notazione binaria, la seguente forma:

32

2n1x=0

|x |f(x) (6.19)

Eimportante notare come grazie al parallelismo quantistico possiamo cal-colare tutti i valori di f(x) con un solo calcolo. In teoria ora ci basterebbemisurare il secondo registro per vedere in quale caso f(x) = 1 e quindi ottene-re la relativa x. Sappiamo pero` che non e` possibile effettuare tale operazioneper la natura probabilistica di tale operazione. Inoltre i due registri si tro-vano in uno stato Entangled e quindi la misura di uno dei due provochera` lamodifica dellaltro. Misurando il secondo registro misureremo uno dei pos-sibili valori di f(x), che chiameremo f(x0), modificando conseguentementelo stato del sistema e in particolare anche il primo registro. Otteniamo cosidopo la nostra misurazione il nuovo stato dato da:

1m

m1j=0

|x0 + jr |f(x0) (6.20)

dove m = N/r e` il numero di valori di x per cui f(x) = f(x0). Concen-triamoci ora sul primo registro che contiene in maniera non esplicita il valoreri r cercato. Il secondo registro non ci servira` piu` nei seguenti passaggi. Pertrovare r utilizzeremo adesso la QFT, grazie alla quale possiamo trovare ilperiodo di una sequanza di valori. Applicando la QFT al primo registrootteniamo :

1r

r1k=0

e2piix0k

r |kNr (6.21)

Quindi la trasformata QFT estrare tutte le frequenze multiple di Nr

. Semisuriamo il primo registro otterremo con eguale probabilita` uno di questivalori, che chiameremo c. Vale quindi che c

N=

r, con numero intero

sconosciuto. Se e r sono coprimi tra loro, allora cN

puo` essere semplificataportandola a una frazione irriducibile da cui e` possibile ricavare e r. Incaso contrario lalgoritmo fallisce e deve essere ripetuto. Si puo` dimostrareche dopo (log log r) tentativi si avra` un successo. Inoltre va` consideratoche spesso la misurazione del registro porta ad un valore approssimato, nonesatto. In questo caso e` possibile utilizzare il metodo delle frazioni continueper trovare la frazione

rcercata, da cui sia possibile ricavare r. Per ottenere

una approssimazione sufficiente deve valere la seguente diseguaglianza:

| cN r| 1

2N(6.22)

33

dove c e` il valore misurato, e` un numero intero ignoto e r e` il valore delperiodo. Se la approssimazione non risulta sufficiente e` possibile aumen-tare la dimensione del primo registro utilizzato per ottenere una maggioreapprossimazione oppure scegliere un nuovo numero casuale a.

6.6 Metodo delle frazioni continue

In generale quando il periodo r di una funzione non divide 2m, m N, ilvalore misurato v dopo aver effettuato la QFT, sara` con una alta probabilita`un valore vicino a un intero del tipo 2

m

r, diciamo j 2

m

r. Vogliamo riuscire

a estrarre comunque da questa frazione il valore r del periodo. Shor hamostrato che con alta probabilita` v e` compreso tra 1

2e j 2

m

r. In generale una

frazione continua finita e` una frazione del tipo:

a0 +1

a1 +1

a2+1

a3+1

+ 1an

(6.23)

dove a0, . . . , an sono interi positivi. Se scriviamo la ennesima frazionepn

qn

abbiamo una relazione di ricorsione definita nel seguente modo:

p0 = a0, p1 = a1a0 + 1, pn = anpn1 + pn2, (6.24)

q0 = 1, q1 = a1, qn = anqn1 + qn2. (6.25)

Inoltre le frazioni ottenute durante le iterazioni sono tutte irriducibili, ovverogcd(pi, qi) = 1. Ogni razionale positivo x puo` essere rappresentato come unafrazione continua ottenuta nel seguente modo: Denotiamo con bxc il piu`grande intero minore o uguale a x. Allora a0 = bxc e x = a0 + 0 con0 0 1. Se 0 6= 0, allora a1 = b1/0c e 1/0 = a1 + 1 con 0 1 1. SeSe 1 6= 0, allora a2 = b1/1c etc. Questo processo termina sempre per ognirazionale x, ottenendo una successione [a0, a1, . . . , an]. Grazie al seguenteteorema siamo in grado di calcolare la unica frazione

rda noi cercata.

Teorema 6.6.1. Supponiamo che pq

sia un qualsiasi numero razionale chesoddisfa

|pq x| 1

2q2. (6.26)

Allora pq

e` una delle frazioni generate con il metodo delle frazioni continueda x.

Per la dimostrazione si rimanda a (Hardy and Wright, 1945, theorem161). In questo modo possiamo semplicemente calcolare le frazioni continuegenerate da v e vedere quale frazione verifica la disuguaglianza |p

q v| 1

2q2.

34

6.7 Complessita`

In questa sezione verra` calcolato ed analizzato il costo computazionale dellal-goritmo di Shor. Data la natura probabilistica di tale algoritmo, effettueremoil calcolo in due fasi. Nella prima fase verra` analizzata la probabilita` che lal-goritmo termini con successo; nella seconda si analizzera` il costo di ciascunainterazione dellalgoritmo. Il prodotto di queste due analisi ci fornira` il costocomputazionale cercato. Ovviamente verra` analizzato il caso in cui un nu-mero n debba essere fattorizzato in due primi p e q. Nel caso in cui il numeron sia il prodotto di piu` primi bastera` iterare lalgoritmo, ed il costo rimarra`lo stesso, tralasciando un fattore costante moltiplicativo.

6.7.1 Probabilita` di terminazione

Conviene qui rielencare rapidamente i passaggi fondamentali dellalgoritmodi Shor dato che ci saranno utili in seguito. Supponiamo di voler fattorizzareil numero n in due primi p e q:

1. Scegliere un numero casuale tra {1,. . . ,n-1}.2. Calcolare gcd(a,n).

3. Se il gcd(a, n) = 1 allora proseguire con il passo successivo, altrimentipassare al passaggio 8.

4. Calcolare lordine r di a rispetto ad n ( Questo e` il passaggio che deveessere effettuato su un calcolatore quantistico).

5. Se r e` pari allora proseguire con il passo successivo, altrimenti passareal passaggio 8.

6. Calcolare p = gcd(ar/2 + 1, n) e q = gcd(ar/2 1, n).7. Se p e q risultano uguali ad n allora si prosegua con il prossimo

passaggio, altrimenti e` stato trovato un fattore di n.

8. Si vada al passggio 1 e si scelga un nuovo elemento a.

Denoteremo con Ps la probabilita` che lalgoritmo termini con successo allaprima iterazione. Chiameremo N il numero di passaggi necessari a trovare idue fattori di n sotto la condizione che PS 1 . Quindi

N log(1/)Ps

(6.27)

Per calcolare la probabilita` di Ps considereremo i seguenti eventi:

35

Aa: Levento ottenere un a tale che a < n e gcd(a, n) = 1. Ar: Levento ottenere il giusto ordine r. Ae: Levento lordine r e` pari. Af : Levento p e q calcolati sono i numeri primi cercati.

Usando la notazione appena descritta possiamo scrivere

Ps P (AeAf |AaAf )P (AaAr) = P (AeAf |AaAf )P (Aa)P (Ar) (6.28)dato che Aa e Ar sono eventi indipendenti. Quindi dovremo valutare treprobabilita` separatamente. La prima Probabilita` e` gia` stata calcolata prece-dentemente nella sezione 6.3 ottendendo:

P (Ae Af |Aa Af ) 1 12k1

(6.29)

tenendo conto che k e` il numero di primi in cui si scompone n. Analizziamoora la probabilita` P (Aa). Levento Aa e` equvalente allevento scegliere un dtale che d < r e gcd(d, r) = 1. La cardinalita` dellinsieme di numeri primi con

d minori di r e` data dalla nota formulda di eulero (r). Quindi P (Aa) =(r)r

.Essendo noto che

limrinf

(r) log log(r)

r= e (6.30)

abbiamo per r sufficientemente grande

P (Ar) =(r)

r e

log log(r) e

log(r) e

log(n)=e log2(e)

log2(n)=

log2(n)(6.31)

con costante rispetto ad n. Sapendo che P (Aa) =(n)n1 , possiamo analoga-

mente ottenere

P (Aa) log2(n)

(6.32)

con costante rispetto ad n. Possiamo infine stimare la probabilita` totalecome il prodotto delle tre probabilita` precedentemente calcolate ottenendo

Ps (1 12k1

)

log2(n)2 . (6.33)

Quindi otteniamo

N log 1/(1 1/2k1)(log2(n))

2 (6.34)

Abbiamo quidni ottenuto una stima sul numero di iterazioni necessarie allacorretta terminazione dellalgoritmo.

36

6.7.2 Costo di una singola iterazione dellalgoritmo

Vediamo ora il costo necessario ad ogni singola iterazione completa. Talecosto verra` ottenuto dalla somma dei costi di ciascun passaggio descrittoprecedentemente. Inizialmente viene eseguito una volta lalgoritmo di Eucli-de per determinare se il numero scelto casualmente e` un fattore di N . Quandosi analizza il tempo di calcolo dellalgoritmo di Euclide, si trova che i valori diinput che richiedono il maggior numero di divisioni sono due successivi nume-ri di Fibonacci, e il caso peggiore richiede (n) divisioni, dove n e` il numerodi cifre nellinput. In seguito, dato che analizziamo il caso pessimo, dobbiamoeseguire il calcolo dellordine di tale numero. Questo passaggio viene eseguitosu un calcolatore quantistico e ha un costo dato dalla trasformata quanti-stica di Fourier, ovvero (n2). Questo si ricava dal fatto che inizialmentedeve essere inizializzato un registro di n digit, quindi con costo lineare; inseguito deve essere calcolata una funzione, con costo costante (c), la QFTcon costo (n2) e alcune misurazioni che hanno nuovamente costo costante(c). Fatto questo dobbiamo nuovamente eseguire due volte lalgoritmo diEuclide per trovare i fattori di N . In totale sommando i vari costi otteniamoun costo del tipo (c n2). Facendo il prodotto fra questultimo costo e laprobabilita` di successo precedentemente calcolata si vede facilmente che siottiene un costo polinomiale nel numero di digit in ingresso. Piu` precisamen-te si ottiene un costo di circa (c n3). Questo mostra il grande vantaggiodi tale algoritmo che riesce quindi a ottenere, ipoteticamente, ottime presta-zioni anche su grandi numeri. Va` specificato ipoteticamente in quanto fin adoggi e` sono stati realizzati solo calcolatori quantistici con qualche decina diqubit. Su tali calcolatori sono stati fattorizzati con successo alcuni piccolinumeri grazie allalgoritmo di Shor. Gia` un calcolatore a 1024 qubit sarebbesufficiente per poter decifrare la maggior parte dei messaggi codificati grazieallRSA.

6.8 Esempio

Vediamo adesso un esempio di dellalgoritmo di Shor. Verra` mostrato ilnucleo di tale algoritmo, ovvero come trovare, dati m e N numeri interi,lordine di m rispetto a N . Nel nostro caso prenderemo come numero dafattorizzare N = 21 e come numero m scelto casualmente 11.

Scegliamo un numero k tale che N2 2k 2N2. Nel nostro casootteniamo 441 2k 882 da cui deriviamo k = 9. Useremo quindiper il nostro primo registro 9 qubit e per il secondo 5 qubit dato che11xmod21 21 25 = 32. Inizialmente i due registri vengono ini-

37

zializzati nello stato |0, 0. Applichiamo loperatore di Hadamard a nqubit al primo registro per ottenere:

12m1

2m1x=0

|x, 0 (6.35)

Calcoliamo adesso grazie al parallelismo quantistico tutti i valori dif(x) = 11xmod 21 in un solo passaggio.Saremo quindi nella forma:

12m1

2m1x=0

|x, 11x mod 21 (6.36)

Per analizzare meglio tale stato puo` risultare utile sviluppare tale som-matoria ottenendo:

|0, f(0)+ |1, f(1)+ + |2n1, f(2n1) (6.37)

Misuriamo adesso il secondo registro ottenendo uno tra i possibili valorif(x). Supponiamo di avere misurato il valore 8. In questo caso anche ilprimo registro collassera`, mantenendo solo i valori di x per cui f(x) = 8.Supponendo che esistano s valori di x che soddisfano tale condizioneavremo il nuovo stato:

1s

x:f(x)=8

|x, 11x mod 21 (6.38)

che espanso diventa: |x1, 8+ |x2, 8+ + |xn, 8.Il secondo registro risultera` inutile nei seguenti passaggi e puo` esseretranquillamente trascurato, per tale motivo esso non verra` piu` rap-presentato. In questo caso possiamo notare che ogni valore di x ri-sulta equiprobabile come valore presente nel primo registro e quindinon ci viene fornita nessuna informazione aggiuntiva.Il grafico di taledistribuzione di probabilita` risulta il seguente:

applichiamo adesso la transformata quantistica di Fourier al primoregistro ottenendo:

j

cj |j 2m

r (6.39)

dove j sono i valori di x rimasti ed r e` il periodo di f(x) da noi cercato.Dopo questo passaggio le probabilita` di misurare un valore x tra tuttii possibili risultano le seguenti:

38

Figura 6.1: probablita` di ottenere x come valore nel primo registro

Figura 6.2: probablita` di ottenere x come valore nel primo registro dopo averapplicato la QFT

39

Figura 6.3: Valori ottenuti con la tecina dellespansione

Si puo` notare che il periodo r non divide esattamente 2m dato che cisono valori della QFT diversi da 0 nelle vicinanze degli interi del tipo2m

r.

misuriamo adesso il primo registro ottenendo come valore v = 427. Seil periodo fosse una potenza del 2 allora sarebbe molto facile estrarreda tale valore r dato che v = j 2

m

r. Dato che il v non e` una potenza

del 2 useremo la tecnica di espansione precedentemente descritta pertrovare una frazione,

r, da cui poter ricavare r. Vengono mostrati nella

seguente figura i valori ottenuti da tale espansione:

Possiamo quindi ricavare 6 = q2 M q3, che risulta essere il periodor cercato.

Sapendo che (a r2 1)(a r2 + 1) = kN per qualche k N , otteniamo che(a

r2 1) = 1330 e (a r2 + 1) = 1332. Usando lalgoritmo di Euclide tra i

due valori trovati ed N possiamo trovare possibilmente 2 fattori di N,infatti:

GCD(21, 1330) = 7 (6.40)

GCD(21, 1332) = 3 (6.41)

che risultano essere i due fattori in cui e` scomponibile 21.

Lalgoritmo poteva fallire per le seguenti ragioni: il valore v poteva non essere sufficientemente vicino a un intero

del tipo 2m

r.

il periodo r e il numero j potevano avere fattori comuni. In questocaso il denominatore q poteva essere un fattore del periodo, e nonil periodo stesso.

avremmo potuto trovare, usando lalgoritmo di Euclide, N stessocome fattore di N.

il periodo della funzione f(x) = ax mod N poteva essere dispari.

40

Bibliografia

[Ben] Giuliano Benenti, Giulio Casati e Giuliano Strini. World Scientific,2004. Principles of Quantum Computation and Information. Volume I:Basic Concepts.

[Shor] Peter W. Shor. Polynomial-Time Algorithms for Prime Fac-torization and Discrete Logarithms on a Quantum Computer.http://arxiv.org/abs/quant-ph/9508027v2

[Lenstra] Lenstra Jr., H. W. 1987. Annals of Mathematics 126. Factoringintegers with elliptic curves.

[KSS05] K.Kuriyama, S.Sano and S. Furuichi 2005. A precise estimation ofthe computational complexity in Shors factoring algorithm

[Pomerance 96] Pomerance Carl, December 1996. A Tale of two Sieves. pp:1473

[Preskill 98] Preskill John, September 1998. Quantu Information andComputation

[RP] Eleanor Rieffel, Wolfgang Polak, 2000. An Introduction to QuantumComputing for Non-Physicistts

[Mermin] N. David Mermin, 2007. Quantum Computer Science, AnIntroduction

41