INFORMATYKA KWANTOWA

background image

1/35

Zakład Optyki Nieliniowej

http://zon8.physd.amu.edu.pl

Informatyka kwantowa

wykład z cyklu

Zaproszenie do fizyki

Ryszard Tanaś

Umultowska 85, 61-614 Poznań

mailto:tanas@kielich.amu.edu.pl

background image

2/35

Spis treści

1 Komputer kwantowy liczy już do 15!

4

2 Informacja klasyczna — bit

6

2.1

Definicja

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2

Informacja jest wielkością fizyczną

. . . . . . . . . . . . . . .

8

3 Informacja kwantowa — qubit (kubit)

9

3.1

Definicja

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2

Kubit (spin) na sferze Blocha

. . . . . . . . . . . . . . . . . .

10

4 Bramki kwantowe

16

4.1

Klasyczne bramki logiczne

. . . . . . . . . . . . . . . . . . . .

16

4.1.1

jednobitowe

. . . . . . . . . . . . . . . . . . . . . . . .

16

4.1.2

dwubitowe

. . . . . . . . . . . . . . . . . . . . . . . .

17

4.2

Bramki kwantowe

. . . . . . . . . . . . . . . . . . . . . . . . .

18

4.2.1

jednobitowe

. . . . . . . . . . . . . . . . . . . . . . . .

18

4.2.2

dwubitowe

. . . . . . . . . . . . . . . . . . . . . . . .

22

background image

3/35

5 Algorytm Shora

26

5.1

Motywacja

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

5.2

Algorytm RSA

. . . . . . . . . . . . . . . . . . . . . . . . . . .

28

5.3

Kwantowa faktoryzacja

. . . . . . . . . . . . . . . . . . . . . .

31

6 Kryptografia kwantowa

33

7 Zaproszenie do fizyki

34

background image

4/35

Komputer kwantowy liczy już do 15!

Rysunek 1: Wiedza i Życie, maj 2002

background image

5/35

Rysunek 2: Isaac L. Chuang i jego procesor kwantowy

background image

6/35

Informacja klasyczna — bit

Definicja

Niech

A

będzie zdarzeniem losowym, które występuje z prawdopodobień-

stwem

P (A)

. Jeśli dowiadujemy się, że takie zdarzenie nastąpiło, to uzy-

skujemy

I(A)

=

log

1

P (A)

jednostek informacji.

Jeśli logarytm jest przy podstawie 2, to jednostka

informacji nazywa się

bit

. Zauważmy, że dla

P (A) =

1
2

,

I(A) = 1

.

background image

6/35

Informacja klasyczna — bit

Definicja

Niech

A

będzie zdarzeniem losowym, które występuje z prawdopodobień-

stwem

P (A)

. Jeśli dowiadujemy się, że takie zdarzenie nastąpiło, to uzy-

skujemy

I(A)

=

log

1

P (A)

jednostek informacji.

Jeśli logarytm jest przy podstawie 2, to jednostka

informacji nazywa się

bit

. Zauważmy, że dla

P (A) =

1
2

,

I(A) = 1

.

Jeden bit to ilość informacji jaką uzyskujemy kiedy zachodzi jedna z dwóch

alternatywnych możliwości

,

np. kiedy poznajemy wynik rzutu monetą.

background image

6/35

Informacja klasyczna — bit

Definicja

Niech

A

będzie zdarzeniem losowym, które występuje z prawdopodobień-

stwem

P (A)

. Jeśli dowiadujemy się, że takie zdarzenie nastąpiło, to uzy-

skujemy

I(A)

=

log

1

P (A)

jednostek informacji.

Jeśli logarytm jest przy podstawie 2, to jednostka

informacji nazywa się

bit

. Zauważmy, że dla

P (A) =

1
2

,

I(A) = 1

.

Jeden bit to ilość informacji jaką uzyskujemy kiedy zachodzi jedna z dwóch

alternatywnych możliwości

,

np. kiedy poznajemy wynik rzutu monetą.

Przy rzucie kostką do gry

P (A) =

1
6

i poznanie wyniku daje

I(A) = log

2

6

≈ 2.58

bitów.

background image

7/35

Niech

{A

1

, A

2

, . . . , A

n

}

będą zdarzeniami niezależnymi występującymi z praw-

dopodobieństwami

{P (A

1

), P (A

2

), . . . , P (A

n

)

}

, wtedy

background image

7/35

Niech

{A

1

, A

2

, . . . , A

n

}

będą zdarzeniami niezależnymi występującymi z praw-

dopodobieństwami

{P (A

1

), P (A

2

), . . . , P (A

n

)

}

, wtedy

H

=

X

i

P (A

i

) log

1

P (A

i

)

=

X

i

P (A

i

) log P (A

i

)

określa średnią informację (entropię) takiego

źródła informacji

.

background image

7/35

Niech

{A

1

, A

2

, . . . , A

n

}

będą zdarzeniami niezależnymi występującymi z praw-

dopodobieństwami

{P (A

1

), P (A

2

), . . . , P (A

n

)

}

, wtedy

H

=

X

i

P (A

i

) log

1

P (A

i

)

=

X

i

