Kryptografia

z elementami kryptografii kwantowej

Ryszard Tanaś

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

Wykład 13

Spis treści

19 Algorytmy kwantowe

3

19.1 Bit kwantowy — kubit (

qubit

)

. . . . . . . . . . .

3

19.2 Twierdzenie o nieklonowaniu

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

5

19.3 Bramki logiczne

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

7

19.4 Problem Deutscha

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

13

19.5 Kwantowy paralelizm

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

16

19.6 Algorytm Shora

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

19

19.7 Kwantowa transformata Fouriera

. . . . . . . . . .

23

19 Algorytmy kwantowe

19.1 Bit kwantowy — kubit (

qubit

)

•

Klasyczny bit może przyjmować dwie wartości

{0, 1}

.

•

Układ kwantowy, który ma

dwa

możliwe stany

{|0i, |1i}

może się

znajdować w

każdym

z nich, ale także w stanie będącym

syperpozycją

stanów bazowych

|Ψi = a|0i + b|1i

i taki stan nazywamy

kubitem

.

•

Oznacza to, że z prawdopodobieństwem

p

0

= |a|

2

układ znajduje się

w stanie

|0i

i z prawdopodobieństwem

p

1

= |b|

2

w stanie

|1i

,

oczywiście

p

0

+ p

1

= 1

. Stan układu kwantowego możemy

przedstawić jako wektor na sferze Blocha

19 Algorytmy kwantowe

19.1 Bit kwantowy — kubit (

qubit

)

•

Klasyczny bit może przyjmować dwie wartości

{0, 1}

.

•

Układ kwantowy, który ma

dwa

możliwe stany

{|0i, |1i}

może się

znajdować w

każdym

z nich, ale także w stanie będącym

syperpozycją

stanów bazowych

|Ψi = a|0i + b|1i

i taki stan nazywamy

kubitem

.

•

Oznacza to, że z prawdopodobieństwem

p

0

= |a|

2

układ znajduje się

w stanie

|0i

i z prawdopodobieństwem

p

1

= |b|

2

w stanie

|1i

,

oczywiście

p

0

+ p

1

= 1

. Stan układu kwantowego możemy

przedstawić jako wektor na sferze Blocha

19 Algorytmy kwantowe

19.1 Bit kwantowy — kubit (

qubit

)

•

Klasyczny bit może przyjmować dwie wartości

{0, 1}

.

•

Układ kwantowy, który ma

dwa

możliwe stany

{|0i, |1i}

może się

znajdować w

każdym

z nich, ale także w stanie będącym

syperpozycją

stanów bazowych

|Ψi = a|0i + b|1i

i taki stan nazywamy

kubitem

.

•

Oznacza to, że z prawdopodobieństwem

p

0

= |a|

2

układ znajduje się

w stanie

|0i

i z prawdopodobieństwem

p

1

= |b|

2

w stanie

|1i

,

oczywiście

p

0

+ p

1

= 1

. Stan układu kwantowego możemy

przedstawić jako wektor na sferze Blocha

19 Algorytmy kwantowe

19.1 Bit kwantowy — kubit (

qubit

)

•

Klasyczny bit może przyjmować dwie wartości

{0, 1}

.

•

Układ kwantowy, który ma

dwa

możliwe stany

{|0i, |1i}

może się

znajdować w

każdym

z nich, ale także w stanie będącym

syperpozycją

stanów bazowych

|Ψi = a|0i + b|1i

i taki stan nazywamy

kubitem

.

•

Oznacza to, że z prawdopodobieństwem

p

0

= |a|

2

układ znajduje się

w stanie

|0i

i z prawdopodobieństwem

p

1

= |b|

2

w stanie

|1i

,

oczywiście

p

0

+ p

1

= 1

. Stan układu kwantowego możemy

przedstawić jako wektor na sferze Blocha

|0i

|1i

|Ψi

Kubit na sferze Blocha

19.2 Twierdzenie o nieklonowaniu

•

Nie istnieje

transformacja unitarna

U

taka, że

U |Ψi|0i

=

|Ψi|Ψi

dla dowolnego

|Ψi

.

•

Dowód:

Przypuśćmy, że istnieje

U

takie, że

U |Ψi|0i

=

|Ψi|Ψi

U |Φi|0i

=

|Φi|Φi

dla dowolnych

|Ψi

i

|Φi

.

•

Transformacja

U

reprezentowała by

maszynę klonującą

, gdyby taka

istniała.

19.2 Twierdzenie o nieklonowaniu

•

Nie istnieje

transformacja unitarna

U

taka, że

U |Ψi|0i

=

|Ψi|Ψi

