Wstęp do informatyki i kryptografii kwantowej.pdf

(1173 KB) Pobierz
Wstęp do informatyki i kryptografii kwantowej
dr inŜ. Witold Jacak
mgr inŜ. Wojciech Donderowicz
mgr inŜ. Janusz Jacak
pod redakcją
prof. dra hab. inŜ. Lucjana Jacaka
E-skrypt opracowany w ramach projektu pt. „Wzrost liczby absolwentów w
Politechnice Wrocławskiej na kierunkach o kluczowym znaczeniu dla gospodarki
opartej na wiedzy” nr UDA-POKL.04.01.02-00-065/09-01
Projekt współfinansowany ze
środków
Unii Europejskiej
w ramach Europejskiego Funduszu Społecznego
Strona 1 z 124
Recenzent: dr hab. inŜ. Andrzej Radosz, prof. PWr
Redaktor serii: dr hab. inŜ. Włodzimierz Salejda, prof. PWr
© Copyright by Politechnika Wrocławska
OFICYNA WYDAWNICZA POLITECHNIKI WROCŁAWSKIEJ
WybrzeŜe Wyspiańskiego 27, 50-370 Wrocław
ISBN 978-83-7493-604-0
Projekt współfinansowany ze
środków
Unii Europejskiej
w ramach Europejskiego Funduszu Społecznego
Strona 2 z 124
Spis treści
Wprowadzenie ............................................................................................................................................... 4
1.1.
Informacja klasyczna ............................................................................................................................. 4
1.2.
Informacja kwantowa ............................................................................................................................ 5
1.3.
Pomiar i dekoherencja ........................................................................................................................... 6
1.4.
Komputer kwantowy – perspektywy i ograniczenia ............................................................................ 11
2.
Zasady kwantowego opisu........................................................................................................................... 16
3.
Pomiar w mechanice kwantowej ................................................................................................................. 18
3.1.
Pomiar w sensie von Neumanna – superwybór
śurka
......................................................................... 20
4.
Macierz gęstości .......................................................................................................................................... 23
5.
Reprezentacja Schmidta i liczba Schmidta, stany splątane ......................................................................... 27
6.
Geometryczne własności macierzy gęstości ................................................................................................ 29
7.
Zbiór wypukły macierzy gęstości qubitu (sfera Blocha) ............................................................................ 31
8.
Protokoły kwantowe .................................................................................................................................... 35
8.1.
Super gęste kodowanie ........................................................................................................................ 35
8.2.
Teleportacja kwantowa ........................................................................................................................ 36
9.
Ewolucja w czasie macierzy gęstości .......................................................................................................... 39
10.
Sterowanie qubitem – oscylacje Rabiego ................................................................................................ 42
11.
Twierdzenia No-cloning, No-broadcasting oraz No-deleting .................................................................. 46
11.1.
Twierdzenie No-cloning .................................................................................................................. 46
11.2.
Twierdzenie No-broadcasting – konsekwencje ............................................................................... 49
11.3.
Twierdzenie No-deleting – konsekwencje ...................................................................................... 49
12.
Bramki jedno-qubitowe ........................................................................................................................... 54
12.1.
Macierze Pauliego ........................................................................................................................... 54
12.2.
Bramka Pauliego
X
...................................................................................................................... 55
12.3.
Bramka Pauliego
Y
........................................................................................................................ 56
12.4.
Bramka Pauliego
Z
....................................................................................................................... 56
12.5.
Bramka Hadamarda ......................................................................................................................... 57
12.6.
Bramka fazy .................................................................................................................................... 58
12.7.
1.
12.8.
12.9.
Rotacje na sferze Blocha ................................................................................................................. 61
12.10.
Twierdzenie o przedstawieniu dowolnej operacji jedno-qubitowej za pomocą operatorów obrotu 67
13.
Bramki wielo-qubitowe ........................................................................................................................... 71
13.1.
Bramka kontrolowanej negacji (CNOT) ......................................................................................... 71
13.2.
Układ kopiujący .............................................................................................................................. 75
13.3.
Bramka kontrolowanej operacji
U
................................................................................................ 76
13.4.
Działanie bramki
CNOT
na macierz gęstości układu dwóch qubitów ........................................ 79
13.5.
Bramka
SWAP
............................................................................................................................. 85
13.6.
Bramka
CNOT
w reprezentacji dowolnej kontrolowanej bramki
U
......................................... 86
13.7.
Bramka Toffoli ................................................................................................................................ 88
13.8.
Bramka Fredkina ............................................................................................................................. 90
13.9.
Dowolna kontrolowana operacja
U
............................................................................................... 91
13.10.
Operacje wielo-qubitowe – bramki uniwersalne ............................................................................. 94
14.
Układ bramek kwantowych realizujący splątane stany (stany Bella) .................................................... 100
15.
Układ bramek kwantowych realizujący teleportację kwantowych stanów ............................................ 101
16.
Równoległość kwantowa ....................................................................................................................... 102
17.
Kwantowa transformata Fouriera........................................................................................................... 105
18.
Algorytm Grovera – poszukiwanie igły w stogu siana (finding
needle in a haystack)
.......................... 113
19.
Algorytm Shora – łamanie szyfru RSA ................................................................................................. 117
20.
Literatura ................................................................................................................................................ 124
8
Bramka
e
i
φ
(przesunięcie fazy o
φ
) ............................................................................................. 60
Bramka
π
...................................................................................................................................... 59
Projekt współfinansowany ze
środków
Unii Europejskiej
w ramach Europejskiego Funduszu Społecznego
Strona 3 z 124
1. Wprowadzenie
1.1.
Informacja klasyczna
Informacja klasyczna wyraŜająca się poprzez makroskopowe wyniki konkretnych fizykalnych
pomiarów, zrozumiała jest dla
świadomości
człowieka (wyraŜa się poprzez liczby
rzeczywiste). Pomiary te są
ściśle
klasyczne, tzn. realizowane przez przyrządy makroskopowe
dobrze opisywane przez klasyczną mechanikę, czy elektrodynamikę. Przetwarzanie kaŜdej
informacji, w tym informacji klasycznej, ma fizyczny charakter, gdyŜ potrzebne są tu
fizyczne nośniki informacji i dla informatyki klasycznej wybiera się takie nośniki, które w
najlepszy moŜliwy sposób imitują klasyczne zachowanie materii (mimo
Ŝe
w istocie cała
materia jest kwantowa). Z dobrym przybliŜeniem, pozwalającym na ewentualną korektę
błędów w sensie klasycznym
1
, wiele układów elektrycznych, czy mechanicznych jest zatem
uŜytecznych i uŜywanych w klasycznej informatyce jako nośniki informacji (łącznie ze
współczesnymi komputerami). Im większa jest jednak skala miniaturyzacji, tym bardziej
klasyczne elementy układów informatycznych zbliŜają się do granicy kwantowej, gdzie
wymykają się klasycznemu opisowi. Dopóki rozmiary elementów (pamięci i procesorów)
pozostają w skali µm (obecne techniki foto-litografii obejmują obszar dolnej granicy
rozdzielczości dla
światła
widzialnego ~0.35 µm, a nawet bliskiego nadfioletu ~0.2 µm), to
opis klasyczny jest zadowalającym przybliŜeniem, jednak juŜ w obszarze nm w strukturach
półprzewodnikowych, kwantowe efekty staja się dominujące (w półprzewodnikach efektywna
masa elektronów moŜe być duŜo mniejsza niŜ swobodnego elektronu i w związku z tym
kwantowe efekty są wyraźniejsze).
Przetwarzanie informacji, nawet klasycznej, pociąga za sobą jednak i głębsze odniesienia
fizykalne. Wymazywanie informacji jest procesem
dyssypatywnym
w sensie fizycznym
2
.
Przeprowadzenie takiej operacji wymaga zmniejszenia objętości fazowej i przez to redukcji
entropii – jest to zatem proces nieodwracalny (i niesamorzutny, konieczne jest wykonanie
pracy, aby taki proces przeprowadzić). Dobrym przykładem jest tu porównanie rejestru bitów
do układu pudełek, w których cząstka (kaŜda w swoim) moŜe zajmować jedną z dwóch
moŜliwych części pudełka.
Resetowanie,
czyli wymazywanie informacji z rejestru, jest
równowaŜne przesunięciu wszystkich cząstek w pudełkach na jedna stronę –
Ŝeby
to wykonać
trzeba przesunąć
ścianki
we wszystkich pudełkach do połowy, a to wymaga pracy przeciw
ciśnieniu znajdującej się tam cząstki (mogła się znajdować w dowolnej części). Ta praca
oznacza napływ energii do układu informatycznego, co odpowiada jego nagrzewaniu się.
Zmiana entropii w przypadku wymazywania pojedynczego bitu wynosi
k
ln 2
(jest to
obniŜenie entropii odpowiadające dwukrotnemu zmniejszeniu objętości fazowej) i przy stałej
temperaturze prowadzi to do
dyssypacji
energii do otoczenia w ilości
kT
ln 2
na bit
(równocześnie równej pracy wykonanej przy resetowaniu bitu, by utrzymać tę samą
klasyczna korekta błędów polega na zwielokrotnieniu układu i zapisaniu we wszystkich kopiach tej samej
informacji i częstym weryfikowania (przez porównanie) stanu całego zapisu – błędy pojawiają się
mniejszościowo i w związku z tym mogą być zidentyfikowane i poprawiane za kaŜdą kolejną weryfikacją (przy
dostatecznym stopniu
redundancji,
czyli zwielokrotnienia i krótkim odstępie między weryfikacjami)
2
na taki aspekt informacji zwrócono uwagę dostrzegając informacyjny charakter entropii wprowadzonej przez
drugą zasadę termodynamiki i jej związek z procesami odwracalnymi i nieodwracalnymi
1
Projekt współfinansowany ze
środków
Unii Europejskiej
w ramach Europejskiego Funduszu Społecznego
Strona 4 z 124
temperaturę – zgodnie z pierwsza zasada termodynamiki). Te ograniczenia energetyczne nie
są widoczne jeszcze przy obecnie stosowanych układach, gdyŜ na skutek niedoskonałości i
makroskopowości
dyssypacje
energii przy klasycznych operacjach są zwykle o wiele rzędów
większe, niŜ te związane z samym procesem wymazywania informacji.
By uniknąć jednak strat dyssypacyjnych w sensie redukcji objętości przestrzeni fazowej przy
np. wymazywaniu informacji klasycznej, moŜna by realizować operacje w sposób odwracalny
czyli
niedyssypacyjny.
Przykład: typową operację NAND, która dwa bity (a,b) przerzuca na
jeden
¬
(
a
∧
b
)
(nieodwracalna operacja) moŜna by zastąpić
bramką Toffoli,
czyli odwracalną
wersją NAND: (a,b,c) przerzuca na
(
a
,
b
,
c
⊕
(
a
∧
b
))
(w tym przypadku dla c=1 trzeci bit ma
tę samą wartość logiczną jak w operacji NAND, ale 3 bity przechodzą na 3 bity, co pozwala
na odwracalność).
11
0
111
110
10
1
101
101
¬
(
a
∧
b
)
⇔
  ⇒  