P (A

i

) log P (A

i

)

określa średnią informację (entropię) takiego

źródła informacji

.

Weźmy np.

Zdarzenie

A

1

A

2

A

3

Prawdopodobieństwo

1
2

1
3

1
6

background image

7/35

Niech

{A

1

, A

2

, . . . , A

n

}

będą zdarzeniami niezależnymi występującymi z praw-

dopodobieństwami

{P (A

1

), P (A

2

), . . . , P (A

n

)

}

, wtedy

H

=

X

i

P (A

i

) log

1

P (A

i

)

=

X

i

P (A

i

) log P (A

i

)

określa średnią informację (entropię) takiego

źródła informacji

.

Weźmy np.

Zdarzenie

A

1

A

2

A

3

Prawdopodobieństwo

1
2

1
3

1
6

wtedy

H

=

1

2

log

1

2

1

3

log

1

3

1

6

log

1

6

≈ 1.46

background image

8/35

Informacja jest wielkością fizyczną

Zasada Landauera

Wymazanie jednego bitu informacji w otoczeniu o temperaturze

T

wymaga

straty energii (wydzielenia ciepła) o wartości co najmniej

kT ln 2

background image

8/35

Informacja jest wielkością fizyczną

Zasada Landauera

Wymazanie jednego bitu informacji w otoczeniu o temperaturze

T

wymaga

straty energii (wydzielenia ciepła) o wartości co najmniej

kT ln 2

Komputer jest układem fizycznym

Jeden bit informacji jest reprezentowany, w układach fizycznych z których

zbudowane są obecne komputery, przez około

10

10

atomów!

background image

8/35

Informacja jest wielkością fizyczną

Zasada Landauera

Wymazanie jednego bitu informacji w otoczeniu o temperaturze

T

wymaga

straty energii (wydzielenia ciepła) o wartości co najmniej

kT ln 2

Komputer jest układem fizycznym

Jeden bit informacji jest reprezentowany, w układach fizycznych z których

zbudowane są obecne komputery, przez około

10

10

atomów!

Jeśli obecny trend w miniaturyzacji układów scalonych się utrzyma, to około

roku 2020 jeden bit będzie reprezentowany przez jeden atom!

background image

8/35

Informacja jest wielkością fizyczną

Zasada Landauera

Wymazanie jednego bitu informacji w otoczeniu o temperaturze

T

wymaga

straty energii (wydzielenia ciepła) o wartości co najmniej

kT ln 2

Komputer jest układem fizycznym

Jeden bit informacji jest reprezentowany, w układach fizycznych z których

zbudowane są obecne komputery, przez około

10

10

atomów!

Jeśli obecny trend w miniaturyzacji układów scalonych się utrzyma, to około

roku 2020 jeden bit będzie reprezentowany przez jeden atom!

Fizyka w skali pojedynczego atomu to fizyka kwantowa — rządzą tu prawa

mechaniki kwantowej.

background image

9/35

Informacja kwantowa — qubit (kubit)

Definicja

Kwantowym odpowiednikiem klasycznego

bitu

jest dowolny układ dwusta-

nowy:

dwa poziomy atomu, spin połówkowy, foton o dwóch wzajemnie

ortogonalnych stanach polaryzacji, itp.

background image

9/35

Informacja kwantowa — qubit (kubit)

Definicja

Kwantowym odpowiednikiem klasycznego

bitu

jest dowolny układ dwusta-

nowy:

dwa poziomy atomu, spin połówkowy, foton o dwóch wzajemnie

ortogonalnych stanach polaryzacji, itp.

Taki układ to

qubit

(quantum bit); po polsku

kubit

.

background image

9/35

Informacja kwantowa — qubit (kubit)

Definicja

Kwantowym odpowiednikiem klasycznego

bitu

jest dowolny układ dwusta-

nowy:

dwa poziomy atomu, spin połówkowy, foton o dwóch wzajemnie

ortogonalnych stanach polaryzacji, itp.

Taki układ to

qubit

(quantum bit); po polsku

kubit

.

Klasyczny bit może przyjmować tylko dwie wartości

{0, 1}

; układ znajduje

się albo w stanie 0 albo w stanie 1.

background image

9/35

Informacja kwantowa — qubit (kubit)

Definicja

Kwantowym odpowiednikiem klasycznego

bitu

jest dowolny układ dwusta-

nowy:

dwa poziomy atomu, spin połówkowy, foton o dwóch wzajemnie

ortogonalnych stanach polaryzacji, itp.

Taki układ to

qubit

(quantum bit); po polsku

kubit

.

Klasyczny bit może przyjmować tylko dwie wartości

{0, 1}

; układ znajduje

się albo w stanie 0 albo w stanie 1.

Kubit (qubit)

to dowolny stan kwantowy układu dwupoziomowego o stanach

własnych

|0i

i

|1i

, który może być superpozycją stanów własnych

|Ψi

=

a|0i + b|1i

|a|

2

+

|b|

2

= 1

background image

10/35

Kubit (spin) na sferze Blocha

background image

11/35

x

y

z

|0i

background image

12/35

x

y

z

|1i

background image

13/35

x

y

z

1

2

(

|0i + |1i)

