Úvod do kvantového počítání

Úvod do kvantového poˇcítání 2. pˇrednáška

Miroslav Dobšíˇcek Katedra poˇcítaˇcu, ˚ Fakulta elektrotechnická ˇ Ceské vysoké uˇcení technické v Praze

17. bˇrezna 2005

Miroslav Dobšíˇcek

Úvod do kvantového poˇcítání

Opakování

ˇ Cást I Pˇrehled z minulé hodiny



Opakování

Kvantové poˇcítaˇce DNA poˇcítaˇce

Alternativní výpoˇcetní modely

ˇ Hledání silnejšího výpoˇcetního modelu než Turinguv ˚ stroj ⇒ poražení Silné Churchovi teze: Problém je ˇrešitelný v polynomiálním cˇ ase, práveˇ tehdy když je v polynomiálním cˇ ase ˇrešitelný na TM. "Známé" modely: Kvantové poˇcítaˇce DNA poˇcítaˇce



Opakování


Kvantové poˇcítaˇce

Založeno na kvantové mechanice Aplikace Rychlejší algoritmy Generování náhodných cˇ ísel Kvantová distribuce klíˇcu˚

Fyzická realizace NMR Cavity QED Ion trap



Opakování


DNA poˇcítaˇce

Založeno na "puzzle" párování nukleotidu˚ T, C, G, A Aplikace experimenty s problémem obchodního cestujícího (NPC problém)

Fyzická realizace Nukleotidová polévka s míchaˇcem a dodávkami cukru



Stavový prostor Lineární operátory Postuláty

ˇ Cást II Dnešní pˇrednáška




Vektorové prostory Vnitˇrní souˇcin Hilbertuv ˚ prostor

Co je to qubit? Kvantový bit - qubit Obecný tvar: |φi = α|0i + β|1i Qubit žije v Hilbertoveˇ prostoru H2 . B = {|0i, |1i} tvoˇrí bázi prostoru. Evoluce kvantového systému je unitární. ˇ rení zpusobuje Meˇ ˚ kolaps qubitu na jeden z bázových vektoru. ˚ α a β jsou komplexní amplitudy.





Notaˇcní zápis podle Diraca

|φi - sloupcový vektor (nazývaný ket), |φi = (x1 , x2 , . . . )T hφ| - ˇrádkový vektor (nazývaný bra), hφ| = (|φi)∗ hφ|ψi - vnitˇrní souˇcin |φi ⊗ |ψi - tensorový souˇcin ||φ|| - norma





ˇ Vektorový prostor V nad telesem F

ˇ Množinu V nazveme vektorovým prostorem nad telesem F ⇐⇒ máme definované operace + : V × V → V (vektorové sˇcítání) a · : F × V → V (skalární násobení) a platí: 1

(V , +) je komutativní grupa.

2

α|φi = |φiα

3

α(β|φi) = (αβ)|φi

4

(α + β)|φi = α|φi + β|φi

5

α(|φi + |ψi) = α|φi + α|ψi





Vnitˇrní souˇcin h·|·i

Necht’ je V komplexní vektorový prostor. Funkci h·|·i : V × V → C nazveme vnitˇrní souˇcin, práveˇ tehdy když 1

hφ|φi ∈ R,

hφ|φi ≥ 0,

2

hφ|ψi = hψ|φi∗

3

hφ|(|ψi + |λi) = hφ|ψi + hφ|λi

4

hφ|αψi = αhφ|ψi

5

hαφ|ψi = α∗ hφ|ψi


hφ|φi = 0 ⇔ |φi = 0




Hilbertuv ˚ prostor Hilberuv ˚ prostor je úplný komplexní vektorový prostor p H s vnitˇrním souˇcinem h·|·i a definovanou normou ||φ|| = hφ|φi Normalizovaný (jednotkový) vektor |φi ⇔ ||φ|| = 1 Ortonormální systém B = {|b1 i, |b2 i, . . . } tvoˇrí bázi prostoru H, práveˇ tehdy když pro všechny vektory |φi mužeme ˚ psát X |φi = λi |bi i i

