Quantum ComputingCurs 13

Andreea Arusoaie

4 Ianuarie 2021

1 / 25

Outline

Problema factorizării - varianta clasică

Problema factorizării - varianta cuantică

2 / 25

Problema factorizării

• Problema factorizării constă ı̂n găsirea factorilor primi ai unui număr.

• Dacă p şi q sunt numere prime mari, atunci produsul N = p · q esteuşor de calculat, ı̂nsă dacă este dat N este greu să găsim factoriiprimi p şi q.

• Cel mai eficient algoritm clasic care rezolvă problema factorizării estegeneral number field sieve(GNFS) care factorizează un ı̂ntreg N ı̂n

timp O(

exp(

2(log2 N)13 (log2 log2 N)

23

)).

− Factorizarea unui număr de 400 digits ar dura 1010 ani.• Problema factorizării este importantă ı̂n practică pentru că pe

dificultatea factorizării se bazează majoritatea schemelor de criptare.

• Criptosistemele RSA(Rivest-Shamir-Adleman) sunt printre cele maides utilizate metode de criptare cu cheie publică şi se bazează pedificultatea factorizării numerelor mari prime.

3 / 25

Criptarea RSA - exemplu

Unele site-uri, spre exemplu Amazon, doresc ca tu sa poţi să le trimiţi unmesaj pe care doar ei să ı̂l poată decripta (datele de pe cardul de credit).

Însă, nu vă puteţi ı̂ntâlni pentru a stabili o cheie de criptare secretă.

Prin urmare, Amazon va găsi două numere mari prime p şi q pe care levor ţine secrete, le va ı̂nmulţi pentru a obţine N = pq, şi va publica N.

Iar noi vom putea cripta un mesaj folosind o cheie publică N astfel: dacămesajul este x , atunci folosind cea mai simplă versiune de RSA mesajulcriptat va fi x3 mod N.

Amazon, ştiind numerele prime p şi q şi mesajul criptat, va putearecupera mesajul x folosind câteva noţiuni de bază din teoria numerelor.

Aşadar, ideea de bază a securităţii de acest tip este aceea că dacă ştim pşi q, atunci vom şti ordinea grupului multiplicativ modulo N (Z/nZ), şi,prin urmare, ı̂l voi putea găsi pe x . Dacă nu ştim p, q ci ştim doarprodusul N, problema va deveni mult mai complicată.

4 / 25

Algoritmul de factorizare al lui Shor

• În 1994, Peter Shor a propus un algoritm cuantic care factorizeazăeficient (timp polinomial) un număr mare.

• Algoritmul lui Shor factorizează un număr N ı̂n timp polinomial, deordinul O(log2(N))3, folosind O(log2(N)) resurse; un număr de 400digits va putea fi factorizat ı̂n mai puţin de 3 ani.

• Algoritmul lui Shor este mai complex comparativ cu algoritmiistudiati pana acum pentru că are şi părţi clasice si părţi cuantice.

• Problema factorizarii unui număr N se poate reduce la a găsi ordinulunui număr ı̂ntreg x mai mic decat N. Această procedura, carepoate fi rezolvată pe un calculator clasic, este apoi implementatăutilizând un algoritm cuantic mult mai eficient de găsire a ordinului.

5 / 25

Algoritmul lui Euclid

I Algoritmul lui Euclid se utilizează pentru găsirea celui mai maredivizor comun al numerelor ı̂ntregi p şi q, notat gcd(p, q).

Teoremă: Dacă p şi q sunt numere ı̂ntregi, iar r ∈ Z, cu r 6= 0 esterestul ı̂mpărţirii lui p la q, atunci gcd(p, q) = gcd(q, r).

Algoritmul lui Euclid de găsire a gcd(p, q) cu p > q are următorii paşi:

• se ı̂mparte p la q pentru a găsi restul r1 < q şi vom avea relaţiagcd(p, q) = gcd(q, r1);

• se ı̂mparte q la r1 şi se obţine r2 < r1, ı̂n plus, are locgcd(q, r1) = gcd(r2, r1);

• repetând procedeul vom divide rn−2 la rn−1 şi vom găsi restulrn < rn−1. Mai mult vom avea, gcd(p, q) = . . . = gcd(rn−1, rn)

• cum ri este o secvenţă strict descrescătoare de numere pozitive, vaexista n cu rn+1 = 0, adică rn−1 = αrn.

• algoritmul se termină dacă avem gcd(p, q) = gcd(rn−1, rn) = rn.

6 / 25

Algoritmul lui Euclid