background image

14/35

x

y

z

1

2

(

|0i + i|1i)

background image

15/35

x

y

z

|Ψi = cos

θ
2

|0i + e

sin

θ
2

|1i

background image

16/35

Bramki kwantowe

Klasyczne bramki logiczne

jednobitowe

0

N OT

1

background image

16/35

Bramki kwantowe

Klasyczne bramki logiczne

jednobitowe

0

N OT

1

1

N OT

0

Bramki jednobitowe są odwracalne

background image

17/35

dwubitowe

x

y

AN D

x

AN D

y

background image

17/35

dwubitowe

x

y

AN D

x

AN D

y

x

y

OR

x

OR

y

background image

17/35

dwubitowe

x

y

AN D

x

AN D

y

x

y

OR

x

OR

y

x

y

XOR

x

XOR

y

Powyższe bramki dwubitowe są nieodwracalne

background image

17/35

dwubitowe

x

y

AN D

x

AN D

y

x

y

OR

x

OR

y

x

y

XOR

x

XOR

y

Powyższe bramki dwubitowe są nieodwracalne

Bramka kontrolowane

N OT

x

y

CN OT

x

x ⊕ y

Ta bramka jest odwracalna!

background image

18/35

Bramki kwantowe

jednobitowe

|0i

N OT

|1i

background image

18/35

Bramki kwantowe

jednobitowe

|0i

N OT

|1i

a|0i + b|1i

N OT

a|1i + b|0i

background image

18/35

Bramki kwantowe

jednobitowe

|0i

N OT

|1i

a|0i + b|1i

N OT

a|1i + b|0i

Zmiana fazy

a|0i + b|1i

S

a|0i − b|1i

background image

18/35

Bramki kwantowe

jednobitowe

|0i

N OT

|1i

a|0i + b|1i

N OT

a|1i + b|0i

Zmiana fazy

a|0i + b|1i

S

a|0i − b|1i

Bramka Hadamarda

|0i

H

1

2

(

|0i + |1i)

background image

18/35

Bramki kwantowe

jednobitowe

|0i

N OT

|1i

a|0i + b|1i

N OT

a|1i + b|0i

Zmiana fazy

a|0i + b|1i

S

a|0i − b|1i

Bramka Hadamarda

|0i

H

1

2

(

|0i + |1i)

|1i

H

1

2

(

|0i − |1i)

background image

19/35

Pierwiastek z

N OT

|0i

N OT

1+i

2

|0i +

1

−i

2

|1i

background image

19/35

Pierwiastek z

N OT

|0i

N OT

1+i

2

|0i +

1

−i

2

|1i

|1i

N OT

1

−i

2

|0i +

1+i

2

|1i

background image

19/35

Pierwiastek z

N OT

|0i

N OT

1+i

2

|0i +

1

−i

2

|1i

|1i

N OT

1

−i

2

|0i +

1+i

2

|1i

(

N OT )

2

= N OT

W informatyce kwantowej liczba nietrywialnych bramek logicznych jest znacz-

nie większa!

background image

19/35

Pierwiastek z

N OT

|0i

N OT

1+i

2

|0i +

1

−i

2

|1i

|1i

N OT

1

−i

2

|0i +

1+i

2

|1i

(

N OT )

2

= N OT

W informatyce kwantowej liczba nietrywialnych bramek logicznych jest znacz-

nie większa!

Interferencja kwantowa pozwala uzyskać operacje logiczne niedostępne w

klasycznej informatyce

background image

20/35

Ewolucja stanów kwantowych (kubitów) opisywana jest

równaniem Schrödingera.

background image

20/35

Ewolucja stanów kwantowych (kubitów) opisywana jest

równaniem Schrödingera.

Bramka kwantowa to operacja przekształcająca stan kwantowy

|Ψi

w nowy

stan

0

i

|Ψi

U

0

i

background image

20/35

Ewolucja stanów kwantowych (kubitów) opisywana jest

równaniem Schrödingera.

Bramka kwantowa to operacja przekształcająca stan kwantowy

|Ψi

w nowy

stan

0

i

|Ψi

U

0

i

W bazie

{|0i, |1i}

, stany bazowe reprezentowane są przez macierze jedno-

kolumnowe (wektory)

|0i

=

1

0

,

|1i =

0

1

background image

20/35

Ewolucja stanów kwantowych (kubitów) opisywana jest

równaniem Schrödingera.

Bramka kwantowa to operacja przekształcająca stan kwantowy

|Ψi

w nowy

stan

0

i

|Ψi

U

0

i

W bazie

{|0i, |1i}

, stany bazowe reprezentowane są przez macierze jedno-

kolumnowe (wektory)

|0i

=

1

0

,

|1i =

0

1

zaś jednokubitowa bramka

U

ma postać macierzy

2

× 2

, np.

N OT

=

0

1

1

0

,

,

background image

20/35

Ewolucja stanów kwantowych (kubitów) opisywana jest

równaniem Schrödingera.

Bramka kwantowa to operacja przekształcająca stan kwantowy

|Ψi

w nowy

stan

0

i

|Ψi

U

0

i

W bazie

{|0i, |1i}