Ortonormální bázové vektory - normalizované bázové vektory Miroslav Dobšíˇcek




Vlastnosti Hilbertova prostoru ˇ Hilbertuv ˚ prostor je H je isomorfní k telesu Cn. ˇ Zápis ket a bra vektoru˚ umožnuje vnitˇrní souˇcin vyjádˇrit ˇ jako bežné násobení matic. Pokud H1 a H2 jsou Hilbertovy prostory, pak tensorový souˇcin   X X  H = H1 ⊗ H2 = cij |i, ji : cij ∈ C   |ii∈B1 |ji∈B2

je také Hilbertuv ˚ prostor s bází B = B1 × B2 . dim H = dim H1 · dim H2





Pˇríklady bází Standardní báze: |0i =

1 0

,

0 1

|1i =

|φi = α|0i + β|1i =

α β

Duální báze: 0

|0 i =

1 1

,

0

|1 i =

1 −1

1 |00 i = √ (|0i + |1i) 2 1 |10 i = √ (|0i − |1i) 2 Miroslav Dobšíˇcek



Lineární operátory Necht’ je V vektorový prostor. Funkci (operátor) A : V → V nazveme lineární práveˇ tehdy když platí A (λ|φi + µ|ψi) = λA|φi + µA|ψi Operátor A zapisujeme jako cˇ tvercovou matici n × n.   a0,0 . . . a0,n−1   .. .. A=  . . an−1,0 . . .


an−1,n−1



Lineární operátory Operátor A mužeme ˚ také napsat jako X aij |iihj| A= i,j

|ii, |ji odpovídají standardním bázovým vektorum. ˚ Pro matici 2 × 2 dostaneme: a0,0 a0,1 = a0,0 |0ih0| + a0,1 |0ih1| + a1,0 |1ih0| + a1,1 |1ih1| a1,0 a1,1 Pro prvky matice aij mužeme ˚ psát aij = hi|A|ji Miroslav Dobšíˇcek



Duležité ˚ druhy operátoru˚ Sdružený operátor ∗ P Operátor A† = AT = i,j aji∗ |iihj| nazveme sdruženým operátorem k operátoru A. Operátor samo sdružený (self-adjoint, Hermitián) ⇔ A† = A vlastní cˇ ísla Hermitiánu jsou vždy reálná

unitární ⇔ A† A = AA† = I → A−1 = A† unitární operátor zachovává vnitˇrní souˇcin; hAφ|Aψi = hφ|ψi




Kvantový stav Evoluce ˇ rení Meˇ

Postuláty kvantové mechaniky 1. Kvantový stav Libovolnému fyzickému systému S muže ˚ být pˇriˇrazen komplexní Hilbertuv ˚ prostor H, kterému ˇríkáme stavový prostor systému S. Stav systému S je úplneˇ popsán vektorem |φi ∈ H s normou ||φ|| = 1, kterému ˇríkáme stavový vektor systému S. Nejjednoduší netriviální kvantoveˇ mechanický systém je kvantový bit - qubit z prostoru H2 . Stav |φi muže ˚ být zapsán jako lineární kombinace (superpozice) dvou bázových vektoru˚ oznaˇcaných |0i, |1i. |φi = α|0i + β|1i kde α, β ∈ C


a |α|2 + |β|2 = 1




Postuláty kvantové mechaniky 2. Evoluce Doˇcasný vývoj uzavˇreného kvantového systému je popsán Schrödingerovou rovnicí i~

∂ |φi = H|φi ∂t

kde ~ je Planckova konstanta a H je Hamiltonián popisující dynamiku v prostoru H. Protože unitární operátor U lze vyjádˇrit jako U = e−iH , mužeme ˚ druhý postulát pˇreformulovat do tvaru: |φt2 i = U|φt1 i, Miroslav Dobšíˇcek