Exemplu: Determinaţi gcd(1071, 1029).

Observaţie:

I Dacă p şi q sunt numere ı̂ntregi reprezentaţe cu n biţi, atunci ri va fiun ı̂ntreg tot din n biţi, pentru orice indice i .

I Fiecare ı̂mpărţire va va costa O(n2), iar cum ri+2 ≤ ri2 , vom aveanevoie de O(n) ı̂mpărţiri; deci gcd(p, q) va costa O(n3).

7 / 25

Găsirea ordinului unui număr ı̂ntreg

Fie x şi N numere ı̂ntregi pozitive. Atunci, vom distinge următoarelesituaţii

• dacă x şi N au factori comuni, atunci gcd(x ,N) este factor al lui N;astfel vom considera doar cazul când x este coprim cu N(adicăgcd(x ,N) = 1);

• dacă N este par, ı̂l vom ı̂mpărţi la 2 repetat până obţin un numărimpar, apoi aplic algoritmul.

Definiţie

Numim ordinul lui x modulo N este cel mai mic număr ı̂ntreg pozitiv rpentru care

x r ≡ 1 mod N

- N este divizorul/factorul lui x r − 1.• Există mereu ordinul unui număr ı̂ntreg deoarece puterile ı̂ntregi xk

formează un grup ciclic finit.

8 / 25

Găsirea ordinului unui număr ı̂ntreg

Dacă r este par, definim y prin x r/2 ≡ y mod N, adică restul ı̂mpărţiriilui x r/2 la N (0 ≤ y < N).

Cum y2 ≡ 1 mod N, vom obţine

x r − 1 = (x r/2 − 1)(x r/2 + 1) = (y − 1)(y + 1) ≡ 0 mod N

deci N divide (y − 1)(y + 1).

Cum 1 < y < N − 1, vom avea că 0 < y − 1 < y + 1 < N, deci N nupoate divide y − 1 şi y + 1 separat, ci N va avea un factor comun netrivialcu fiecare dintre y − 1 şi y + 1, factori care să dea N prin ı̂nmulţire.

Aşadar gcd(y − 1,N) şi gcd(y + 1,N) sunt factori netriviali ai lui N, şipot fi calculaţi ı̂ntr-un număr de O(log3 N) operaţii.

9 / 25

Factorizarea numerelor ı̂ntregi - varianta clasică

Sumarizând, problema factorizării ı̂ntregilor are următorii paşi:

I Alegem un număr aleator x , cu x < N;

I Calculez gcd(x ,N)

I Dacă gcd(x ,N) 6= 1 am găsit un factor netrivial al lui N, şi măopresc;

I Dacă gcd(x ,N) = 1, găsesc ordinul r al lui x ;

I Dacă r este par şi 0 < y − 1 < y + 1 < N, factorii lui N suntgcd(y − 1,N) şi gcd(y + 1,N).

I Dacă nu are loc una din condiţiile de la pasul precedent, mă ı̂ntorc lapasul 1 şi aleg un alt x .

Observaţii:

1. Se poate ı̂ntâmpla ca algoritmul să dea factori triviali ai lui N(1 şi N)

2. Algoritmul nu este eficient pentru N mare. Este dificil să calculămperioada r al lui x mod N pentru N mare.

10 / 25

Outline

Problema factorizării - varianta clasică

Problema factorizării - varianta cuantică

11 / 25

Problema factorizării - varianta cuantică

• Algoritmul cuantic propus de Peter Shor, calculează mult mai eficientordinul/perioada unui număr ı̂ntreg x şi coprim cu N folosind QFT.

• Presupunem că avem o funcţie cu proprietatea f (t) = f (t + r),adică o funcţie periodică de perioadă r .

• În mod clasic este greu de găsit perioada deoarece avem nevoie demulte evaluări ale funcţiei f (t). Avantajul calculatorului cuantic estecă el calculează ı̂ntr-o singură rulare f (t) pentru toate valorile t.

• Dacă vom alege f (t) = x t mod N, unde N este numărul defactorizat, x < N este un număr ales random, atunci perioada rpoate fi folosită pentru a găsi factorii primi ai lui N.

12 / 25

Găsirea ordinului/perioadei

• Dacă alegem, spre exemplu N = 15 şi x = 2 vom aveaf2,15(t) = 2

t mod 15 şi deci următoarele valori

t 0 1 2 3 4 5 6 7 8 9 10 11 12 . . .

f2,15(t) 1 2 4 8 1 2 4 8 1 2 4 8 1 . . .deci perioada r pentru x = 2 este 4.