, stany bazowe reprezentowane są przez macierze jedno-

kolumnowe (wektory)

|0i

=

1

0

,

|1i =

0

1

zaś jednokubitowa bramka

U

ma postać macierzy

2

× 2

, np.

N OT

=

0

1

1

0

,

H =

1

2

1

2

1

2

1

2

,

background image

20/35

Ewolucja stanów kwantowych (kubitów) opisywana jest

równaniem Schrödingera.

Bramka kwantowa to operacja przekształcająca stan kwantowy

|Ψi

w nowy

stan

0

i

|Ψi

U

0

i

W bazie

{|0i, |1i}

, stany bazowe reprezentowane są przez macierze jedno-

kolumnowe (wektory)

|0i

=

1

0

,

|1i =

0

1

zaś jednokubitowa bramka

U

ma postać macierzy

2

× 2

, np.

N OT

=

0

1

1

0

,

H =

1

2

1

2

1

2

1

2

,

N OT =

1+i

2

1

−i

2

1

−i

2

1+i

2

background image

21/35

Działanie bramki wygląda tak

N OT |0i

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

=

0

1

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

=

0

1

=

|1i

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

=

0

1

=

|1i

H|0i

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

=

0

1

=

|1i

H|0i

=

1

2

1

2

1

2

1

2

1

0

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

=

0

1

=

|1i

H|0i

=

1

2

1

2

1

2

1

2

1

0

=

1

2

1

2

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

=

0

1

=

|1i

H|0i

=

1

2

1

2

1

2

1

2

1

0

=

1

2

1

2

=

1

2

(

|0i + |1i)

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

=

0

1

=

|1i

H|0i

=

1

2

1

2

1

2

1

2

1

0

=

1

2

1

2

=

1

2

(

|0i + |1i)

N OT |0i

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

=

0

1

=

|1i

H|0i

=

1

2

1

2

1

2

1

2

1

0

=

1

2

1

2

=

1

2

(

|0i + |1i)

N OT |0i

=

1+i

2

1

−i

2

1

−i

2

1+i

2

1

0

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

=

0

1

=

|1i

H|0i

=

1

2

1

2

1

2

1

2

1

0

=

1

2

1

2

=

1

2

(

|0i + |1i)

N OT |0i

=

1+i

2

1

−i

2

1

−i

2

1+i

2

1

0

=

1+i

2

1

−i

2

background image

21/35

Działanie bramki wygląda tak

N OT |0i

=

0

1

1

0

1

0

=

0

1

=

|1i

H|0i

=

1

2

1

2

1

2

1

2

1

0

=

1

2

1

2

=

1

2

(

|0i + |1i)

N OT |0i

=

1+i

2

1

−i

2

1

−i

2

1+i

2

1

0

=

1+i

2

1

−i

2

=

1 + i

2

|0i +

1

− i

2

|1i

background image

22/35

dwubitowe

0

i

1

i

U

|Ψi

background image

22/35

dwubitowe

0

i

1

i

U

|Ψi

Bazę w przestrzeni dwukubitowej tworzą stany

{|00i, |01i, |10i, |11i}

. Dwu-

kubitowa bramka

U

opisywana jest w tej bazie macierzą

4

× 4

, np.

CN OT =








1

0

0

0

0

1

0

0

0

0

0

1

0

0

1

0








background image

23/35

Weźmy

0

i

=

1

2

(

|0i − |1i),

background image

23/35

Weźmy

0

i

=

1

2

(

|0i − |1i),

1

i = |1i

background image

23/35

Weźmy

0

i

=

1

2

(

|0i − |1i),

1

i = |1i

0

i ⊗ |Ψ

1

i

=

0

Ψ

1

i = 0|00i +

1

2

|01i + 0|10i −

1

2

|11i

background image

23/35

Weźmy

0

i

=

1

2

(

|0i − |1i),

1

i = |1i

0

i ⊗ |Ψ

1

i

=

0

Ψ

1

i = 0|00i +

1

2

|01i + 0|10i −

1

2

|11i

CN OT |Ψ

0

i|Ψ

1

i

background image

23/35

Weźmy

0

i

=

1

2

(

|0i − |1i),

1

i = |1i

0

i ⊗ |Ψ

1

i

=

0

Ψ

1

i = 0|00i +

1

2

|01i + 0|10i −

1

2

|11i

CN OT |Ψ

0

i|Ψ

1

i

=








1

0

0

0

0

1

0

0

0

0

0

1

0

0

1

0















0

1

2

0

1

2








=

background image

23/35

Weźmy

0

i

=

1

2

(

|0i − |1i),

1

i = |1i

0

i ⊗ |Ψ

1

i

=

0

Ψ

1

i = 0|00i +

1

2

|01i + 0|10i −

1

2

|11i

CN OT |Ψ

0

i|Ψ

1

i

=








1

0

0

0

0

1

0

0

0

0

0

1

0

0

1

0















0

1

2

0

1

2








=








0

1

2

1

2

0








background image

23/35

Weźmy

0

i

=

1

2

(

|0i − |1i),

1

i = |1i

0

i ⊗ |Ψ

1

i

=

0

Ψ

1

i = 0|00i +

