Quantum Computing

Curs 12

Andreea Arusoaie

December, 21, 2020

1 / 26

Outline

Algoritmul lui Grover

Transformata Fourier: Aplicatii

2 / 26

Algoritmul lui Grover

I In algoritmii cuantici prezentati anterior se aplicau unor probleme cese refereau la o functie f cu o anume proprietate (constanta,balansata, periodica)

I Algoritmul de cautare al lui Grover se refera la o functie ce nu areproprietati speciale si ofera o solutie rapida a problemei:

Sa se gaseasca unul dintre obiectele care satisfac o anumitacerinta dintr-o lista nesortata de N obiecte.

I Cautarea ıntr-o baza de date cu N intrari ın mod clasic se face ıntimp liniar, ınsa cu ajutorul algoritmului cuantic al lui Grovercautarea se poate face ın timp O(

√N) si folosind O(logN) spatiu

de stocare.

I Algoritmul lui Grover este unul probabilist, va furniza un raspuns cuo probabilitate mai mare. Probabilitatea sa nu obtinem rezultatulcorect poate fi redusa prin repetarea de mai multe ori a algoritmului.

3 / 26

Algoritmul lui Grover

Problema:

I Dorim sa cautam ıntr-o lista de N elemente, yx , undex ∈ {0, . . . ,N − 1}

I Fie N = 2n. Asadar, vom putea stoca x ın n qubiti.

I Presupunem ca numarul obiectelor /solutiilor ce satisfac o cerintadata este M, unde 1 ≤ M ≤ N;

I In loc sa ne focusam pe lista nesortata, ne vom ındrepta atentiaasupra index-ului x ;

I Data o valoare x , verificati ca yx rezolva problema de cautare.

4 / 26

Algoritmul lui Grover

I Spre exemplu, daca am f (t) = a pentru t = t0, ma intereseazavaloarea lui t pentru care valoarea functiei este a.

Daca lista ar fi sortata, eventual dupa valorile lui f , as putea gasivaloarea t = t0, uitandu-ma la log2 N intrari ın lista.

Daca N = 2n caut f (t) pentru t = 2n−1 − 1 si verific daca este maimare ca a. Daca este mai mare ca a, verific f pentru t = 2n−2 − 1.

Un numar de n cautari ar fi suficient sa verific toti cei 2n termenisortati.

I Daca lista este nesortata, trebuie sa verific N/2 termeni ınainte saam o probabilitate de 1/2 pentru a gasi raspunsul.

I Daca am M obiecte care sa verifice cerinta data, vom avea nevoie ınmedie de N/M rulari ale algoritmului clasic.

I Algoritmul lui Grover gaseste solutia ın√N/M rulari.

5 / 26

Algoritmul lui Grover

Circuitul care implementeaza algoritmul de cautare al lui Grover este:

I Starea initiala este |ψ0〉 = |0〉⊗n ⊗ |1〉;I Dupa aplicarea portilor Hadamard obtinem:

|ψ1〉 = (H⊗n ⊗ H)(|0〉⊗n ⊗ |1〉) =

(1√N

2n−1∑x=0

|x〉⊗n)⊗ H|1〉

6 / 26

Algoritmul lui Grover

Iteratia lui Grover, G este descrisa de urmatorul circuit

sicontine doua transformari:

I prima transformare, O, numita oracol, marcheaza si evidentiazastarea elementului cautat. (Mai exact inverseaza faza amplitudiniistarii respective)

O|x〉⊗n ⊗ |y〉 = |x〉⊗n ⊗ |y ⊕ f (x)〉

7 / 26

Algoritmul lui Grover

Un oracol poate fi reprezentat de o procedura/functie booleanaf : {0, 1}n → {0, 1} cu f (x) = 1 daca x = x0 este o solutie si f (x) = 0 ıncaz contrar.

Forma generala a actiunii oracolului se poate scrie

O(|x〉 ⊗ |−〉) = (−1)f (x)|x〉 ⊗ |−〉,

asadar

O(|ψ〉 ⊗ |−〉) = O

(1√2n

2n−1∑x=0

|x〉 ⊗ |−〉

)=

1√2n

2n−1∑x=0

O (|x〉 ⊗ |−〉)

=1√2n

2n−1∑x=0

(−1)f (x)|x〉 ⊗ |−〉 (1)

8 / 26

Algoritmul lui Grover

Asadar, starea primului registru dupa ce am aplicat oracolul O este

|ψ1〉 =1√2n

2n−1∑x=0

(−1)f (x)|x〉,

adica avem o superpozitie a tuturor starilor bazei. Amplitudineaelementului cautat x0 este negativa ın timp ce toate celelalte amplitudinisunt pozitive. Prin urmare, am marcat elementul cautat.