• Pentru N = 15 şi x = 4t 0 1 2 3 4 5 6 7 8 9 10 11 12 . . .

f4,15(t) 1 4 1 4 1 4 1 4 1 4 1 4 1 . . .avem perioada r = 2.

• Pentru N = 15 şi x = 13 avemt 0 1 2 3 4 5 6 7 8 9 10 11 12 . . .

f13,15(t) 1 13 4 7 1 13 4 7 1 13 4 7 1 . . .deci perioada va fi r = 4.

13 / 25

Găsirea ordinului/perioadei

• Nu vom avea neaparat nevoie de toate valorile funcţiei, ci maidegraba ar trebui să găsim perioada funcţiei, adică cel mai micnumăr r cu proprietatea că

fx,N(r) = xr mod N = 1

iar dacă fx,N(r) = 1, atunci fx,N(r + s) = fx,N(s),∀s.• Pentru numere mici precum 15, 21, 247 se poate calcula relativ uşor

perioada funcţiei, ı̂nsă dacă N ar avea mai multe digits( spreexemplu, de ordinul sutelor) calculatorul clasic va avea nevoie defoarte mult timp şi foarte multe resurse pentru a găsi ordinul lui x şia factoriza N.

• Cu ajutorul superpoziţiei, calculatorul cuantic ne va ajuta săevaluăm fx,N(t) pentru toate valorile t dintr-o singură interogare.

14 / 25

Partea cuantică a algoritmului

Circuitul cuantic care implementează funcţia fx,N este următorul:

|a〉nUfx,N

|a〉n

|b〉m |b⊕ fx,N(a)〉m

unde Ufx,N este operatorul unitar descris prin

Ufx,N |a〉n ⊗ |b〉m = |a〉n ⊗ |b⊕ fx,N(a)〉m = |a〉n ⊗ |b⊕ (xa mod N)〉m

unde fx,N(a) = xa mod N, iar |a〉n şi |b〉m sunt stări de n−qubiţi,

respectiv m−qubiţi.

Cum valorile funcţiei fx,N vor fi mereu mai mici decât N, alegem

m = log2 N, iar n = logN2

2 = 2m.

Dacă perioada r este o putere a lui 2 putem lua n = m.

15 / 25

Implementarea porţii Ufx,N cu ajutorul porţilor cuantice

Pentru a putea implementa Ufx,N cu ajutorul matricilor unitare, va trebuisă “̂ımpărţim ” Ufx,N ı̂n mai multe matrici unitare(porţi cuantice).

Spre exemplu, dacă scriu a ı̂n binar avem

a = an−1an−2 . . . a1a0

sau, formal, a scris ca un număr este

a = an−12n−1 + an−22

n−2 + . . .+ a12 + a0.

Prin urmare, putem rescrie funcţia fx,N astfel

fx,N(a) = xa mod N = xan−12

n−1· xan−22

n−2· . . . · xa12 · xa0 mod N.

16 / 25

Implementarea porţii Ufx,N cu ajutorul porţilor cuantice

Cu această idee, vom putea reprezenta Ufx,N cu o serie de porţiControlled − Ux2i .

a0 a0

a1 a1

a2 a2

......

...

an−1 an−1

Ux20 Ux21 Ux22 U... Ux2n−1

17 / 25

Algoritmul lui Shor

Algoritmul lui Shor cuantic poate fi implementat cu ajutorul următoruluicircuit:

|0〉⊗n

|0〉⊗m

H⊗n

Ufx,N

QFT †

|ψ0〉 |ψ1〉 |ψ2〉

unde QFT † reprezintă inversa transformatei Fourier cuantice.

Starea calculatorului la ı̂nceputul circuitului este

|ψ0〉 = |0〉⊗n ⊗ |0〉⊗m.

18 / 25

Algoritmul lui Shor

Aplicând operatorul Hadamard asupra primilor n qubiţi, vom găsi

|ψ1〉 = H⊗n ⊗ |0〉⊗m =1√2n

2n−1∑k=0

|k〉n ⊗ |0〉m,

unde, pentru simplitate, am notat cu |·〉j o stare cu j qubiţi.

Aplicăm acum poarta Ufx,N , starea sistemului devenind

|ψ2〉 = Ufx,N |ψ1〉 =1√2n

2n−1∑k=0

Ufx,N (|k〉n⊗|0〉m) =1√2n

2n−1∑k=0

|k〉n ⊗ |xk mod N〉m

I Cum operatorul Ufx,N este liniar, el va acţiona asupra tuturor stărilor|k〉n ⊗ |0〉m simultan pentru toate cele 2n valori ale lui k, generând şitoate puterile lui x simultan. Această caracteristică se numeşteparalelism cuantic.

