La Trasformata di Fourier `e alla base di una procedura generale nota come stima delle fasi che permette di ottenere una stima degli autovalori di una matrice unitaria. Questa procedura `e a sua volta parte essenziale di molti algoritmi quantistici.
17.1 Stima dell’autovalore di una matrice unitaria
Dato un operatore unitario U su m qubit con un autovalore λ corrispondente ad un autovettore |ui, il problema `e stabilire con una certa precisione il valore di λ disponendo di oracoli che eseguono controlled-U2j, j = 0, . . . , t per un dato intero positivo t, e di una preparazione dello stato |ui. Nota che poich`e U `e unitaria, |λ| = 1 cio`e λ = e2πiϕ per qualche ϕ tale che 0 ≤ ϕ ≤ 1. Il problema consiste quindi nel trovare una stima per ϕ.
Questo problema si pu`o risolvere efficientemente mediante l’algoritmo quantistico che descriviamo nel seguito. L’uso di questo algoritmo non `e limitato a risolvere il problema descritto, ma `e parte integrante di altri algoritmi, dal momento che molti problemi si possono ridurre al problema della stima delle fasi, tra cui quelli descritti in 17.2 e l’algoritmo per la fattorizzazione in 17.5.
Il circuito schematizzato in Figura 27 implementa la procedura che si svolge in tre passi a partire da un input formato da due registri.
H F T†
Uj
|0i
|ui |ui
|ji
Figure 27: Circuito schematico per l’algoritmo di stima delle fasi
|ui H H H H U20 U21 U22 U2t−1 |0i |0i |0i |0i |ui
|0i + e2πi(2t−1ϕ)|1i
|0i + e2πi(22ϕ)|1i |0i + e2πi(21ϕ)|1i |0i + e2πi(20ϕ)|1i
Figure 28: Descrizione dettagliata del primo stadio del circuito in Figura 27 Il primo registro contiene t qubit inizialmente nello stato |0i. Il secondo registro contiene l’autovettore |ui che (come vedremo) non verr`a modificato dall’applicazione di Uj. Nella fase iniziale si applica H⊗t al primo registro |0i⊗t che diventa quindi
|ji =h(|0i + |1i)/√2i⊗t = √1 2t
2t−1
X
k=0
|ki .
Ciascun qubit nel primo registro viene usato come qubit di controllo dell’operazione controlled-U2k
come illustrato in Figura 28.
L’effetto della sequenza di controlled-U2k`e di trasformare |ji |ui in |ji Uj|ui. Infatti, notando che la rappresentazione binaria di j `e j12t−1 + j22t−2 + . . . jt20, Uj = Ujt20 Ujt−121 · · · Uj22t−2 Uj12t−1 ,
che viene applicata solo quando jk = 1 per ogni k = 1, . . . , t, cio`e solo se j = 1.
Osserviamo che se |ui `e una autovettore di U con autovalore λ, allora |ui `e anche un autovettore di U2k con autovalore λ2k. Pertanto
|ji Uj|ui = |ji e2πijϕ|ui = e2πijϕ|ji |ui = h(e2πij12t−1ϕ
|j1i) · · · (e2πijt−121ϕ
|jt−1i)(e2πijt20ϕ
|jti)i|ui . Poich`e ogni jk`e della forma (|0i + |1i)/√2, lo stato del primo registro dopo l’applicazione del circuito in Figura 28 risulta
t−1
O
k=0
|0i + e2πi2kϕ|1i √ 2 = 1 √ 2t 2t−1 X y=0 e2πiϕy/2t|yi ,
che corrisponde all’espressione ottenuta dall’applicazione della QFT al vet-tore |ϕi. Il secondo passo dell’algoritmo consiste quindi nell’applicazione dell’inversa della trasformata di Fourier, QF T†. Supponiamo che ϕ si possa rappresentare esattamente con t bit. Allora il secondo passo produce |ϕ1ϕ2. . . ϕti. L’ultimo passo `e una misurazione nella base computazionale che permette quindi di ottenere il valore esatto di ϕ.
Supponiamo ora che ϕ sia un qualsiasi numero reale (razionale o ir-razionale) in [0, 1] la cui rappresentazione su t bit `e approssimata a meno di un errore δ. Pi`u precisamente, supponiamo che ϕ = a/2t + δ, dove a = a0a1. . . at−1, ak ∈ {0, 1} per ogni k ∈ [0, t − 1]. Quindi a/2t `e la migliore approssimazione di ϕ su t bit, cio`e 0 ≤ δ ≤ 1/2t+1.Vogliamo con-siderare il caso in cui l’errore δ `e strettamente positivo. In questo caso si dimostra che dopo l’applicazione della QF T†, una misurazione dello stato finale produce questa approssimazione su t bit di ϕ con probabilit`a almeno 4/π2 ≈ 0.405.
Il valore di t si pu`o fissare in modo da ottenere una stima di ϕ pre-cisa quanto si vuole. Si pu`o cio`e fissare un ǫ tale che l’algoritmo produca un’approssimazione di ϕ precisa fino all’n-simo bit con probabilit`a almeno 1 − ǫ. Per ottenere questa stima si deve fissare t al valore
t = n + log 2 + 1 2ǫ , (6)
dove ⌈·⌉ indica la parte intera alta.
In generale, dati gli autovettori |ui , u ∈ T di un operatore unitario U con corrispondenti autovalori φu, l’algoritmo di stima delle fasi trasforma lo stato normalizzato
|0i (X
u∈T
nello stato X u∈T du ˜ φuE|ui), dove ˜ φu E
`e una buona stima di |φui. In questo caso la probabilit`a che questa stima sia precisa fino all’n-simo bit `e almeno |du|2(1 − ǫ) se t `e scelto come in ( 6).
17.2 Trovare l’ordine di un numero
Dati due interi positivi x ed N che non hanno fattori comuni e tali che x < N , si definisce l’ordine di x modulo N come il pi`u piccolo intero r tale che xr= 1(modN ).
Non si conoscono algoritmi classici che dati x ed N permettono di de-terminare r in tempo polinomiale in L = ⌈log N⌉. Nel seguito descriviamo un algoritmo quantistico che risolve questo problema con un numero di op-erazioni O(L3).
Richiamiamo prima le nozioni di aritmetica modulare necessarie per capire il problema e la tecnica utilizzata nell’algoritmo quantistico.
17.2.1 Aritmetica modulo n
Dati due interi positivi x ed n, si indica con x(mod n) il resto della di-visione di x per n. Pi`u precisamente, x si pu`o scrivere in modo univoco come x = kn + r dove k ≥ 0 e r `e il resto, 0 ≤ r ≤ n − 1. Le oper-azioni nell’aritmetica modulo n sono le operoper-azioni aritmetiche di somma, sottrazione, moltiplicazione e divisione dove si prende il risultato modulo n. Una differenza sostanziale `e la definizione dell’inverso di un numero modulo n. Infatti, mentre in aritmetica gli unici interi ad avere un inverso sono 1 e −1, in aritmetica modulare ci possono essere altri interi che hanno un inverso. La seguente proposizione stabilisce una condizione necessaria e suf-ficiente perch´e un intero abbia un inverso modulo n.
Proposition 17.1 Un intero x ha un inverso modulo n se e solo se M CD(x, n) = 1, dove M CD(x, n) `e il massimo comun divisore di x ed n.
17.2.2 L’algoritmo quantistico
L’algoritmo quantistico per trovare l’ordine di un numero x modulo N con-siste essenzialmente nell’applicare il metodo di stima delle fasi all’operatore
unitario U definito da:
U |yi = |xy(mod N)i se 0 ≤ y ≤ N − 1 U |yi = |yi se N ≤ y ≤ 2L− 1.
Si verifica facilmente che, se r `e l’ordine di x modulo N e 0 ≤ s ≤ r − 1, ogni vettore della forma
|usi = √1 r r−1 X k=0 e−2πisk/r x k(mod N )E,
`e un autovettore di U con autovalore e2πis/r. Infatti, usando l’ipotesi xr = 1(mod N ), si ha che: U |usi = √1 r r−1 X k=0 e−2πisk/r x k+1(mod N )E = √1 r r X k=1 e−2πis(k−1)/r x k(mod N )E = √1 r r−1 X k=0 e−2πis(k−1)/r x k(mod N )E = e2πis/r|usi .
Il penultimo passaggio si spiega osservando che nella sommatoria
r−1 X k=0 e−2πis(k−1)/r x k(mod N )E
il valore dell’elemento che si ottiene per k = 0 (cio`e e2πis/r|1(mod N)i) `e esattamente quello che si ottiene nella sommatoria
r X k=1 e−2πis(k−1)/r x k(mod N )E
per k = r. Quest’ultimo infatti risulta:
e−2πis(r−1)/r|xr(mod N )i = e−2πise2πis/r|1(mod N)i = e2πis/r|1(mod N)i . L’idea base dell’algoritmo `e di ottenere un’approssimazione accurata della fase s/r da cui poter ricavare il valore di r.
Il primo problema da risolvere `e preparare lo stato |usi. Questo problema non `e banale dal momento che |usi `e definito in termini del valore r che vogliamo trovare. Invece di |usi, prepariamo il secondo registro in input al circuito per la stima delle fasi nello stato |1i. Pochi calcoli dimostrano infatti che questo stato corrisponde ad una combinazione lineare di tutti gli autovettori |usi di U per 0 ≤ s ≤ r − 1: 1 √r r−1 X s=0 |usi = r−1 X k=0 1 r r−1 X s=0 e−2πisk/r ! x k(mod N )E,
dove l’espressione in parentesi risulta uguale a 1 se k = 0, mentre `e 0 per tutti gli altri valori di k. Per vedere questo basta osservare che per k > 0 la sommatoria in parentesi `e la serie geometrica di ragione e−2πik/r e quindi converge a 1−(e−2πik/r)r
1−e−2πik/r = 0. Pertanto, la combinazione degli autovettori |usi coincide con lo stato |1i.
Per ragioni che saranno chiarite in 17.4, prendiamo n = 2L + 1. Di conseguenza, il numero di qubit del primo registro dell’algoritmo di stima delle fasi sar`a t = 2L + 1 +log 2 + 1
2ǫ. Inoltre una misurazione del primo registro produrr`a per ogni s, 0 ≤ s ≤ r − 1, un’approssimazione ϕs di s/r precisa fino al bit 2L + 1 con una probabilit`a di almeno (1 − ǫ)/r (cf. 17.1).
Dobbiamo ora risolvere ancora due problemi:
Come eseguire la sequenza di controlled-U2k, Come ricavare r dalla stima ϕs trovata.
17.3 Complessit`a delle operazioni controllate C(U2k)
Nell’algoritmo descritto in 17.1 le operazioni controllate U2k sono state trattate come “scatole nere”. Nell’istanza particolare dell’algoritmo per il nostro problema di trovare l’ordine di un numero x modulo N , la sequenza di controlled-U2k corrisponde esattamente alla moltiplicazione modulo N del secondo registro per x elevato ad una potenza pari al contenuto del primo registro. Infatti, se |ki `e lo stato del primo registro e |ui lo stato del secondo registro, allora dopo l’applicazione della sequenza di controlled-U2k
si ottiene
|ki |ui 7→ |ki Ukt2t−1
Ukt−12t−2 . . . Uk120 |ui = |ki x kt2t−1 xkt−12t−2 . . . xk120 u(mod N )E = |ki x kt2t−1+kt−12t−2...k120 u(mod N )E
= |ki x
ku(mod N )E.
Questa operazione pu`o essere realizzata usando lo schema di computazione reversibile con un numero di operazioni elementari dell’ordine di L3. L’idea `e di eseguire t − 1 = O(L) operazioni di moltiplicazione modulare per cal-colare x2(mod N ), x4(mod N ) e cos`ı via fino a x2t−1
(mod N ). Ciascuna di queste operazioni costa O(L2) (se si usano le regole ordinarie per la molti-plicazione binaria). Quindi il calcolo costa in totale O(L3). A questo punto si usa l’identit`a
xku(mod N ) = xkt2t−1+kt−12t−2...+k120
u(mod N ),
per ottenere xku(mod N ) con altre t − 1 moltiplicazioni reversibili con com-plessit`a O(L3).
17.4 Frazioni continue
Per ricavare r dalla stima ϕs si usa la tecnica delle frazioni continue che illustriamo brevemente nel seguito.
Le frazioni continue permettono di approssimare un qualsiasi numero reale con una sequenza di numeri razionali della forma
[a0, a1, a2, . . . , ap] = a0+ 1 a1+a 1
2+ 1 ...+ 1ap
,
dove aj sono interi positivi per j ≥ 1.
Per un numero reale c, si definisce l’espansione in frazioni continue nel seguente modo. A partire da c si costruiscono ricorsivamente le sequenze {aj}j≥0 e {rj}j≥0 prendendo a0 = ⌊c⌋, r0 = c − a0 e per ogni j ≥ 1, aj = ⌊rj−11 ⌋ e rj = r1
j−1 − ⌊rj−11 ⌋. Allora per ogni j ≥ 0 con rj > 0, c = a0+ 1 a1+a 1 2+ 1 ...+ 1 aj+rj .
Il numero razionale [a0, a1, a2, . . . , aj] `e detto il j-esimo convergente di c. Se rj = 0 allora le frazioni continue terminano con aj e si ottiene l’uguaglianza c = [a0, a1, a2, . . . , aj].
Esempio 17.2 L’espansione in frazioni continue di 47/13 `e data da: 47 13 = 3 + 8 13 = 3 + 1 13 8 = 3 + 1 1 +58 = 3 + 1 1 + 18 5 = 3 + 1 1 +1+13 5 = 3 + 1 1 + 1+11 5 3 = 3 + 1 1 + 1 1+ 1 1+ 23 = 3 + 1 1 + 1 1+ 1 1+ 13 2 = 3 + 1 1 + 1 1+ 1 1+ 1 1+ 12 . Pertanto c = [3, 1, 1, 1, 1, 2].
Elenchiamo alcuni importanti risultati della teoria dei numeri che ci saranno utili per il nostro problema. In particolare, siamo interessati al caso in cui c `e un numero razionale (come appunto s/r). In questo caso si dimostra la seguente proposizione:
Proposition 17.3 L’espansione in frazioni continue di un numero reale c termina se e solo se c `e un numero razionale.
La seguente proposizione ci permette di ricavare numeratore e denomi-natore di un numero razionale dalla sua espansione in frazioni continue. Proposition 17.4 Il numero razionale [a0, a1, a2, . . . , aj] `e il numero pj
qj
dove p0= a0, q0= 1, p1= 1 + a0a1, q1 = a1 e per ogni j ≥ 2: pj = ajpj−1+ pj−2 e qj = ajqj−1+ qj−2.
Corollary 17.5 L’espansione in frazioni continue di un numero razionale positivo p/q si pu`o ottenere in O(m3) operazioni, se p e q sono interi su m bit.
Teorema 17.6 Supponiamo che x e p/q siano numeri razionali tali che |x − p/q| ≤ 1/2q2. Allora p/q `e un convergente della frazione continua per x.
Questo teorema ci permette di concludere che s/r `e un convergente del numero razionale ϕs ottenuto dall’algoritmo di stima delle fasi, purch´e si scelga una precisione n = 2L+1. Infatti, in questo caso, poich`e r ≤ N ≤ 2L, si ha che
|ϕs− s/r| < 1/22L+1≤ 1/2r2.
Inoltre, questo convergente s/r si pu`o calcolare con O(L3) operazioni ele-mentari.
Avendo a disposizione questi risultati possiamo ora completare la de-scrizione dell’algoritmo quantistico per trovare l’ordine r di un numero pos-itivo x modulo N .
Calcoliamo con il metodo delle frazioni continue un convergente p/q di ϕs, tale che q ≤ 2L e |ϕs− p/q| < 1/22L+1 (si dimostra che esiste sempre almeno una frazione con queste propriet`a). Il denominatore q `e un candidato per r. Si controlla se xq = 1(mod N ). Se il test ha successo, allora q `e l’ordine di x modulo N . Altrimenti l’algoritmo fallisce e bisogna eseguirlo nuovamente.
Una condizione importante per il successo dell’algoritmo `e che r ed s non abbiano fattori comuni, altrimenti il numero restituito dall’algoritmo delle frazioni continue potrebbe essere un fattore di r piuttosto che r stesso. Per N molto grandi, la probabilit`a che r ed s siano co-primi `e almeno 1/ log N . Basta quindi ripetere l’algoritmo un numero adeguato di volte per ottenere con alta probabilit`a un istanza di s/r con r ed s co-primi. In particolare, ripetendo l’algoritmo O(L) volte l’algoritmo ha successo con probabilit`a (1− ǫ)(1 − 1/N), con un costo totale di O(L4) operazioni.
17.5 Fattorizzazione
Dato un numero intero positivo dispari e composto N , il problema della fattorizzazione consiste nel trovare i fattori primi di N .
Determinare se un numero N `e primo o composto `e un problema com-putazionalmente “facile”: l’algoritmo probabilistico di Miller-Rabin per il test di primalit`a impiega O(s log N ) operazioni aritmetiche con una proba-bilit`a di errore P ≤ 2−s. Recentemente (nell’estate del 2002) tre ricercatori indiani hanno scoperto un algoritmo deterministico in grado di stabilire in tempo polinomiale (e con certezza) se un numero `e primo oppure no, di-mostrando che il problema `e effettivamente in P.
Una volta stabilito che un numero `e composto, non sembra altrettanto facile determinare i suoi fattori primi.
I sistemi crittografici oggi pi`u diffusi (come il sistema RSA10) sono basati sulla seguente congettura:
Conjecture 17.7 La fattorizzazione di interi `e un problema computazional-mente pi`u difficile della moltiplicazione di interi: mentre esistono molti al-goritmi polinomiali per la moltiplicazione di interi, non esistono alal-goritmi polinomiali per la fattorizzazione di interi.
Questa assunzione `e basata sul fatto che gli sforzi che per molte centi-naia di anni hanno impegnato i pi`u grandi scenziati non sono stati suffi-cienti a produrre un algoritmo polinomiale per la fattorizzazione. Il pi`u efficiente algoritmo classico che si conosca al momento `e il cosiddetto “num-ber field sieve” la cui complessit`a `e stata euristicamente dimostrata essere O(expc(log N)1/3(loglogN )2/3), cio`e l’algoritmo richiede un tempo super-polinomiale nel numero di cifre O(log N ) in N .
Verso la met`a degli anni ’90 Peter Shor ide`o (partendo da risultati prece-denti dovuti a Benioff, Bennet, Deutsch, Feynmann, Simon ed altri) un al-goritmo quantistico in grado di fattorizzare un intero in tempo polinomiale. La complessit`a di questo algoritmo risulta infatti
O (log N )2(log log N )(log log log N ) , cio`e polinomiale nel numero di cifre O(log N ) in N .
L’algoritmo consiste dei cinque passi descritti alla fine di questo capitolo, di cui solo il Passo 3 richiede l’uso di un computer quantistico (in partico-lare questo passo invoca la procedura quantistica per trovare l’ordine di un numero descritta in 17.2). Tutti gli altri passi dell’algoritmo possono essere eseguiti su un computer classico.
Richiamiamo brevemente i principali risultati di teoria dei numeri nec-essari per capire come funziona l’algoritmo e qual `e la sua complessit`a.
Descriviamo per prima cosa l’algoritmo di Euclide per trovare il massimo comun divisore, M CD(p, q), di due interi positivi p e q che si basa sul seguente risultato:
Proposition 17.8 Dati due interi p e q, supponiamo che r sia il resto della divisione di p per q e che sia r 6= 0. Allora
M CD(p, q) = M CD(q, r).
10RSA `e un sistema crittografico a chiavi pubbliche inventato da Rivest, Shamir, Adle-man da cui ha preso il nome.
L’algoritmo di Euclide `e il seguente: supponendo che p > q, si divide p per q e si trova il resto r1 < q. Per la proposizione 17.8, M CD(p, q) = M CD(q, r1). Si divide quindi q per r1 e si trova il resto r2 < r1 con M CD(q, r1) = M CD(r1, r2). Induttivamente, si divide rn−1 per rn−2 per trovare il resto rn< rn−1 con
M CD(p, q) = M CD(q, r1) = . . . = M CD(rn, rn+1).
Poich`e la sequenza rj `e una sequenza di interi positivi strettamente decres-cente, esiste n tale che rn+1 = 0, cio`e rn−1 `e un multiplo di rn. Quindi l’algoritmo termina con
M CD(p, q) = M CD(rn−1, rn) = rn.
La complessit`a dell’algoritmo di Euclide `e O(L3), dove L `e il numero di bit necessari per rappresentare p e q. Infatti, l’algoritmo richiede al pi`u O(L) divisioni binarie, ciascuna delle quali richiede O(L2) operazioni su bit. Il seguente teorema ci fa vedere come il problema della fattorizzazione si riduce a quello di trovare l’ordine di un numero.
Teorema 17.9 Supponiamo che N sia un numero composto e che x ∈ {1, . . . , N} sia una soluzione non banale dell’equazione x2 = 1(mod N ), cio`e tale che x 6= 1(mod N) e x 6= N − 1 = −1(mod N). Supponiamo in-oltre che L sia il numero di bit necessari per rappresentare N (L = ⌈log N⌉). Allora almeno uno tra M CD(x − 1, N) e MCD(x + 1, N) `e un fattore non banale di N che pu`o essere calcolato in O(L3) passi.
Questo risultato combinato con il seguente teorema permette di deter-minare con alta probabilit`a un fattore non banale di un qualsiasi numero composto N .
Teorema 17.10 Supponiamo che la scomposizione in fattori primi del nu-mero intero dispari composto N sia N = pn1
1 · · · pnm
m . Se x `e un intero scelto casualmente tra 1 e N tale che M CD(x, N ) = 1 e r `e l’ordine di x modulo N , allora
P (r `e pari e xr/26= −1(mod N)) ≥ 1 − 1/2m.
L’algoritmo Per calcolare un fattore non banale di un numero intero N di L bit, dispari e composto si procede come segue:
Passo 2 Con l’algoritmo di Euclide calcoliamo il M CD(x, N ). Se M CD(x, N ) > 1 allora abbiamo trovato un fattore non banale di N . Altrimenti si procede con il passo 3.
Passo 3 Usiamo l’algoritmo quantistico descritto in 17.2 per trovare l’ordine r di x modulo N .
Passo 4 Se r `e dispari, oppure r `e pari e xr/2 = −1(mod N), allora ritor-niamo al passo 1.
Passo 5 Con l’algoritmo di Euclide calcoliamo M CD(xr/2−1, N) e MCD(xr/2+ 1, N ) e se uno dei due interi calcolati risulta essere un fattore non ba-nale di N , allora l’algoritmo termina con successo. Altrimenti fallisce e bisogna ripeterlo a partire dal passo 1.