Cu ajutorul urmatoarei transformari vom amplifica amplitudinea stariielementului cautat prin aplicarea operatorului 2|ψ〉〈ψ| − I - numitoperator de inversare fata de medie.

9 / 26

Algoritmul lui Grover

(|ψ〉〈ψ|)|α〉 =1

N

1 1 . . . 11 1 . . . 1...

... . . ....

1 1 . . . 1

α1

α2

...αN

=

1N

N∑i=1

αi

1N

N∑i=1

αi

...

1N

N∑i=1

αi

vectorul valorilor medii

Actiunea operatorului de inversare fata de medie este echivalenta cusuccesiunea de transformari HZH, unde Z este

|x〉 Z−→{|x〉 x = 0−|x〉 x > 0

pentru orice stare |x〉 din baza computationala. Astfel ca putem scrie

Z = 2|0〉〈0| − I

10 / 26

Algoritmul lui Grover

Operatorul Grover poate fi scris astfel

G = HZHO.

Mai mult, daca rescriem starea |ψ1〉, obtinem:

|ψ1〉 =1√2n

2n−1∑x=0

(−1)f (x)|x〉 = 2|ψ〉 − 2

2n|x0〉,

atunci dupa actiunea operatorului Grover vom avea

|ψG 〉 = (2|ψ〉〈ψ| − I )|ψ1〉 =2n−2 − 1

2n−2 |ψ〉+2√2n|x0〉

|ψG 〉 este starea primului registru dupa aplicarea iteratiei Grover.

11 / 26

Algoritmul lui Grover

Prin urmare, amplitudinea starii marcate creste cu O(

1√N

)iar

amplitudinile starilor nemarcate scad.

Pentru ca probabilitatea sa se masoare starea marcata sa fie apropiata de1, este necesara aplicarea iteratiei lui Grover de O(

√N) ori. (mai precis

de ceil(π4

√N) ori.

12 / 26

Algoritmul lui Grover

Algoritmul lui Grover are urmatorii pasi:

I Incep cu starea |0〉⊗n ⊗ |1〉;I Aplic transformarea Hadamard pentru a ajunge ıntr-o stare de

superpozitie;

I Aplic operatorul lui Grover de dπ4√Ne ori :

I aplic oracolul O;I aplic H⊗n;I aplic o poarta phase-shift conditional Z care face transformarea

|x〉 Z−→ −|x〉, pentru x 6= 0;I aplic H⊗n;

I Masor primii n qubiti.

13 / 26

Outline

Algoritmul lui Grover

Transformata Fourier: Aplicatii

14 / 26

Introducere

Transformarea Fourier este una dintre cele mai utilizate instrumentematematice ın inginerie (mai ales ın procesarea de semnale).In general, transformata Fourier se utilizeaza pentru

I ınlaturarea zgomotului din date;

I examinarea proprietatilor cristalelor;

I producerea de holograme;

15 / 26

Transformata Fourier discreta

Transformata Fourier discreta (DFT) se aplica ın general pe multimidiscrete de date .

DFT transforma un vector de N numere complexe (x0, . . . , xN−1) ıntr-unnou vector (y0, . . . , yN−1), dupa formula:

yk =1√N

N−1∑j=0

exp

(2πi · j · k

N

)xj ,

unde

I unde xj sunt numere complexe, j ∈ {0, . . . ,N − 1};I unde yk sunt numere complexe, k ∈ {0, . . . ,N − 1}I i =

√−1;

16 / 26

Transformarea Fourier discreta

Daca notam ω = exp

(2πi

N

)atunci vom putea scrie suma

yk =1√N

N−1∑j=0

ωjkxj .

Se poate observa ca transformata Fourier discreta este o operatie unitarape CN :

F =1√N

1 1 1 . . . 11 ω ω2 . . . ω−1

1 ω2 ω4 . . . ω−2

1 ω3 ω6 . . . ω−3

......

...1 ω1−N ω2N−2 . . . ω

17 / 26

Exemplu DFT:

Dat (x0, x1) = (1, 2), calculati vectorul y = (y0, y1)

k = 0 : y0 =1√2

2−1∑j=0

ωj0xj =1√2

(x0 + x1) =3√2.

k = 1 : y1 =1√2

2−1∑j=0

ωjxj =1√2

(x0 + eπix1) = − 1√2.

I Pentru a calcula DFT pentru o lista f de N numere ar trebui saefectam N2 ınmultiri.

I Insa, ın 1965 J. Cooley si J. Turkey au introdus un algoritm numitFast Fourier Transform(FFT), care calculeaza DFT ın timpN log(N).

I Spre exemplu, daca N − 106, algoritmul FFT va calcula DFT de unmilion de ori mai rapid comparativ cu varianta clasica.

I FFT este des utilizat pentru procesarea sunetelor, ın procesareaimaginilor pentru a ınlatura zgomotele.

18 / 26

Transformata Fourier Cuantica

Cum starea unui qubit este reprezentata sub forma unor vectori denumere complexe, am putea utiliza DFT si ın cazul calculului cuantic.

I Consideram un vector de stare |ψ〉 =N−1∑j=0

αj |j〉 =

α0

α1

. . .αN−1

I Transformata Fourier cuantica (QFT) a lui |ψ〉 este egala cu

QFT |ψ〉 =N−1∑k=0

yk |k〉

unde

yk =1√N

N−1∑j=0

αj exp

(2πijk

N

)

19 / 26

Exemplu de QTF

Consideram starea de doi qubiti

|ψ〉 = a00 |00〉+ a01 |01〉+ a10 |10〉+ a11 |11〉

unde N = 4. Atunci QFT |ψ〉 =N−1∑k=0

yk |k〉, unde

|0〉 = |00〉, |1〉 = |01〉, |2〉 = |10〉, |3〉 = |11〉

iar yk = 1√4

3∑j=0

αj exp(

2πijk4

). Mai precis avem

y0 =1√4

3∑j=0

αje0 =

1

2(α00 + α01 + α10 + α11)

y1 =1√4

3∑j=0

αjeπij2 =

1

2(α00 + e

πi2 α01 + eπiα10 + e

3πi2 α11)

20 / 26

Exemplu de QTF

y2 =1√4

3∑j=0

αje(πij) =

1

2(α00 + eπiα01 + e2πiα10 + e3πiα11)

y3 =1√4

3∑j=0

αje( 3πij

2 ) =1

2(α00 +

3πi

2α01 + e3πiα10 + e

9πi2 α11)

Daca notam ω = eiπ2 , si observam ca ω4 = e2iπ = 1, e

9iπ2 = e

iπ2 = i ,

atunci putem scrie QFT ın forma matriceala:

QFT =

1 1 1 11 ω ω2 ω3

1 ω2 1 ω2

1 ω3 ω2 ω

=

1 1 1 11 i −1 −i1 −1 1 −11 −i −1 i

Putem arata ca QFT este un operator unitar. Prin urmare, putemconstrui un circuit cuantic care efectueaza aceasta transformare.

21 / 26

Transformata Fourier cuantica

Transformata Fourier cuantica este folosita ıntr-un numar mare dealgoritmi, printre care si algoritmul lui Shor de factorizare.

Circuitul cuantic care implementeaza QFT este destul de simplu, dar maiavem nevoie sa introducem unele porti elementare

I Poarta Controlled - Rk :

Rk =

1 0 0 00 1 0 00 0 1 0

0 0 0 e2πi

2k

Rk

22 / 26

Transformata Fourier cuantica

I Avem nevoie de o poarta care sa faca swap ıntre qubiti

SWAP3 =

1 0 0 0 0 0 0 00 0 0 0 1 0 0 00 0 1 0 0 0 0 00 0 0 0 0 0 1 00 1 0 0 0 0 0 00 0 0 0 0 1 0 00 0 0 1 0 0 0 00 0 0 0 0 0 0 1

Actiunea portii SWAP3 este urmatoarea:

|000〉 → |000〉, |001〉 → |100〉, |010〉 → |010〉, |011〉 → |110〉

|100〉 → |001〉, |101〉 → |101〉, |110〉 → |011〉, |111〉 → |111〉

23 / 26

Transformata Fourier cuantica

Circuitul care evalueaza QFT este urmatorul:

24 / 26

Transformata Fourier cuanticaExemplu:

Daca consideram o starea cu doi qubiti, atunci QFT va fi descrisa deurmatorul circuit:

|I 〉H R2

H

ϕ1 ϕ2 ϕ3

|O〉

|ϕ1〉 = U1|I 〉, |ϕ2〉 = U2|ϕ1〉, |ϕ3〉 = U3|ϕ2〉, |Q〉 = U4|ϕ3〉.

Se poate verifica prin calcul ca

QFT = U4U3U2U1 =1

2

1 1 1 11 i −1 −i1 −1 1 −11 −i −1 i

,

25 / 26

Transformata Fourier cuantica

I Toate portile Ui , i ∈ {1, 2, 3, 4} sunt unitare, deci si QFT este otransformare unitara;

I Circuitul are n porti Hadamard, n(n − 1)/2 porti Controlled-Rk ,adica, ın total n(n + 1)/2 porti elementare, la care se adauga [n/2]porti SWAP, unde [·] reprezinta partea ıntreaga.

I Asadar, complexitatea algoritmului este O(n2).

26 / 26