Quantum Computing [8mm] Curs 10andreea.arusoaie/QC/QC10.pdf · 2021. 1. 4. · Curs 10 Andreea...

Quantum Computing

Curs 10

Andreea Arusoaie

December 7, 2020

1 / 27

Outline

Algoritmi cuantici

Algoritmul lui Deutsch

Algoritmul Deutsch-Jozsa

2 / 27

Algoritmi cuantici

Algoritmii cuantici sunt ın general potriviti pentru a studia uneleproprietati globale ale unei functii sau ale unei secvente de date (spreexemplu, pentru a gasi perioada unei functii, media unei secvente, etc),ınsa nu pentru a gasi detalii. (nu vom putea gasi valoarea unei functii)

Vom prezenta cei mai cunoscuti algoritmi cuantici ın ordinea dificultatiilor

I Algoritmul lui Deutsch

I Algoritmul lui Deutsch-Jozsa

I Algoritmul lui Simon (determina patternul ın functii)

I Algoritmul de cautare al lui Grover (poate cauta ıntr-o multime cu nelemente ın timp

√n.

I Algoritmul de factorizare al lui Shor (factorizeaza numerele ın timppolinomial)

3 / 27

Paralelismul cuantic

I Este o caracteristica fundamentala a algoritmilor cuantici;

I Paralelismul cuantic perminte calculatoarelor cuantice sa evalueze ofunctie f (x) pentru mai multe valori ale lui x simultan;

I Spre deosebire de paralelismul clasic, unde mai multe circuite, fiecareconstruit sa calculeze f (x), sunt activate simultan, aici un singurcircuit este construit pentru a calcula functia f (x) simultan, pentrumai multe valori ale lui x , folosind proprietatea de superpozitie.

I Calculul cuantic are nevoie ın plus si de posibilitatea de a extrageinformatii referitoare la mai multe valori ale lui f (x).

4 / 27

Outline

Algoritmi cuantici



5 / 27


I Cel mai simplu exemplu de algoritm cuantic. Algoritmul lui Deutschcombina paralelismul cuantic cu o alta proprietate a mecaniciicuantice: interferenta.

ProblemaPresupunem ca avem un device care evalueaza o functie

f : {0, 1} → {0, 1}.

Consideram ca acest device este ca un blackbox. Nu putem sa privim ıninterior pentru a vedea cum functioneaza.Putem afla informatii doar daca ıi dam un input a ∈ {0, 1} si permitemdevice-ului sa evalueze f (a) ∈ {0, 1}. Rezultatele posibile vor fi

Inputf0 f1 f2 f3

0 0 0 1 11 0 1 0 1

6 / 27


Inputf0 f1 f2 f3

0 0 0 1 11 0 1 0 1

Dorim sa determinam daca functia f este constanta (exemplu f0, f3) saudaca este balansata(adica fiecare output apare de acelasi numar de ori;spre exemplu f1, f2)

Varianta clasica necesita doua evaluari ale functiei.

Varianta cuantica

I ar trebui ca black box-ul sa fie o operatie cuantica valida (sacorespunda unei transformari unitare)

I Nu este suficient sa consideram o poarta ce actioneaza pentru unqubit, spre exemplu

|a〉 |f (a)〉f

7 / 27

Algoritmul lui DeutschDaca, spre exemplu, f = f0 atunci poarta corespunzatoare ar aveamatricea asociata (

1 10 0

)nu este unitara.

Vom considera, pentru orice functie f : {0, 1} → {0, 1}, o poarta pentru2-qubiti, notata Uf , ce actioneaza astfel

|a〉 |a〉

|b〉 |b ⊕ f (a)〉Uf

Daca f = f2, f (0) = 1, f (1) = 0, atunci matricea corespunzatoare lui Uf

este 0 1 0 01 0 0 00 0 1 00 0 0 1

8 / 27


Presupunem ca avem acces la transformarea Uf pentru o functief : {0, 1} → {0, 1} si vrem sa determinam daca f este constanta saubalansata.

Folosind un algoritm cuantic este necesara doar o singura aplicare a portiiUf pentru a rezolva problema (comparativ cu doua evaluari - cazul clasic)ca ın urmatorul circuit

|0〉

|1〉

H

Uf

H

H

Output-ul este un single bit si are urmatoarea interpretare

I rezultatul 0 indica faptul ca functia este constanta;

I rezultatul 1 indica faptul ca functia este balansata.

9 / 27

Algoritmul lui DeutschIncercam sa evaluam circuitul

|01〉 H⊗H−→ 1√2

(|0〉+ |1〉)⊗ 1√2

(|0〉 − |1〉)

=1

2[|0〉 ⊗ (|0〉 − |1〉) + |1〉 ⊗ (|0〉 − |1〉)]

Aplic poarta Uf

Uf−→ 1

2|0〉 ⊗ (|0⊕ f (0)〉 − |1⊕ f (0)〉) +

1

2|1〉 ⊗ (|0⊕ f (1)〉 − |1⊕ f (1)〉)

Folosim ca

|0⊕ a〉 − |1⊕ a〉 = (−1)a(|0〉 − |1〉), a ∈ {0, 1},

si obtinem

1

2(−1)f (0) |0〉 ⊗ (|0〉 − |1〉) +

1

2(−1)f (1) |1〉 ⊗ (|0〉 − |1〉)

10 / 27

Algoritmul lui DeutschAsadar, dupa aplicarea portii Uf am obtinut starea(

1√2

(−1)f (0) |0〉+1√2

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

1√2|0〉 − 1√

2|1〉)

sau, mai simplu

(−1)f (0)(

1√2|0〉+

1√2

(−1)f (0)⊕f (1) |1〉)⊗(

1√2|0〉 − 1√

2|1〉)

Observam ca al doilea qubit nu se modifica ın urma aplicarii portii Uf ,ınsa au aparut factorii (−1)f (0) si (−1)f (1) ın primul qubit, fenomennumit “phase kick-back” si ıntalnit des ın algoritmii cuantici.

In final, aplicam poarta Hadamard primului qubit si rezulta starea

(−1)f (0) |f (0)⊕ f (1)〉 ⊗(

1√2|0〉 − 1√

2|1〉)

11 / 27


Unde am folosit ca

H

(1√2|0〉+

1√2

(−1)a |1〉)

= |a〉,

unde a ∈ {0, 1}(se poate verifica tratand cazurile a = 0 si a = 1).

Masurand primul qubit, vom obtine f (0)⊕ f (1), adica valoarea este 0doar daca f este constanta si 1 daca f este balansata.

12 / 27

Un algoritm simplu de cautare

Consideram o functie f : {0, 1}2 → {0, 1}, care poate fi una dintreurmatoarele patru functii:

f00 f01 f10 f11

input output00 101 010 011 0

input output00 001 110 011 0

input output00 001 010 111 0

input output00 001 010 011 1

Vrem sa determinam cu exactitate care dintre aceste patru functii este.Dorim sa gasim care este inputul pentru care functia are valoarea 1.

I Utilizand calculul clasic avem nevoie de 3 evaluari pentru a rezolvaproblema.

I Utilizand algoritmii cuantici vom avea nevoie doar de o singuraevaluare pentru a rezolva problema.

13 / 27


Circuitul care descrie prima parte a procedurii este urmatorul

|0〉

|0〉

|1〉

H

Uf

?

H

H

Evaluam circuitul:

I Aplic Hadamard pe cei trei qubiti si obtinem

|001〉 H3

−→(

1

2|00〉+

1

2|01〉+

1

2|10〉+

1

2|11〉

)⊗(

1√2|0〉 − 1√

2|1〉)

14 / 27

Un algoritm simplu de cautareI Apoi aplicam poarta Uf . Asadar, avem:

1

2

((−1)f (00) |00〉+ (−1)f (01) |01〉+ (−1)f (10) |10〉+ (−1)f (11) |11〉

)⊗(

1√2|0〉 − 1√

2|1〉)

I Ultimul qubit este independent de primii doi, asa ca ıl vom neglija.Prin urmare, ramanem cu urmatoarele patru posibilitati

f = f00 ⇒ |ϕ00〉 = −1

2|00〉+

1

2|01〉+

1

2|10〉+

1

2|11〉

f = f01 ⇒ |ϕ01〉 =1

2|00〉 − 1

2|01〉+

1

2|10〉+

1

2|11〉

f = f10 ⇒ |ϕ10〉 =1

2|00〉+

1

2|01〉 − 1

2|10〉+

1

2|11〉

f = f11 ⇒ |ϕ11〉 =1

2|00〉 − 1

2|01〉+

1

2|10〉 − 1

2|11〉

15 / 27


Multimea {ϕ00, ϕ01, ϕ10, ϕ11} este ortonormala, adica

〈ϕab|ϕcd〉 =

{1 daca a = c si b = d0 ın rest

Prin urmare, am putem construi un circuit care sa ne determine starilecautate (punand vectorii pe coloana si apoi aplicand conjugata). Acestcircuit va avea matricea

U =

− 1

212

12

12

12 − 1

212

12

12

12 − 1

212

12

12

12 − 1

2

care actioneaza astfel

U|ϕab〉 = |ab〉

16 / 27

Outline

Algoritmi cuantici



17 / 27


Problema:

Se considera o functie f : {0, 1}n → {0, 1}, n ∈ N∗ despre care se stie caeste

1. fie f este constanta: adica fie f (x) = 0,∀x ∈ {0, 1}n sauf (x) = 1,∀x ∈ {0, 1}n.

2. fie f este balansata: adica numarul de input-uri x ∈ {0, 1}n pentrucare functia ia valorile 0 si 1 sunt egale:

|{x ∈ {0, 1}n : f (x) = 0}| = |{x ∈ {0, 1}n : f (x) = 1}| = 2n−1

Vrem sa determinam daca functia f este balansata sau este constanta.

18 / 27


Putem presupune, la fel ca ın cazurile precedente, ca transformarea Uf

este

Uf (|x〉 ⊗ |b〉) = |x〉 ⊗ |b ⊕ f (x)〉,∀x ∈ {0, 1}n si b ∈ {0, 1}.

In mod clasic, am putea rezolva problema daca am considera variantaprobabilista, acceptand o eroare de probabilitate.

I Aleg, k input-uri random, x1, . . . , xk ∈ {0, 1}n;

I Evaluam f (xi ), i = 1, 2, . . . , k .

I Vom spune ca f este constanta daca f (x1) = . . . = f (xn) sibalansata ın caz contrar.

I Daca f este constanta, atunci probabilitatea de eroare este 0, altfel,

daca f este balansata, algoritmul va gresi cu o probabilitate1

2k−1 .

I Daca cerem ca algoritmul sa returneze rezultatul corect, ar trebui, ıncel mai rau caz, sa evaluam de 2n−1 + 1 ori.

19 / 27

Algoritmul Deutsch-JozsaDaca consideram varianta cuantica, putem sa determinam daca functiaeste balansata sau constanta dintr-o singura evaluare, cu ajutorulurmatorului circuit Deutsch-Jozsa:

|0〉

|0〉

......

|0〉

|1〉

H

Uf

H

H H

H H

H

In urma efectuarii celor n masuratori, vom obtine ca:I functia era constanta daca toti cei n rezultati sunt 0;I functia era balansata daca macar un bit rezultat este 1.

20 / 27

Transformata Hadamard

Am vazut ca pentru orice a ∈ {0, 1} avem

H|a〉 =1√2|0〉+

1√2

(−1)a|1〉.

Putem scrie relatia de mai sus si astfel:

H|a〉 =1√2

∑b∈{0,1}

(−1)ab|b〉.

Daca vom considera o stare cu doi qubiti |x〉 = |x1x2〉, atunci

(H ⊗ H) |x〉 =

1√2

∑y1∈{0,1}

(−1)x1y1 |y1〉

· 1√

2

∑y2∈{0,1}

(−1)x2y2 |y2〉

=

1

2

∑y∈{0,1}2

(−1)x1y1+x2y2 |y〉

21 / 27

Transformata Hadamard

Putem gerenaliza la n qubiti, calculand H⊗n = H ⊗ . . .⊗ H, astfel

H⊗n|x〉 =1√2n

∑y∈{0,1}n

(−1)x1y1+...+xnyn |y〉,

pentru orice x ∈ {0, 1}n. Mai mult, daca notam

x · y not=

n∑i=1

xiyi (mod2)

atunci putem scrie

H⊗n|x〉 =1√2n

∑y∈{0,1}n

(−1)x·y |y〉,

22 / 27


Evaluand circuitul lui Deutsch-Jozsa pentru input-ul |00 . . . 01〉 dupaaplicarea portilor Hadamard, avem

1√2n

∑x∈{0,1}n

|x〉 ⊗(

1√2|0〉 − 1√

2|1)

Aplicam poarta Uf , iar starea va deveni

1√2n

∑x∈{0,1}n

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

1√2|0〉 − 1√

2|1〉)

Neglijand ultimul qubit si aplicand poarta Hadamard primilor n qubiti,vom obtine

1√2n

∑x∈{0,1}n

(−1)f (x)

1√2n

∑y∈{0,1}n

(−1)x·y |y〉

23 / 27


Mai simplu, putem scrie

1

2n

∑y∈{0,1}n

∑x∈{0,1}n

(−1)f (x)+x·y |y〉

Noi dorim sa vedem care este probabilitatea ca toate masuratorile sa fie0. Amplitudinea asociata starii |0n〉 este

1

2n

∑x∈{0,1}n

(−1)f (x).

Prin urmare, probabilitatea ca toate masuratorile sa fie 0 este∣∣∣∣∣∣ 1

2n

∑x∈{0,1}n

(−1)f (x)

∣∣∣∣∣∣2

=

{1 daca f este constanta0 daca f este balansata

24 / 27

Algoritmul lui Deutsch-Jozsa

Sumarizand..

Input: O poarta Uf care efectueaza transformarea

|x〉 ⊗ |y〉 → |x〉 ⊗ |y ⊕ f (x)〉.

Se stie ca f (x) este fie constanta pentru toate valorile ale lui x sau feste balansata.

Output: 0 daca si numai daca f este constanta.

Runtime: O singura evaluare a lui Uf

25 / 27


Procedura:

1. se initializa starea: |0〉n ⊗ |1〉;2. se creeaza o superpozitie folosind poarta Hadamard:

1√2n

∑x∈{0,1}n

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

1√2|0〉 − 1√

2|1〉)

3. Se calculeaza functia f cu ajutorul portii Uf :

1√2n

∑x∈{0,1}n

(−1)f (x)

1√2n

∑y∈{0,1}n

(−1)x·y |y〉

⊗( 1√2|0〉 − 1√

2|1〉).

4. Aplicam poarta Hadamard asupra primilor n qubiti :

1

2n

∑y∈{0,1}n

∑x∈{0,1}n

(−1)f (x)+x·y |y〉

⊗ ( 1√2|0〉 − 1√

2|1〉)

5. Masuram

26 / 27


I Un calculator cuantic poate rezolva problema lui Deutsch doar cuajutorul unei evaluari a functiei f , spre deosebire de cazul clasic carenecesita 2n−1 + 1 evaluari.

I Un algoritm probabilist poate sa rezolve problema alegand randomun x si verificand daca f este constanta sau balansata cuprobabilitate mare.

I Algoritmul Deutsch-Jozsa nu are aplicatii practice, ınsa esteimportant sa ıl studiem deoarece ne ajuta sa ıntelegem algoritmiimai importanti ce o sa apara.

27 / 27

Quantum Computing [8mm] Curs 10andreea.arusoaie/QC/QC10.pdf · 2021. 1. 4. · Curs 10 Andreea...

Documents

Transcript of Quantum Computing [8mm] Curs 10andreea.arusoaie/QC/QC10.pdf · 2021. 1. 4. · Curs 10 Andreea...