dla dowolnego

|Ψi

.

•

Dowód:

Przypuśćmy, że istnieje

U

takie, że

U |Ψi|0i

=

|Ψi|Ψi

U |Φi|0i

=

|Φi|Φi

dla dowolnych

|Ψi

i

|Φi

.

•

Transformacja

U

reprezentowała by

maszynę klonującą

, gdyby taka

istniała.

19.2 Twierdzenie o nieklonowaniu

•

Nie istnieje

transformacja unitarna

U

taka, że

U |Ψi|0i

=

|Ψi|Ψi

dla dowolnego

|Ψi

.

•

Dowód:

Przypuśćmy, że istnieje

U

takie, że

U |Ψi|0i

=

|Ψi|Ψi

U |Φi|0i

=

|Φi|Φi

dla dowolnych

|Ψi

i

|Φi

.

•

Transformacja

U

reprezentowała by

maszynę klonującą

, gdyby taka

istniała.

19.2 Twierdzenie o nieklonowaniu

•

Nie istnieje

transformacja unitarna

U

taka, że

U |Ψi|0i

=

|Ψi|Ψi

dla dowolnego

|Ψi

.

•

Dowód:

Przypuśćmy, że istnieje

U

takie, że

U |Ψi|0i

=

|Ψi|Ψi

U |Φi|0i

=

|Φi|Φi

dla dowolnych

|Ψi

i

|Φi

.

•

Transformacja

U

reprezentowała by

maszynę klonującą

, gdyby taka

istniała.

•

Z unitarności

U

wynika jednak, że

hΨ|h0|U

†

U |Φi|0i

=

hΨ|ΦihΨ|Φi

hΨ|Φih0|0i

=

hΨ|ΦihΨ|Φi

co nie jest prawdziwe dla dowolnych

|Ψi

i

|Φi

, natomiast może

zachodzić dla stanów ortogonalnych

hΨ|Φi = {0, 1}

.

•

Stany

ortogonalne

(klasyczne bity)

mogą

być kopiowane, natomiast

dowolne stany kwantowe

nie

.

•

Z unitarności

U

wynika jednak, że

hΨ|h0|U

†

U |Φi|0i

=

hΨ|ΦihΨ|Φi

hΨ|Φih0|0i

=

hΨ|ΦihΨ|Φi

co nie jest prawdziwe dla dowolnych

|Ψi

i

|Φi

, natomiast może

zachodzić dla stanów ortogonalnych

hΨ|Φi = {0, 1}

.

•

Stany

ortogonalne

(klasyczne bity)

mogą

być kopiowane, natomiast

dowolne stany kwantowe

nie

.

19.3 Bramki logiczne

klasyczne

kwantowe

x

x

a

|0i + b|1i

a

|0i + b|1i

a

|1i + b|0i

a

|0i − b|1i

|1i

1

√2

(|0i + |1i)

S

R

Jednobitowe bramki logiczne

klasyczne

kwantowe

x

x

x

x

y

y

y

x ∧ y

x ⊕ y

x ⊕ y

CNOT

Dwubitowe bramki logiczne

• W bazie stanów

{|0i, |1i}

, mamy

|0i ≡





1

0





,

|1i ≡





0

1





• Wtedy operacje na stanach kwantowych mają

reprezentację

macierzową

, i tak na przykład

U

NOT

=





0

1

1

0





U

NOT

|0i =





0

1

1

0









1

0





=





0

1





≡ |1i

• W bazie stanów

{|0i, |1i}

, mamy

|0i ≡





1

0





,

|1i ≡





0

1





• Wtedy operacje na stanach kwantowych mają

reprezentację

macierzową

, i tak na przykład

U

NOT

=





0

1

1

0





U

NOT

|0i =





0

1

1

0









1

0





=





0

1





≡ |1i

• Operacja

przesunięcia fazy

, która nie zmienia stanu

|0i

zaś

stan

|1i

zmienia na

−|1i

, ma postać

U

S

=





1

0

0

−1





• Operacja

Hadamarda

, czasem nazywana pierwiastkiem

kwadratowym z NOT (

√

NOT

), ma postać

H

=

1

√

2





1

1

1

−1





• Operacja

przesunięcia fazy

, która nie zmienia stanu

|0i

zaś

stan

|1i

zmienia na

−|1i

, ma postać

U

S

=





1

0

0

−1





• Operacja

Hadamarda

, czasem nazywana pierwiastkiem

kwadratowym z NOT (

√

NOT

), ma postać

H

=

1

√

2





1

1

1

−1





• Istnieje nieskończenie wiele bramek kwantowych generowanych

przez

rotacje

o kąt

θ

U

R

(θ)

=





cos θ

− sin θ

sin θ

cos θ





• oraz

przesunięcia faz

U

P

(ϕ

1

, ϕ

2

)

=





e

iϕ

1

0

0

e

iϕ

2





• Istnieje nieskończenie wiele bramek kwantowych generowanych

przez

rotacje

o kąt

θ

U

R

(θ)

=





cos θ

− sin θ

sin θ

cos θ





• oraz

przesunięcia faz

U

P

(ϕ

1

, ϕ

2

)

=





e

iϕ

1

0

0

e

iϕ

2





• Operacja

CNOT

(kontrolowane NOT) na dwóch kubitach ma

postać

U

CN

=











1

0

0

0

0

1

0

0

0

0

0

1

0

0

1

0











19.4 Problem Deutscha

• Przypuśćmy, że mamy kwantową czarną skrzynkę obliczającą

funkcję

f (x)

, tzn. wykonującą transformację unitarną na

dwóch kubitach przedstawioną poniżej

|xi

?

|f (x)i

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

U

f

: |xi|yi → |xi|y ⊕ f (x)i

• Pytanie: Czy po jednym przebiegu kwantowego komputera

możemy stwierdzić, że

f (0) = f (1)

?

19.4 Problem Deutscha

• Przypuśćmy, że mamy kwantową czarną skrzynkę obliczającą

funkcję

f (x)

, tzn. wykonującą transformację unitarną na

dwóch kubitach przedstawioną poniżej

|xi

?

|f (x)i

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

U

f

: |xi|yi → |xi|y ⊕ f (x)i

• Pytanie: Czy po jednym przebiegu kwantowego komputera

możemy stwierdzić, że

f (0) = f (1)

?

19.4 Problem Deutscha

• Przypuśćmy, że mamy kwantową czarną skrzynkę obliczającą

funkcję

f (x)

, tzn. wykonującą transformację unitarną na

dwóch kubitach przedstawioną poniżej

|xi

?

|f (x)i

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

U

f

: |xi|yi → |xi|y ⊕ f (x)i

• Pytanie: Czy po jednym przebiegu kwantowego komputera

możemy stwierdzić, że

f (0) = f (1)

?

19.4 Problem Deutscha

• Przypuśćmy, że mamy kwantową czarną skrzynkę obliczającą

funkcję

f (x)

, tzn. wykonującą transformację unitarną na

dwóch kubitach przedstawioną poniżej

|xi

?

|f (x)i

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

U

f

: |xi|yi → |xi|y ⊕ f (x)i

• Pytanie: Czy po jednym przebiegu kwantowego komputera

możemy stwierdzić, że

f (0) = f (1)

?

• Weźmy następujący

obwód kwantowy

|0i

H

H

Pomiar

|1i

H

U

f

gdzie

H

jest kwantową bramką Hadamarda.

• Weźmy następujący

obwód kwantowy

|0i

H

H

Pomiar

|1i

H

U

f

gdzie

H

jest kwantową bramką Hadamarda.

19.4.1 Działanie obwodu

H : |0i →

1

√

2

(|0i + |1i),

|1i →

1

√

2

(|0i − |1i)

19.4.1 Działanie obwodu

H : |0i →

1

√

2

(|0i + |1i),

|1i →

1

√

2

(|0i − |1i)

|0i|1i →

1

2

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

19.4.1 Działanie obwodu

H : |0i →

1

√

2

(|0i + |1i),

|1i →

1

√

2

(|0i − |1i)

|0i|1i →

1

2

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

→

1

2



(−1)

f (0)

|0i + (−1)

f (1)

|1i



(|0i − |1i)

19.4.1 Działanie obwodu

H : |0i →

1

√

2

(|0i + |1i),

|1i →

1

√

2

(|0i − |1i)

|0i|1i →

1

2

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

→

1

2



(−1)

f (0)

|0i + (−1)

f (1)

|1i



(|0i − |1i)

→

1

2





(−1)

f (0)

+ (−1)

f (1)



|0i

+



(−1)

f (0)

− (−1)

f (1)



|1i



1

√

2

(|0i − |1i)

19.4.1 Działanie obwodu

H : |0i →

1

√

2

(|0i + |1i),

|1i →

1

√

2

(|0i − |1i)

|0i|1i →

1

2

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

→

1

2



(−1)

f (0)

|0i + (−1)

f (1)

|1i



(|0i − |1i)

→

1

2





(−1)

f (0)

+ (−1)

f (1)



|0i

+



(−1)

f (0)

− (−1)

f (1)



|1i



1

√

2

(|0i − |1i)

|mi =







±|0i

dla

f (0) = f (1)

±|1i

dla

f (0) 6= f (1)

19.5 Kwantowy paralelizm

•

Przypuśćmy, że mamy funkcję działającą na

N

bitów o

2

N

możliwych wartościach. Aby obliczyć tablicę funkcji

f (x)

musielibyśmy policzyć wartość funkcji

2

N

razy (dla

N = 100

∼ 10

30

)!

•

Na komputerze kwantowym działającym zgodnie z

U

f

: |xi|0i

→

|xi|f (x)i

możemy wybrać stan początkowy (kwantowy rejestr) w postaci

|ψ

0

i

=



1

√

2

(|0i + |1i)



N

=

1

2

N/2

2

N

−1

X

x=0

|xi

19.5 Kwantowy paralelizm

•

Przypuśćmy, że mamy funkcję działającą na

N

bitów o

2

N

możliwych wartościach. Aby obliczyć tablicę funkcji

f (x)

musielibyśmy policzyć wartość funkcji

2

N

razy (dla

N = 100

∼ 10

30

)!

•

Na komputerze kwantowym działającym zgodnie z

U

f

: |xi|0i

→

|xi|f (x)i

możemy wybrać stan początkowy (kwantowy rejestr) w postaci

|ψ

0

i

=



1

√

2

(|0i + |1i)



N

=

1

2

N/2

2

N

−1

X

x=0

|xi

19.5 Kwantowy paralelizm

•

Przypuśćmy, że mamy funkcję działającą na

N

bitów o

2

N

możliwych wartościach. Aby obliczyć tablicę funkcji

f (x)

musielibyśmy policzyć wartość funkcji

2

N

razy (dla

N = 100

∼ 10

30

)!

•

Na komputerze kwantowym działającym zgodnie z

U

f

: |xi|0i

→

|xi|f (x)i

możemy wybrać stan początkowy (kwantowy rejestr) w postaci

|ψ

0

i

=



1

√

2

(|0i + |1i)



N

=

1

2

N/2

2

N

−1

X

x=0

|xi

i obliczając

f (x)

tylko raz

otrzymujemy stan

|ψi =

1

2

N/2

2

N

−1

X

x=0

|xi|f (x)i

•

Stan ten jest superpozycją wartości funkcji dla wszystkich wartości

jej argumentów. Mamy tu do czynienia z

kwantowym paralelizmem.

i obliczając

f (x)

tylko raz

otrzymujemy stan

|ψi =

1

2

N/2

2

N

−1

X

x=0

|xi|f (x)i

•

Stan ten jest superpozycją wartości funkcji dla wszystkich wartości

jej argumentów. Mamy tu do czynienia z

kwantowym paralelizmem.

•

Na przykład, dla

N = 2

, stan początkowy może mieć postać

|ψ

0

i =

1

2

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

|00i → |0i

|01i → |1i

|10i → |2i

|11i → |3i

|ψ

0

i =

1

2

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

•

Otrzymujemy

superpozycję czterech liczb

, na których komputer

kwantowy wykonuje operacje w jednym kroku!

•

Na przykład, dla

N = 2

, stan początkowy może mieć postać

|ψ

0

i =

1

2

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

|00i → |0i

|01i → |1i

|10i → |2i

|11i → |3i

|ψ

0

i =

1

2

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

•

Otrzymujemy

superpozycję czterech liczb

, na których komputer

kwantowy wykonuje operacje w jednym kroku!

19.6 Algorytm Shora

Rejestr

A

Rejestr

B

0

0

1

0

2

0

3

0

4

0

5

0

6

0

7

0

8

0

9

0

10

0

11

0

12

0

13

0

14

0

15

0

Etap 1. Przygotowujemy rejestr

A

komputera

kwantowego w superpozycji wszystkich możliwych

stanów

19.6 Algorytm Shora

Rejestr

A

Rejestr

B

0

1

1

2

2

4

3

8

4

1

5

2

6

4

7

8

8

1

9

2

10

4

11

8

12

1

13

2

14

4

15

8

Etap 1. Przygotowujemy rejestr

A

komputera

kwantowego w superpozycji wszystkich możliwych

stanów

Etap 2. Liczba, którą chcemy sfaktoryzować jest

N

,

N = 15

. Wybieramy liczbę losową

X

,

1 < X < N − 1

,

X = 2

. Wykonujemy operację

B = X

A

(mod N )

np. dla

X = 2

mamy wyniki przedstawione w

tabelce

19.6 Algorytm Shora

Rejestr

A

Rejestr

B

0

1

1

2

2

4

3

8

4

1

5

2

6

4

7

8

8

1

9

2

10

4

11

8

12

1

13

2

14

4

15

8

Etap 1. Przygotowujemy rejestr

A

komputera

kwantowego w superpozycji wszystkich możliwych

stanów

Etap 2. Liczba, którą chcemy sfaktoryzować jest

N

,

N = 15

. Wybieramy liczbę losową

X

,

1 < X < N − 1

,

X = 2

. Wykonujemy operację

B = X

A

(mod N )

np. dla

X = 2

mamy wyniki przedstawione w

tabelce

Etap 3. Obliczamy

P = X

f /2

− 1

;

f = 4

i

sprawdzamy czy

P

jest dzielnikiem

N

w naszym przypadku

P = 2

4/2

− 1 = 3

,

P = 2

4/2

+ 1 = 5

;

19.6 Algorytm Shora

Rejestr

A

Rejestr

B

0

1

1

2

2

4

3

8

4

1

5

2

6

4

7

8

8

1

9

2

10

4

11

8

12

1

13

2

14

4

15

8

Etap 1. Przygotowujemy rejestr

A

komputera

kwantowego w superpozycji wszystkich możliwych

stanów

Etap 2. Liczba, którą chcemy sfaktoryzować jest

N

,

N = 15

. Wybieramy liczbę losową

X

,

1 < X < N − 1

,

X = 2

. Wykonujemy operację

B = X

A

(mod N )

np. dla

X = 2

mamy wyniki przedstawione w

tabelce

Etap 3. Obliczamy

P = X

f /2

− 1

;

f = 4

i

sprawdzamy czy

P

jest dzielnikiem

N

w naszym przypadku

P = 2

4/2

− 1 = 3

,

P = 2

4/2

+ 1 = 5

;

Hurra !!!

15/3 = 5

15/5 = 3

19.7 Kwantowa transformata Fouriera

QF T : |xi

→

1

q

q−1

X

y=0

e

2πixy/q

|yi

gdzie

q = 2

N

19.7 Kwantowa transformata Fouriera

QF T : |xi

→

1

q

q−1

X

y=0

e

2πixy/q

|yi

gdzie

q = 2

N

19.7.1 Okres funkcji

•

Przygotowujemy stan

|ψ

0

i =

1

√

q

q−1

X

x=0

|xi|f (x)i

•

Mierzymy drugi rejestr dostając

|f (x

0

)i

, co powoduje, że pierwszy

rejestr staje się superpozycją wszystkich stanów, które dają wartość

f (x

0

)

(funkcja jest

okresowa

z okresem

r

)

1

√

a

a−1

X

j=0

|x

0

+ jri ,

a − 1 <

q

r

< a + 1

19.7.1 Okres funkcji

•

Przygotowujemy stan

|ψ

0

i =

1

√

q

q−1

X

x=0

|xi|f (x)i

•

Mierzymy drugi rejestr dostając

|f (x

0

)i

, co powoduje, że pierwszy

rejestr staje się superpozycją wszystkich stanów, które dają wartość

f (x

0

)

(funkcja jest

okresowa

z okresem

r

)

1

√

a

a−1

X

j=0

|x

0

+ jri ,

a − 1 <

q

r

< a + 1

19.7.1 Okres funkcji

•

Przygotowujemy stan

|ψ

0

i =

1

√

q

q−1

X

x=0

|xi|f (x)i

•

Mierzymy drugi rejestr dostając

|f (x

0

)i

, co powoduje, że pierwszy

rejestr staje się superpozycją wszystkich stanów, które dają wartość

f (x

0

)

(funkcja jest

okresowa

z okresem

r

)

1

√

a

a−1

X

j=0

|x

0

+ jri ,

a − 1 <

q

r

< a + 1

•

Stosujemy

QT F

1

√

qa

q−1

X

y=0

e

2πix

0

y

a−1

X

j=0

e

2πijry/q

|yi

Prob(y) =

a

q








1

a

a−1

X

j=0

e

2πijry/q








2

•

Jeśli

q/r

jest całkowite (

q/r = a

), to

Prob

(y) =

1

a








1

a

a−1

X

j=0

e

2πijy/q








2

=







1
r

y = a ∗

integer

0

otherwise

•

Stosujemy

QT F

1

√

qa

q−1

X

y=0

e

2πix

0

y

a−1

X

j=0

e

2πijry/q

|yi

Prob(y) =

a

q








1

a

a−1

X

j=0

e

2πijry/q








2

•

Jeśli

q/r

jest całkowite (

q/r = a

), to

Prob

(y) =

1

a








1

a

a−1

X

j=0

e

2πijy/q








2

=







1
r

y = a ∗

integer

0

otherwise