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