1

2

|01i + 0|10i −

1

2

|11i

CN OT |Ψ

0

i|Ψ

1

i

=








1

0

0

0

0

1

0

0

0

0

0

1

0

0

1

0















0

1

2

0

1

2








=








0

1

2

1

2

0








=

1

2

(

|01i − |10i)

background image

23/35

Weźmy

0

i

=

1

2

(

|0i − |1i),

1

i = |1i

0

i ⊗ |Ψ

1

i

=

0

Ψ

1

i = 0|00i +

1

2

|01i + 0|10i −

1

2

|11i

CN OT |Ψ

0

i|Ψ

1

i

=








1

0

0

0

0

1

0

0

0

0

0

1

0

0

1

0















0

1

2

0

1

2








=








0

1

2

1

2

0








=

1

2

(

|01i − |10i)

Otrzymaliśmy stan, który nie daje się rozseparować na iloczyn dwóch stanów

(kubitów). Taki stan nazywamy

stanem splątanym

.

background image

24/35

Stan

1

2

(

|01i + |10i)

jest znaną

parą EPR

. Pomiar jednego kubitu da

0

lub

1

z prawdopodobieństwem

1
2

. Ale jeśli pomiar pierwszego kubitu dał

0

to

drugiego musi dać

1

, i na odwrót! Niezależnie od tego jak daleko od siebie

oddalone są oba kubity!

background image

24/35

Stan

1

2

(

|01i + |10i)

jest znaną

parą EPR

. Pomiar jednego kubitu da

0

lub

1

z prawdopodobieństwem

1
2

. Ale jeśli pomiar pierwszego kubitu dał

0

to

drugiego musi dać

1

, i na odwrót! Niezależnie od tego jak daleko od siebie

oddalone są oba kubity!

Układy wielokubitowe możemy traktować jako

rejestry kwantowe

, na któ-

rych możemy wykonywać kwantowe operacje logiczne (unitarna ewolucja)

lub pomiary.

background image

24/35

Stan

1

2

(

|01i + |10i)

jest znaną

parą EPR

. Pomiar jednego kubitu da

0

lub

1

z prawdopodobieństwem

1
2

. Ale jeśli pomiar pierwszego kubitu dał

0

to

drugiego musi dać

1

, i na odwrót! Niezależnie od tego jak daleko od siebie

oddalone są oba kubity!

Układy wielokubitowe możemy traktować jako

rejestry kwantowe

, na któ-

rych możemy wykonywać kwantowe operacje logiczne (unitarna ewolucja)

lub pomiary.

Stan

|Ψi

=

1

2

(

|00i + |01i + |10i + |11i)

background image

24/35

Stan

1

2

(

|01i + |10i)

jest znaną

parą EPR

. Pomiar jednego kubitu da

0

lub

1

z prawdopodobieństwem

1
2

. Ale jeśli pomiar pierwszego kubitu dał

0

to

drugiego musi dać

1

, i na odwrót! Niezależnie od tego jak daleko od siebie

oddalone są oba kubity!

Układy wielokubitowe możemy traktować jako

rejestry kwantowe

, na któ-

rych możemy wykonywać kwantowe operacje logiczne (unitarna ewolucja)

lub pomiary.

Stan

|Ψi

=

1

2

(

|00i + |01i + |10i + |11i)

=

1

2

(

|0i + |1i + |2i + |3i)

background image

24/35

Stan

1

2

(

|01i + |10i)

jest znaną

parą EPR

. Pomiar jednego kubitu da

0

lub

1

z prawdopodobieństwem

1
2

. Ale jeśli pomiar pierwszego kubitu dał

0

to

drugiego musi dać

1

, i na odwrót! Niezależnie od tego jak daleko od siebie

oddalone są oba kubity!

Układy wielokubitowe możemy traktować jako

rejestry kwantowe

, na któ-

rych możemy wykonywać kwantowe operacje logiczne (unitarna ewolucja)

lub pomiary.

Stan

|Ψi

=

1

2

(

|00i + |01i + |10i + |11i)

=

1

2

(

|0i + |1i + |2i + |3i)

jest dwukubitowym rejestrem kwantowym w stanie superpozycji z jedna-

kowymi amplitudami,w którym liczby od

0

− 3

reprezentowane są z takim

samym prawdopodobieństwem. Dla reprezentacji większych liczb potrzebu-

jemy rejestrów wielokubitowych.

background image

25/35

Procesor Chuanga to procesor 7 kubitowy.

background image

25/35

Procesor Chuanga to procesor 7 kubitowy.

Bramki wielokubitowe można konstruować z bramek jedno- i dwukubito-

wych.

background image

25/35

Procesor Chuanga to procesor 7 kubitowy.

Bramki wielokubitowe można konstruować z bramek jedno- i dwukubito-

wych.

W ten sposób możemy konstruować

komputer kwantowy

!

background image

25/35

Procesor Chuanga to procesor 7 kubitowy.

Bramki wielokubitowe można konstruować z bramek jedno- i dwukubito-

wych.

W ten sposób możemy konstruować

komputer kwantowy

!

Co taki komputer potrafi?

background image

26/35

Algorytm Shora