19 / 25

Algoritmul lui Shor

Mai mult, dacă xk mod N este periodică de perioadă r , atunci avemrelaţia xk ≡ xk+r mod N şi atunci funcţia fx,N(k) = xk mod N va fi ofuncţie periodică de perioadă r .

Pentru a vedea ce se obţine dacă am măsura stările de ieşire, vom rescrie|ψ2〉 colectând termenii egali din registrul al doilea.

Cum xk mod N are perioada r , vom nota k = αr + β, unde

0 ≤ α ≤ 2n

r− 1, iar 0 ≤ β ≤ r − 1. Înlocuind k ı̂n |ψ2〉 şi folosind că xβ

şi xαr+β sunt echivalente modulo N, obţinem

|ψ2〉 =1√2n

r−1∑β=0

2n

r −1∑α=0

|αr + β〉n ⊗ |xβ mod N〉m,

Dacă măsurăm cel de-al doilea registru, vom obţine x0, x1, . . . , x r−1 cuprobabilităţi egale.

20 / 25

Algoritmul lui Shor

Dacă rezultatul obţinut este xβ′, atunci starea după măsurare a

calculatorului cuantic este

|ψ3〉 =√

r

2n

2n

r −1∑α=0

|αr + β′〉n ⊗ |xβ′

mod N〉m.

La pasul următor se găseşte perioada r utilizând transformata Fouriercuantică.

Vom aplica transformata Fourier cuantică inversă asupra registrului deintrare (primii n qubiti).

Definiţia generală a acestei transformări este:

QFT †|x〉n =1√2n

2n−1∑y=0

e−2iπN xy |y〉n

21 / 25

Algoritmul lui Shor

Starea sistemului după aplicarea transformatei Fourier cuantice va fiurmătoarea

|ψ4〉 = QFT †|ψ3〉 =√

r

2n

2n

r −1∑α=0

1√2n

2n−1∑j=0

e−2πijN (αr+β

′)|j〉

|xβ′ mod N〉.Inversând ordinea de sumare avem

|ψ4〉 =1√r

2n−1∑j=0

r2n

2n

r −1∑α=0

e−2πiN jαr

e− 2πiN jβ′ |j〉n |xβ′ mod N〉.

Cum 1N

N−1∑j=0

e2πiN jk =

{1, dacă k este multiplu de N0, ı̂n caz contrar

vom avea

paranteza rotundă nenulă doar dacă j = k2n

r , unde k = 0, . . . , r − 1.

22 / 25

Algoritmul lui Shor

Aşadar, dacă j = k 2n

r vom avea

|ψ4〉 =1√r

(r−1∑k=0

e−2πir kβ

′|k · 2

n

r〉n

)|xβ′

mod N〉m

În final, măsor starea cuantică. Dacă obţin valoarea k′2n

r , unde0 ≤ k ′ ≤ r − 1, atunci procedez astfelI dacă k ′ = 0 (j = 0), nu ştiu nimic, şi atunci voi rula din nou partea

cuantică.

I dacă k ′ 6= 0, impart k′2n

r la 2n şi obţin valoarea k

′

r (fără să cunosck ′, r).

Dacă k ′ 6= 0, utilizăm un algoritm cuantic găsesc forma raţională a luic = k

′

r , adică găsesc a, b astfel ı̂ncât c = a/b şi gcd(a, b) = 1. În acestcaz, ordinul lui x este valoarea b.

23 / 25

Algoritmul de factorizare

Algoritmul de factorizare al lui Shor are următorii paşi:

1. Aleg x coprim cu N, unde 0 ≤ x ≤ N − 1;2. Calculăm gcd(x ,N).

3. Dacă gcd(x ,N) 6= 1, atunci am găsit un factor al lui N;4. Dacă gcd(x ,N) 6= 1 atunci găsesc ordinul r al funcţiei

fx,N(t) = xt mod N, adică cel mai mic număr r astfel ı̂ncât

x r ≡ 1 mod N;5. Dacă r este impar, ne ı̂ntoarcem la pasul 1;

6. Dacă r este par: calculez a = x r/2 mod N:I dacă a + 1 ≡ 0 mod N, ne ı̂ntoarcem la pasul 1;I ı̂n caz contrar, calculez gcd(a + 1,N) şi gcd(a− 1,N);I dacă obţinem factori netriviali ai lui N, am rezolvat problema.

24 / 25

Exemplu - Factorizarea pentru N = 15

25 / 25