pro cˇ as t1 ≤ t2 Úvod do kvantového poˇcítání



Pˇríklad evoluce

Hadamardova rotace ˇ Jeden z nejduležit ˚ ejších jedno-qubitových operátoru˚ je Hadamardova rotace. 1 1 1 H=√ 2 1 −1 ! Odpovídá diskrétní Fourieroveˇ transformaci v Z2 . !





Hadamardova rotace Pˇríklady: 1

1 H|0i = √ (|0i + |1i) 2 2

1 H|1i = √ (|0i − |1i) 2 3

ˇ Obecne:

1 Hn |xi = √ 2n

X

(−1)x.y |y i

y ∈{0,1}n

kde x.y = ⊕ni=1 xi yi .





Postuláty kvantové mechaniky ˇ rení 3. Meˇ ˇ rení je popsáno self-adjoint operátorem A (observable) se Meˇ spektrální dekompozicí A=

k X

ai Pi =

i=0

k X

ai |pi ihpi |,

i=0

kde ai jsou unikátní vlastní hodnoty (eigenvalues) a Pi projekce do podprostoru urˇceného vlastními vektory (eigenvectors) |pi i. Vlastní hodnoty odpovídají možným výsledkum ˚ získaných ˇ rení. pomocí meˇ





ˇ rení Výsledky meˇ ˇ rením stavu |φi získáme výsledek ai s pravdepodobností ˇ Meˇ Pr(ai ) = ||Pi |φi||2 = hφ|Pi |φi . ˇ rení Destruktivní dusledek ˚ meˇ ˇ rení kolabuje na stav Stav |φi po meˇ Pi |φi

|φ0 i = p

hφ|Pi |φi

.

⇒ pokud není |φi shodný s vlastním vektorem, který urˇcuje projekˇcní prostor, je puvodní ˚ superpozice stavu |φi nenávratneˇ zniˇcena. Miroslav Dobšíˇcek




ˇ Prum ˚ erná hodnota vlastních cˇ ísel ˇ rení operátorem A se mužeme ˇ Pˇri meˇ ˚ ptát, jaká bude prum ˚ erná ˇ rená hodnota. Víme, že nameˇ Pr (ai ) = ||Pi |φi||2 = hφ|Pi |φi, A=

k X

ai Pi .

i=0

Potom EA =

k X i=0

Pr(ai )ai =

k X

hφ|ai Pi |φi = hφ|A|φi .

i=0





Výpoˇcet vlastních vektoru˚ a cˇ ísel ˇ rovnici Vlastní cˇ ísla a vektory splnují A|v i = a|v i Úpravy: A|v i = a.I.|v i (A − a.I)|v i = 0 pro det (A − a.I) 6= 0 ⇒ |v i = 0 pro det (A − a.I) = 0 ⇒ |v i = 6 0





Výpoˇcet vlastních vektoru˚ a cˇ ísel Pro operátor A =

0 1 1 0

0−a 1 1 0−a

vypoˇcteme vlastní cˇ ísla:

= a2 − 1 = 0

⇒

a1,2 = ±1

Výpoˇcet vlastního vektoru pro a1 = 1 : −1 1 v1 0 · ⇒ v1 = v2 = 1 −1 v2 0 Výpoˇcet vlastního vektoru pro a2 = −1 : 1 1 v1 0 · = ⇒ v1 = −v2 1 1 v2 0 Miroslav Dobšíˇcek

⇒

|p1 i =

⇒


|p2 i =

1 1

1 −1



Duální báze Po normalizaci dostaneme 1 1 1 1 |p1 i = √ a |p2 i = √ . 2 1 2 −1 Duální báze Výše uvedené vektory tvoˇrí tzv. duální bázi oznaˇcovanou {|00 i, |10 i}. Platí |00 i = |10 i =

√1 2 √1 2

(|0i + |1i) (|0i − |1i)



Úvod do kvantového počítání

Recommend Documents