Rysunek 3: Peter Shor

background image

27/35

Motywacja

• Systemy kryptograficzne z kluczem publicznym wykorzystują fakt, że

rozkład dużej liczby na czynniki jest trudny (czasochłonny)

background image

27/35

Motywacja

• Systemy kryptograficzne z kluczem publicznym wykorzystują fakt, że

rozkład dużej liczby na czynniki jest trudny (czasochłonny)

• Najszybszy obecnie algorytm wymaga czasu

∼ exp[(

64

9

)

1/3

(ln ln N )

2/3

]

faktoryzacja liczby 400 cyfrowej wymagałaby

10

10

lat

background image

27/35

Motywacja

• Systemy kryptograficzne z kluczem publicznym wykorzystują fakt, że

rozkład dużej liczby na czynniki jest trudny (czasochłonny)

• Najszybszy obecnie algorytm wymaga czasu

∼ exp[(

64

9

)

1/3

(ln ln N )

2/3

]

faktoryzacja liczby 400 cyfrowej wymagałaby

10

10

lat

• W 1994 r. RSA 129 został złamany na 1600 stacjach roboczych w

ciągu 8 miesięcy

background image

27/35

Motywacja

• Systemy kryptograficzne z kluczem publicznym wykorzystują fakt, że

rozkład dużej liczby na czynniki jest trudny (czasochłonny)

• Najszybszy obecnie algorytm wymaga czasu

∼ exp[(

64

9

)

1/3

(ln ln N )

2/3

]

faktoryzacja liczby 400 cyfrowej wymagałaby

10

10

lat

• W 1994 r. RSA 129 został złamany na 1600 stacjach roboczych w

ciągu 8 miesięcy

• Algorytm kwantowy Petera Shora wymaga czasu

∼ (ln N )

2+

komputer kwantowy, który faktoryzowałby liczbę 130 cyfrową w ciągu

miesiąca, sfaktoryzowałby liczbę 400 cyfrową w czasie krótszym niż 3

lata

background image

28/35

Algorytm RSA

(Ron Rivest, Adi Shamir, Len Adleman)

Kryptografia z kluczem publicznym

Klucz publiczny:

{e, N }

Klucz prywatny:

{d, N }

Szyfrowanie:

C = M

e

mod

N

Deszyfrowanie:

M = C

d

mod

N

background image

29/35

Jak to działa?

• Mnożymy dwie duże liczby pierwsze

p

i

q

N = pq

background image

29/35

Jak to działa?

• Mnożymy dwie duże liczby pierwsze

p

i

q

N = pq

• Znajdujemy funkcję Eulera

ϕ(N ) = N − p − q + 1 = (p − 1)(q − 1)

background image

29/35

Jak to działa?

• Mnożymy dwie duże liczby pierwsze

p

i

q

N = pq

• Znajdujemy funkcję Eulera

ϕ(N ) = N − p − q + 1 = (p − 1)(q − 1)

• Wybieramy losowo

e < ϕ(N )

względnie pierwsze z

ϕ(N )

.

background image

29/35

Jak to działa?

• Mnożymy dwie duże liczby pierwsze

p

i

q

N = pq

• Znajdujemy funkcję Eulera

ϕ(N ) = N − p − q + 1 = (p − 1)(q − 1)

• Wybieramy losowo

e < ϕ(N )

względnie pierwsze z

ϕ(N )

.

• Ujawniamy

e

i

N

— to jest nasz

klucz publiczny

.

Teraz każdy może użyć naszego klucza publicznego do zaszyfrowania

informacji przesyłanej do nas.

background image

29/35

Jak to działa?

• Mnożymy dwie duże liczby pierwsze

p

i

q

N = pq

• Znajdujemy funkcję Eulera

ϕ(N ) = N − p − q + 1 = (p − 1)(q − 1)

• Wybieramy losowo

e < ϕ(N )

względnie pierwsze z

ϕ(N )

.

• Ujawniamy

e

i

N

— to jest nasz

klucz publiczny

.

Teraz każdy może użyć naszego klucza publicznego do zaszyfrowania

informacji przesyłanej do nas.

• Wyznaczamy

d < ϕ(N )

takie, że

de = 1

mod

ϕ(N )

.

To jest nasz

klucz prywatny

, którego

pilnie strzeżemy !!!

background image

30/35

Przykład

Weźmy:

p = 11

,

q = 13

;

N = 11 ∗ 13 = 143

;

ϕ(N ) = 10 ∗ 12 = 120

wybieramy:

e = 7

;

(120

− 1)/7 = 17

jest całkowite;

d = 120 − 17 = 103

.

Weźmy:

M = 31

(to jest wiadomość do zaszyfrowania)

Szyfrujemy:

31

7

mod

143 = 125

Rozszyfrowujemy:

125

103

mod

143 = 31

background image

30/35

Przykład

Weźmy:

p = 11

,

q = 13

;

N = 11 ∗ 13 = 143

;

ϕ(N ) = 10 ∗ 12 = 120

wybieramy:

e = 7

;

(120

− 1)/7 = 17

jest całkowite;

d = 120 − 17 = 103

.

Weźmy:

M = 31