, ale takŜe
(
a
,
b
, (
c
=
1)
⊕
(
a
∧
b
))
⇔
  ⇒  
01
1
011
011
 
 
 
 
00
1
001
001
RównowaŜność logiczna nieodwracalnej bramki NAND i bramki Toffoli
Realizacja odwracalnych operacji klasycznej informatyki prowadzi jednak, jak wida
ć
na
powy
Ŝ
szym przykładzie, do zwielokrotnienia układów i bramek logicznych, które
zawierałyby wci
ąŜ
rosn
ą
c
ą
dodatkow
ą
informacj
ę
. Nie jest jasne, czy realistyczny jest pomysł
Ch. Benneta, by mimo tej zło
Ŝ
ono
ś
ci wykona
ć
procedury do ko
ń
ca, wynik zapisa
ć
i
procedury (odwracalne) odwróci
ć
. Czy b
ę
dzie to w istocie zupełnie nie potrzebuj
ą
cy energii
proces obróbki informacji, czy jednak nie, wobec konieczno
ś
ci dysponowania ogromnymi
nadmiarowymi obszarami informatycznymi. Jest to nie do ko
ń
ca rozpoznany jeszcze
problem/paradoks. Istotn
ą
uwag
ą
mo
Ŝ
e by
ć
tu fakt,
Ŝ
e układy fizyczne s
ą
jednak w swej
mikroskopowej warstwie nieklasyczne, ale kwantowe, i rozdrabnianie i zwielokrotnianie
układów prowadzi w nieunikniony sposób do miniaturyzacji, gdzie z przyczyn podstawowych
nie mo
Ŝ
na dalej stosowa
ć
klasycznych poj
ęć
informatycznych.
1.2.
Informacja kwantowa
Informacja kwantowa to stan obiektu w sensie kwantowym, np. stan cz
ą
stki opisany przez jej
kwantow
ą
funkcj
ę
falow
ą
. Jest ona nieobserwowalna dla klasycznych obiektów (w
szczególno
ś
ci, dla człowieka – obserwatora), chocia
Ŝ
w kwantowy sposób przetwarzana jest i
przekazywana pomi
ę
dzy innymi układami kwantowymi. W ten sposób informacja kwantowa
jest przez sam
ą
przyrod
ę
przetwarzana, ale w sposób nieczytelny dla deterministycznego,
klasycznego obserwatora. Mo
Ŝ
na dokonywa
ć
pomiarów nad układem kwantowym i w ten
sposób dowiadywa
ć
si
ę
w klasycznych (makroskopowych) terminach o jej zawarto
ś
ci; jednak
jest to mo
Ŝ
liwe tylko w małym stopniu w stosunku do całej kwantowej informatycznej
zawarto
ś
ci funkcji falowej. Na przeszkodzie stoj
ą
tu bowiem stoj
ą
zasady nieoznaczono
ś
ci –
pomiary jednej wielko
ś
ci zwykle tak zaburzaj
ą
stan kwantowy,
Ŝ
e pomiary innej wielko
ś
ci s
ą
ju
Ŝ
niemo
Ŝ
liwe (i to nie z przyczyn zwi
ą
zanych z precyzj
ą
przyrz
ą
du pomiarowego, ale
Projekt współfinansowany ze
środków
Unii Europejskiej
w ramach Europejskiego Funduszu Społecznego
Strona 5 z 124

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin