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 {|0 , |1 } może się
znajdować w każdym z nich, ale także w stanie będącym
syperpozycją stanów bazowych
|¨ = a|0 + b|1
i taki stan nazywamy kubitem.
" Oznacza to, że z prawdopodobieństwem p0 = |a|2 układ znajduje się
w stanie |0 i z prawdopodobieństwem p1 = |b|2 w stanie |1 ,
oczywiście p0 + p1 = 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 {|0 , |1 } może się
znajdować w każdym z nich, ale także w stanie będącym
syperpozycją stanów bazowych
|¨ = a|0 + b|1
i taki stan nazywamy kubitem.
" Oznacza to, że z prawdopodobieństwem p0 = |a|2 układ znajduje się
w stanie |0 i z prawdopodobieństwem p1 = |b|2 w stanie |1 ,
oczywiście p0 + p1 = 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 {|0 , |1 } może się
znajdować w każdym z nich, ale także w stanie będącym
syperpozycją stanów bazowych
|¨ = a|0 + b|1
i taki stan nazywamy kubitem.
" Oznacza to, że z prawdopodobieństwem p0 = |a|2 układ znajduje się
w stanie |0 i z prawdopodobieństwem p1 = |b|2 w stanie |1 ,
oczywiście p0 + p1 = 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 {|0 , |1 } może się
znajdować w każdym z nich, ale także w stanie będącym
syperpozycją stanów bazowych
|¨ = a|0 + b|1
i taki stan nazywamy kubitem.
" Oznacza to, że z prawdopodobieństwem p0 = |a|2 układ znajduje się
w stanie |0 i z prawdopodobieństwem p1 = |b|2 w stanie |1 ,
oczywiście p0 + p1 = 1. Stan układu kwantowego możemy
przedstawić jako wektor na sferze Blocha
|1
|¨
|0
Kubit na sferze Blocha
19.2 Twierdzenie o nieklonowaniu
" Nie istnieje transformacja unitarna U taka, że
U|¨ |0 = |¨ |¨
dla dowolnego |¨ .
" Dowód:
Przypuśćmy, że istnieje U takie, że
U|¨ |0 = |¨ |¨
U|Åš |0 = |Åš |Åš
dla dowolnych |¨ 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|¨ |0 = |¨ |¨
dla dowolnego |¨ .
" Dowód:
Przypuśćmy, że istnieje U takie, że
U|¨ |0 = |¨ |¨
U|Åš |0 = |Åš |Åš
dla dowolnych |¨ 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|¨ |0 = |¨ |¨
dla dowolnego |¨ .
" Dowód:
Przypuśćmy, że istnieje U takie, że
U|¨ |0 = |¨ |¨
U|Åš |0 = |Åš |Åš
dla dowolnych |¨ 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|¨ |0 = |¨ |¨
dla dowolnego |¨ .
" Dowód:
Przypuśćmy, że istnieje U takie, że
U|¨ |0 = |¨ |¨
U|Åš |0 = |Åš |Åš
dla dowolnych |¨ i |Åš .
" Transformacja U reprezentowała by maszynę klonującą, gdyby taka
istniała.
" Z unitarności U wynika jednak, że
¨| 0|U U|Åš |0 = ¨|Åš ¨|Åš
¨|Åš 0|0 = ¨|Åš ¨|Åš
co nie jest prawdziwe dla dowolnych |¨ i |Åš , natomiast może
zachodzić dla stanów ortogonalnych ¨|Åš = {0, 1}.
" Stany ortogonalne (klasyczne bity) mogą być kopiowane, natomiast
dowolne stany kwantowe nie.
" Z unitarności U wynika jednak, że
¨| 0|U U|Åš |0 = ¨|Åš ¨|Åš
¨|Åš 0|0 = ¨|Åš ¨|Åš
co nie jest prawdziwe dla dowolnych |¨ i |Åš , natomiast może
zachodzić dla stanów ortogonalnych ¨|Åš = {0, 1}.
" Stany ortogonalne (klasyczne bity) mogą być kopiowane, natomiast
dowolne stany kwantowe nie.
19.3 Bramki logiczne
klasyczne
kwantowe
a|1 + b|0
a|0 + b|1
a|0 - b|1
S
x x a|0 + b|1
1
"
R
|1 (|0 + |1 )
2
Jednobitowe bramki logiczne
klasyczne
kwantowe
x
x
x '" y x
y
x •" y
y
x
x •" y
y
CNOT
Dwubitowe bramki logiczne
" W bazie stanów {|0 , |1 }, mamy
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
|0 a" , |1 a"
0 1
" Wtedy operacje na stanach kwantowych majÄ… reprezentacjÄ™
macierzową, i tak na przykład
îÅ‚ Å‚Å‚
0 1
ðÅ‚ ûÅ‚
UNOT =
1 0
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
0 1 1 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
UNOT|0 = = a" |1
1 0 0 1
" W bazie stanów {|0 , |1 }, mamy
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
|0 a" , |1 a"
0 1
" Wtedy operacje na stanach kwantowych majÄ… reprezentacjÄ™
macierzową, i tak na przykład
îÅ‚ Å‚Å‚
0 1
ðÅ‚ ûÅ‚
UNOT =
1 0
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
0 1 1 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
UNOT|0 = = a" |1
1 0 0 1
" Operacja przesunięcia fazy, która nie zmienia stanu |0 zaś
stan |1 zmienia na -|1 , ma postać
îÅ‚ Å‚Å‚
1 0
ðÅ‚ ûÅ‚
US =
0 -1
" Operacja Hadamarda, czasem nazywana pierwiastkiem
"
kwadratowym z NOT ( NOT), ma postać
îÅ‚ Å‚Å‚
1 1
1
ðÅ‚ ûÅ‚
"
H =
2
1 -1
" Operacja przesunięcia fazy, która nie zmienia stanu |0 zaś
stan |1 zmienia na -|1 , ma postać
îÅ‚ Å‚Å‚
1 0
ðÅ‚ ûÅ‚
US =
0 -1
" Operacja Hadamarda, czasem nazywana pierwiastkiem
"
kwadratowym z NOT ( NOT), ma postać
îÅ‚ Å‚Å‚
1 1
1
ðÅ‚ ûÅ‚
"
H =
2
1 -1
" Istnieje nieskończenie wiele bramek kwantowych generowanych
przez rotacje o kÄ…t ¸
îÅ‚ Å‚Å‚
cos ¸ - sin ¸
ðÅ‚ ûÅ‚
UR(¸) =
sin ¸ cos ¸
" oraz przesunięcia faz
îÅ‚ Å‚Å‚
eiÕ1 0
ðÅ‚ ûÅ‚
UP (Õ1, Õ2) =
0 eiÕ2
" Istnieje nieskończenie wiele bramek kwantowych generowanych
przez rotacje o kÄ…t ¸
îÅ‚ Å‚Å‚
cos ¸ - sin ¸
ðÅ‚ ûÅ‚
UR(¸) =
sin ¸ cos ¸
" oraz przesunięcia faz
îÅ‚ Å‚Å‚
eiÕ1 0
ðÅ‚ ûÅ‚
UP (Õ1, Õ2) =
0 eiÕ2
" Operacja CNOT (kontrolowane NOT) na dwóch kubitach ma
postać
îÅ‚ Å‚Å‚
1 0 0 0
ïÅ‚ śł
ïÅ‚ śł
ïÅ‚ śł
0 1 0 0
ïÅ‚ śł
UCN =
ïÅ‚ śł
ïÅ‚ śł
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
|x |f(x)
?
f : {0, 1} {0, 1}
Uf : |x |y |x |y •" f(x)
" 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
|x |f(x)
?
f : {0, 1} {0, 1}
Uf : |x |y |x |y •" f(x)
" 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
|x |f(x)
?
f : {0, 1} {0, 1}
Uf : |x |y |x |y •" f(x)
" 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
|x |f(x)
?
f : {0, 1} {0, 1}
Uf : |x |y |x |y •" f(x)
" Pytanie: Czy po jednym przebiegu kwantowego komputera
możemy stwierdzić, że f(0) = f(1)?
" Wez
my następujący obwód kwantowy
|0 Pomiar
H H
|1 Uf
H
gdzie H jest kwantowÄ… bramkÄ… Hadamarda.
" Wez
my następujący obwód kwantowy
|0 Pomiar
H H
|1 Uf
H
gdzie H jest kwantowÄ… bramkÄ… Hadamarda.
19.4.1 Działanie obwodu
1 1
H : |0 " (|0 + |1 ), |1 " (|0 - |1 )
2 2
19.4.1 Działanie obwodu
1 1
H : |0 " (|0 + |1 ), |1 " (|0 - |1 )
2 2
1
|0 |1 (|0 + |1 )(|0 - |1 )
2
19.4.1 Działanie obwodu
1 1
H : |0 " (|0 + |1 ), |1 " (|0 - |1 )
2 2
1
|0 |1 (|0 + |1 )(|0 - |1 )
2