(to jest wiadomość do zaszyfrowania)

Szyfrujemy:

31

7

mod

143 = 125

Rozszyfrowujemy:

125

103

mod

143 = 31

Jeśli chcesz się pobawić z większymi liczbami to ściągnij program autorstwa

Michała Tanasia demostrujący działanie algorytmu RSA i łamanie szyfru.

Do skompilowania programu pod Linuksem potrzebne są biblioteki GNU

MP 4.1 oraz QT 3.x dostępne w Internecie. Po skompilowaniu programu

można go uruchomić klikając na

RSA demo

poniżej.

Pamiętaj jednak, że

faktoryzacja jest problemem trudnym obliczeniowo!

RSA demo

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

• Przygotowujemy rejestr kwantowy w stanie superpozycji wszystkich

liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

• Przygotowujemy rejestr kwantowy w stanie superpozycji wszystkich

liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

• Wykonujemy operację

B = X

A

mod

N

, wykorzystując kwantowy

paralelizm i wyniki umieszczamy w rejestrze

B

. Komputer kwantowy

wykonuje taką operację w jednym kroku!

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

• Przygotowujemy rejestr kwantowy w stanie superpozycji wszystkich

liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

• Wykonujemy operację

B = X

A

mod

N

, wykorzystując kwantowy

paralelizm i wyniki umieszczamy w rejestrze

B

. Komputer kwantowy

wykonuje taką operację w jednym kroku!

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

• Przygotowujemy rejestr kwantowy w stanie superpozycji wszystkich

liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

• Wykonujemy operację

B = X

A

mod

N

, wykorzystując kwantowy

paralelizm i wyniki umieszczamy w rejestrze

B

. Komputer kwantowy

wykonuje taką operację w jednym kroku!

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

B

1

2

4

8

1

2

4

8

1

2

4

8

1

2

4

8

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

• Przygotowujemy rejestr kwantowy w stanie superpozycji wszystkich

liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

• Wykonujemy operację

B = X

A

mod

N

, wykorzystując kwantowy

paralelizm i wyniki umieszczamy w rejestrze

B

. Komputer kwantowy

wykonuje taką operację w jednym kroku!

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

B

1

2

4

8

1

2

4

8

1

2

4

8

1

2

4

8

• Zauważamy, że wyniki w rejestrze

B

są okresowe z okresem

r = 4

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

• Przygotowujemy rejestr kwantowy w stanie superpozycji wszystkich

liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

• Wykonujemy operację

B = X

A

mod

N

, wykorzystując kwantowy

paralelizm i wyniki umieszczamy w rejestrze

B

. Komputer kwantowy

wykonuje taką operację w jednym kroku!

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

B

1

2

4

8

1

2

4

8

1

2

4

8

1

2

4

8

• Zauważamy, że wyniki w rejestrze

B

są okresowe z okresem

r = 4

B

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

• Przygotowujemy rejestr kwantowy w stanie superpozycji wszystkich

liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

• Wykonujemy operację

B = X

A

mod

N

, wykorzystując kwantowy

paralelizm i wyniki umieszczamy w rejestrze

B

. Komputer kwantowy

wykonuje taką operację w jednym kroku!

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

B

1

2

4

8

1

2

4

8

1

2

4

8

1

2

4

8

• Zauważamy, że wyniki w rejestrze

B

są okresowe z okresem

r = 4

B

1

2

4

8

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

• Przygotowujemy rejestr kwantowy w stanie superpozycji wszystkich

liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

• Wykonujemy operację

B = X

A

mod

N

, wykorzystując kwantowy

paralelizm i wyniki umieszczamy w rejestrze

B

. Komputer kwantowy

wykonuje taką operację w jednym kroku!

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

B

1

2

4

8

1

2

4

8

1

2

4

8

1

2

4

8

• Zauważamy, że wyniki w rejestrze

B

są okresowe z okresem

r = 4

B

1

2

4

8

1

2

4

8

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

• Przygotowujemy rejestr kwantowy w stanie superpozycji wszystkich

liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

• Wykonujemy operację

B = X

A

mod

N

, wykorzystując kwantowy

paralelizm i wyniki umieszczamy w rejestrze

B

. Komputer kwantowy

wykonuje taką operację w jednym kroku!

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

B

1

2

4

8

1

2

4

8

1

2

4

8

1

2

4

8

• Zauważamy, że wyniki w rejestrze

B

są okresowe z okresem

r = 4

B

1

2

4

8

1

2

4

8

1

2

4

8

background image

31/35

Kwantowa faktoryzacja

Chcemy sfaktoryzować liczbę

N

,

N = 15

. Wybieramy liczbę losową

1 < X <

N − 1

względnie pierwszą z

N

, tzn. taką, że

N W D(N, X) = 1

, powiedzmy

X = 2

.

• Przygotowujemy rejestr kwantowy w stanie superpozycji wszystkich

liczb od 0 do 15

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

• Wykonujemy operację

B = X

A

mod

N

, wykorzystując kwantowy

paralelizm i wyniki umieszczamy w rejestrze

B

. Komputer kwantowy

wykonuje taką operację w jednym kroku!

A

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

B

1

2

4

8

1

2

4

8

1

2

4

8

1

2

4

8

• Zauważamy, że wyniki w rejestrze

B

są okresowe z okresem

r = 4

B

1

2

4

8

1

2

4

8

1

2

4

8

1

2

4

8

Komputer kwantowy potrafi szybko znajdować okres funkcji!

background image

32/35

• Jeśli

r

jest nieparzyste, to wybieramy inne

X

i zaczynamy procedurę od

nowa. Jeśli

r

jest parzyste, obliczamy

P = X

r/2

− 1

lub

P = X

r/2

+ 1

i sprawdzamy czy

P

jest dzielnikiem

N

. W naszym przykładzie

r = 4

i

P = 2

4/2

− 1 = 3

lub

P = 2

4/2

+ 1 = 5

.

background image

32/35

• Jeśli

r

jest nieparzyste, to wybieramy inne

X

i zaczynamy procedurę od

nowa. Jeśli

r

jest parzyste, obliczamy

P = X

r/2

− 1

lub

P = X

r/2

+ 1

i sprawdzamy czy

P

jest dzielnikiem

N

. W naszym przykładzie

r = 4

i

P = 2

4/2

− 1 = 3

lub

P = 2

4/2

+ 1 = 5

.

Hurra !!!

15/3 = 5

15/5 = 3

background image

32/35

• Jeśli

r

jest nieparzyste, to wybieramy inne

X

i zaczynamy procedurę od

nowa. Jeśli

r

jest parzyste, obliczamy

P = X

r/2

− 1

lub

P = X

r/2

+ 1

i sprawdzamy czy

P

jest dzielnikiem

N

. W naszym przykładzie

r = 4

i

P = 2

4/2

− 1 = 3

lub

P = 2

4/2

+ 1 = 5

.

Hurra !!!

15/3 = 5

15/5 = 3

Ten wynik udało się już uzyskać eksperymentalnie!

background image

32/35

• Jeśli

r

jest nieparzyste, to wybieramy inne

X

i zaczynamy procedurę od

nowa. Jeśli

r

jest parzyste, obliczamy

P = X

r/2

− 1

lub

P = X

r/2

+ 1

i sprawdzamy czy

P

jest dzielnikiem

N

. W naszym przykładzie

r = 4

i

P = 2

4/2

− 1 = 3

lub

P = 2

4/2

+ 1 = 5

.

Hurra !!!

15/3 = 5

15/5 = 3

Ten wynik udało się już uzyskać eksperymentalnie!

Komputer kwantowy liczy już do 15!

background image

33/35

Kryptografia kwantowa

Czy zbudowanie komputera kwantowego spowoduje, że bezpieczne przesy-

łanie informacji stanie się niemożliwe?

background image

33/35

Kryptografia kwantowa

Czy zbudowanie komputera kwantowego spowoduje, że bezpieczne przesy-

łanie informacji stanie się niemożliwe?

Nie!

background image

33/35

Kryptografia kwantowa

Czy zbudowanie komputera kwantowego spowoduje, że bezpieczne przesy-

łanie informacji stanie się niemożliwe?

Nie!

Bezpieczne przesyłanie informacji zapewnia

kryptografia kwantowa

.

background image

33/35

Kryptografia kwantowa

Czy zbudowanie komputera kwantowego spowoduje, że bezpieczne przesy-

łanie informacji stanie się niemożliwe?

Nie!

Bezpieczne przesyłanie informacji zapewnia

kryptografia kwantowa

.

Popularny wyklad na temat kryptografii kwantowej można znaleźć na mojej

stronie:

http://zon8.physd.amu.edu.pl/~tanas/

Tam też można znaleźć ten wykład oraz program ilustrujący działanie RSA.

background image

34/35

Zaproszenie do fizyki

Studiujcie fizykę kwantową!

background image

34/35

Zaproszenie do fizyki

Studiujcie fizykę kwantową!

a może

Informatykę kwantową?!

background image

34/35

Zaproszenie do fizyki

Studiujcie fizykę kwantową!

a może

Informatykę kwantową?!

Powodzenia!

background image

35/35

Koniec


Document Outline


Wyszukiwarka

Podobne podstrony:
INFORMATYKA KWANTOWA
Informatyka Kwantowa E Skrypt, L Jacak
Informatyka kwantowa
hossa, kompresja informacji L,Kwantowanie liniowe, kwantowanie dynamiczne i kwantowanie nieliniowe (
kwantowe systemy informatyki
pytania, kwantowa teoria informacji, Głupie pytanie
Zbudowanie komputera kwantowego zrewolucjonizuje współczesną informatykę, Fizyka XX wieku
Brytyjski fizyk uważa, że ludzka dusza jest tylko zbiorem informacji, przechowywanych na poziomie kw
Hławiczka Zachowanie informacji w różnych interpretacjach mechaniki kwantowej
techniki informacyjne
wykład 6 instrukcje i informacje zwrotne
Technologia informacji i komunikacji w nowoczesnej szkole
Państwa Ogólne informacje
Fizyka 0 wyklad organizacyjny Informatyka Wrzesien 30 2012
informacja w pracy biurowej 3

więcej podobnych podstron