1
(-1)f(0)|0 + (-1)f(1)|1 (|0 - |1 )
2
19.4.1 Działanie obwodu
1 1
H : |0 " (|0 + |1 ), |1 " (|0 - |1 )
2 2
1
|0 |1 (|0 + |1 )(|0 - |1 )
2

1
(-1)f(0)|0 + (-1)f(1)|1 (|0 - |1 )
2


1
(-1)f(0) + (-1)f(1) |0
2


1
"
+ (-1)f(0) - (-1)f(1) |1 (|0 - |1 )
2
19.4.1 Działanie obwodu
1 1
H : |0 " (|0 + |1 ), |1 " (|0 - |1 )
2 2
1
|0 |1 (|0 + |1 )(|0 - |1 )
2

1
(-1)f(0)|0 + (-1)f(1)|1 (|0 - |1 )
2


1
(-1)f(0) + (-1)f(1) |0
2


1
"
+ (-1)f(0) - (-1)f(1) |1 (|0 - |1 )
2
Å„Å‚
òÅ‚
Ä…|0 dla f(0) = f(1)
|m =
ół
Ä…|1 dla f(0) = f(1)

19.5 Kwantowy paralelizm
" Przypuśćmy, że mamy funkcję działającą na N bitów o 2N
możliwych wartościach. Aby obliczyć tablicę funkcji f(x)
musielibyśmy policzyć wartość funkcji 2N razy (dla N = 100
<" 1030)!
" Na komputerze kwantowym działającym zgodnie z
Uf : |x |0 |x |f(x)
możemy wybrać stan początkowy (kwantowy rejestr) w postaci
N
2N -1

1 1
|È0 = " (|0 + |1 ) = |x
2N/2
2
x=0
19.5 Kwantowy paralelizm
" Przypuśćmy, że mamy funkcję działającą na N bitów o 2N
możliwych wartościach. Aby obliczyć tablicę funkcji f(x)
musielibyśmy policzyć wartość funkcji 2N razy (dla N = 100
<" 1030)!
" Na komputerze kwantowym działającym zgodnie z
Uf : |x |0 |x |f(x)
możemy wybrać stan początkowy (kwantowy rejestr) w postaci
N
2N -1

1 1
|È0 = " (|0 + |1 ) = |x
2N/2
2
x=0
19.5 Kwantowy paralelizm
" Przypuśćmy, że mamy funkcję działającą na N bitów o 2N
możliwych wartościach. Aby obliczyć tablicę funkcji f(x)
musielibyśmy policzyć wartość funkcji 2N razy (dla N = 100
<" 1030)!
" Na komputerze kwantowym działającym zgodnie z
Uf : |x |0 |x |f(x)
możemy wybrać stan początkowy (kwantowy rejestr) w postaci
N
2N -1

1 1
|È0 = " (|0 + |1 ) = |x
2N/2
2
x=0
i obliczajÄ…c f(x) tylko raz otrzymujemy stan
2N -1

1
|È = |x |f(x)
2N/2
x=0
" 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
2N -1

1
|È = |x |f(x)
2N/2
x=0
" 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,
1stan początkowy może mieć postać
|È0 = (|00 + |01 + |10 + |11 )
2
|00 |0
|01 |1
|10 |2
|11 |3
1
|È0 = (|0 + |1 + |2 + |3 )
2
" Otrzymujemy superpozycję czterech liczb, na których komputer
kwantowy wykonuje operacje w jednym kroku!
" Na przykład, dla N = 2,
1stan początkowy może mieć postać
|È0 = (|00 + |01 + |10 + |11 )
2
|00 |0
|01 |1
|10 |2
|11 |3
1
|È0 = (|0 + |1 + |2 + |3 )
2
" Otrzymujemy superpozycję czterech liczb, na których komputer
kwantowy wykonuje operacje w jednym kroku!
19.6 Algorytm Shora
Etap 1. Przygotowujemy rejestr A komputera
Rejestr A Rejestr B
kwantowego w superpozycji wszystkich możliwych
0 0
stanów
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
19.6 Algorytm Shora
Etap 1. Przygotowujemy rejestr A komputera
Rejestr A Rejestr B
kwantowego w superpozycji wszystkich możliwych
0 1
stanów
1 2
2 4
Etap 2. Liczba, którą chcemy sfaktoryzować jest N,
3 8
N = 15. Wybieramy liczbÄ™ losowÄ… X,
1 < X < N - 1, X = 2. Wykonujemy operacjÄ™
4 1
B = XA (mod N)
5 2
np. dla X = 2 mamy wyniki przedstawione w
6 4
tabelce
7 8
8 1
9 2
10 4
11 8
12 1
13 2
14 4
15 8
19.6 Algorytm Shora
Etap 1. Przygotowujemy rejestr A komputera
Rejestr A Rejestr B
kwantowego w superpozycji wszystkich możliwych
0 1
stanów
1 2
2 4
Etap 2. Liczba, którą chcemy sfaktoryzować jest N,
3 8
N = 15. Wybieramy liczbÄ™ losowÄ… X,
1 < X < N - 1, X = 2. Wykonujemy operacjÄ™
4 1
B = XA (mod N)
5 2
np. dla X = 2 mamy wyniki przedstawione w
6 4
tabelce
7 8
8 1
Etap 3. Obliczamy P = Xf/2 - 1; f = 4 i
9 2
sprawdzamy czy P jest dzielnikiem N
10 4 w naszym przypadku
P = 24/2 - 1 = 3,
11 8
P = 24/2 + 1 = 5;
12 1
13 2
14 4
15 8
19.6 Algorytm Shora
Etap 1. Przygotowujemy rejestr A komputera
Rejestr A Rejestr B
kwantowego w superpozycji wszystkich możliwych
0 1
stanów
1 2
2 4
Etap 2. Liczba, którą chcemy sfaktoryzować jest N,
3 8
N = 15. Wybieramy liczbÄ™ losowÄ… X,
1 < X < N - 1, X = 2. Wykonujemy operacjÄ™
4 1
B = XA (mod N)
5 2
np. dla X = 2 mamy wyniki przedstawione w
6 4
tabelce
7 8
8 1
Etap 3. Obliczamy P = Xf/2 - 1; f = 4 i
9 2
sprawdzamy czy P jest dzielnikiem N
10 4 w naszym przypadku
P = 24/2 - 1 = 3,
11 8
P = 24/2 + 1 = 5;
12 1
13 2
Hurra !!!
14 4
15/3 = 5
15 8
15/5 = 3
19.7 Kwantowa transformata Fouriera
q-1

1
QF T : |x e2Ä„ixy/q|y
q
y=0
gdzie q = 2N
19.7 Kwantowa transformata Fouriera
q-1

1
QF T : |x e2Ä„ixy/q|y
q
y=0
gdzie q = 2N
19.7.1 Okres funkcji
" Przygotowujemy stan
q-1

1
|È0 = |x |f(x)
"
q
x=0
" Mierzymy drugi rejestr dostając |f(x0) , co powoduje, że pierwszy
rejestr staje się superpozycją wszystkich stanów, które dają wartość
f(x0)
(funkcja jest okresowa z okresem r)
a-1

1 q
|x0 + jr , a - 1 < < a + 1
"
a r
j=0
19.7.1 Okres funkcji
" Przygotowujemy stan
q-1

1
|È0 = |x |f(x)
"
q
x=0
" Mierzymy drugi rejestr dostając |f(x0) , co powoduje, że pierwszy
rejestr staje się superpozycją wszystkich stanów, które dają wartość
f(x0)
(funkcja jest okresowa z okresem r)
a-1

1 q
|x0 + jr , a - 1 < < a + 1
"
a r
j=0
19.7.1 Okres funkcji
" Przygotowujemy stan
q-1

1
|È0 = |x |f(x)
"
q
x=0
" Mierzymy drugi rejestr dostając |f(x0) , co powoduje, że pierwszy
rejestr staje się superpozycją wszystkich stanów, które dają wartość
f(x0)
(funkcja jest okresowa z okresem r)
a-1

1 q
|x0 + jr , a - 1 < < a + 1
"
a r
j=0
" Stosujemy QT F
q-1
a-1

1
e2Ä„ix0y e2Ä„ijry/q|y
"
qa
y=0 j=0
2

a-1


a 1

Prob(y) = e2Ä„ijry/q
a
q

j=0
" Jeśli q/r jest całkowite (q/r = a), to
2 Å„Å‚

a-1
1
òÅ‚


y = a " integer
1 1
r

Prob(y) = e2Ä„ijy/q =
a
ół
a

0 otherwise
j=0
" Stosujemy QT F
q-1
a-1

1
e2Ä„ix0y e2Ä„ijry/q|y
"
qa
y=0 j=0
2

a-1


a 1

Prob(y) = e2Ä„ijry/q
a
q

j=0
" Jeśli q/r jest całkowite (q/r = a), to
2 Å„Å‚

a-1
1
òÅ‚


y = a " integer
1 1
r

Prob(y) = e2Ä„ijy/q =
a
ół
a

0 otherwise
j=0