kwantowe systemy informatyki

Kwantowe systemy informatyki

Stefan Węgrzyn, Jerzy Klamka, Jarosław A. Miszczak

25 czerwca 2003

Spis treści

1 Wprowadzenie

2 Podstawy matematyczne

2.1 Qubity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2.2 Układy złożone . . . . . . . . . . . . . . . . . . . . . . . . . .

2.3 Barmki kwantowe . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3.1

Bramki 1-qubitowe . . . . . . . . . . . . . . . . . . . . 11

2.3.2

Bramki 2-qubitowe . . . . . . . . . . . . . . . . . . . . 13

2.4 Bramki wieloqubitowe . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Splątanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6 Układy bramek kwantowych . . . . . . . . . . . . . . . . . . . 20

3 Algorytmy kwantowe

3.1 Algorytm Grovera . . . . . . . . . . . . . . . . . . . . . . . . . 22

3.1.1

Operator Grovera . . . . . . . . . . . . . . . . . . . . . 23

3.2 Algorytmy Shora . . . . . . . . . . . . . . . . . . . . . . . . . 26

3.2.1

Znajdowanie rzędu w grupie . . . . . . . . . . . . . . . 26

3.2.2

Szybka faktoryzacja . . . . . . . . . . . . . . . . . . . . 29

3.3 Kwantowa transformata Fouriera . . . . . . . . . . . . . . . . 30

3.3.1

Złożoność obliczeniowa . . . . . . . . . . . . . . . . . . 32

3.4 Inne algorytmy kwantowe . . . . . . . . . . . . . . . . . . . . 35

4 Kwantowa teoria informacji

4.1 Gęste kodowanie . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Teleportacja kwantowa . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Kwantowa dystrybucja klucza . . . . . . . . . . . . . . . . . . 39

5 Implementacje obliczeń kwantowych

5.1 Jakie warunki musi spełniać komputer kwantowy? . . . . . . . 43
5.2 Magnetyczny rezonans jądrowy . . . . . . . . . . . . . . . . . 44
5.3 Pułapkowanie jonów . . . . . . . . . . . . . . . . . . . . . . . 46

SPIS TREŚCI

5.3.1

Budowa pułapki jonowej . . . . . . . . . . . . . . . . . 47

5.3.2

Model pułapki jonowej . . . . . . . . . . . . . . . . . . 47

5.4 Kropki kwantowe . . . . . . . . . . . . . . . . . . . . . . . . . 48

5.4.1

Działania na kropkach kwantowych . . . . . . . . . . . 48

5.5 Realizacje doświadczalne . . . . . . . . . . . . . . . . . . . . . 48
5.6 Podsumowanie . . . . . . . . . . . . . . . . . . . . . . . . . . 49

Rozdział 1

Wprowadzenie

Informatyka jest dyscypliną naukową o własnych pojęciach podstawowych,
badająca prawa rządzące procesami zapisywania, przechowywania i rozpro-
wadzania danych.

Badania te prowadzone są zarówno dla wewnętrznych potrzeb całej nauki,

dla naszych potrzeb cywilizacyjnych, jak i dla stworzenia i rozwoju podstaw
naukowych projektowania i budowy potrzebnych ludziom w tej dziedzinie
urządzeń i systemów.

Z tego zakresu zwracają obecnie uwagę liczne prace badawcze nad możli-

wościami realizacji procesów informatycznych w oparciu o zjawiska mechaniki
kwantowej.

Niniejsze opracowanie ma na celu omówienie tego zagadnienia.
W okresie ostatnich kilku lat nastąpił bardzo szybki rozwój prac badaw-

czych dotyczących szeroko rozumianej informatyki kwantowej, a w szcze-
gólności możliwości konstruowania komputerów kwantowych. Informatyka
kwantowa jest dyscypliną naukową o bardzo silnych związkach zarówno z kla-
syczną informatyką, jak i z fizyką kwantową. Badania eksperymentalne nad
realizacją komputera kwantowego wymagają stosowania technik badawczych
zaczerpniętych bezpośrednio z technologii kwantowych. Obecnie, najpopu-
larniejszymi technologiami kwantowymi są: magnetyczny rezonans jądrowy,
jony w pułapkach optycznych, półprzewodnikowe kropki kwantowe oraz na-
nozłącza Josephsona.

Układ kwantowy złożony z n qubitów może występować w 2

różnych sta-

nach kwantowych reprezentowanych przez n-elementowe ciągi binarne (zero-
jedynkowe). Zatem do opisu układu kwantowego złożonego z n qubitów po-
trzeba 2

liczb. Istotną cechą n-qubitowego komputera kwantowego jest zja-

wisko zwane superpozycją stanów kwantowych poszczególnych qubitów. Su-
perpozycja stanów kwantowych poszczególnych qubitów oznacza, że układ n
qubitów może istnieć w wielu stanach kwantowych jednocześnie i w tym sa-

mym czasie można równolegle dokonywać operacji kwantowych na każdym ze
stanów. Zatem komputer kwantowy może wykonywać olbrzymią liczbę ope-
racji matematycznych równolegle wykorzystując do tego celu jeden procesor
kwantowy.

Wykonywanie obliczeń na komputerze kwantowym wymaga stosowania

odpowiednich algorytmów obliczeniowych, dostosowanych do specyfiki dzia-
łania komputera kwantowego. Algorytmy te umożliwiają wielokrotne przy-
spieszenie obliczeń w stosunku do rezultatów osiąganych za pomocą algoryt-
mów stosowanych do tej pory w klasycznych komputerach. Najlepszym tego
przykładem jest algorytm rozkładu liczby naturalnej na czynniki pierwsze
zaproponowany po raz pierwszy w 1994 roku przez Petera W. Shora. Innym
przykładem może był algorytm kwantowego przeszukiwania zaproponowany
przez L. K. Grovera. Algorytm ten umożliwia szybkie wyszukiwanie określo-
nej informacji w dużych zbiorach informacji.

Wykonywanie obliczeń na komputerze kwantowym wymaga stosowania

odpowiednich algorytmów obliczeniowych, dostosowanych do specyfiki dzia-
łania komputera kwantowego. Algorytmy te umożliwiają wielokrotne przy-
spieszenie obliczeń w stosunku do rezultatów osiąganych za pomocą algo-
rytmów stosowanych do tej pory w klasycznych komputerach. Najlepszym
tego przykładem jest algorytm rozkładu danej liczby naturalnej na czynniki
pierwsze zaproponowany po raz pierwszy w 1994 roku przez Petera W. Sho-
ra. Innym przykładem może być algorytm kwantowego przeszukiwania za-
proponowany przez L. K. Grovera. Algorytm ten umożliwia bardzo szybkie
wyszukiwanie określonej informacji w dużych nieuporządkowanych zbiorach
informacji.

Następną interesującą cechą odróżniającą układy kwantowe od układów

klasycznych jest tak zwane splątanie (zawikłanie). Zjawisko splątania jest
znane w fizyce od lat 30 XX wieku i najczęściej jest ono wiązane z zapro-
ponowanym przez Einsteina, Podolskiego oraz Rosena eksperymentem my-
ślowym który jakoby miał podważać kopmletność opisu rzeczywistości przez
mechanikę kwantową. W kwantowej teorii informacji splątanie jest wiąza-
ne z proponowanymi protokołami przesyłania informacji oraz z wydajnością
osiągana przez algorytmy kwantowe. Oprócz tego badani teoretyczne dotczą-
ce splątania stanowią dynamicznie rozwijający się obszar fizyki.

Rozdział 2

Podstawy matematyczne

2.1

Qubity

Podstawy teoretyczne informatyki kwantowej wynikają bezpośrednio z pod-
stawowych zasad nierelatywistycznej mechaniki kwantowej. W klasycznej in-
formatyce opartej na algebrze Boole’a pojedynczy bit może przyjmować tyl-
ko dwie ustalone wartości logiczne to znaczy 0 lub 1. Natomiast elementarną
jednostką obliczeniową w informatyce kwantowej jest kwantowy bit w skró-
cie zwany qubitem, będący elementem zespolonej przestrzeni Hilberta C

Precyzyjniej wyraża to poniższa definicja:

Definicja 1 Qubitem nazywamy układ kwantowy opisywany dwuwymiarową
przestrzenią Hilberta.

Tutaj i w całym opracowaniu rozważane będą jedynie przestrzenie Hil-

berta nad ciałem liczb zespolonych C.

Dwa ortogonalne stany pojedynczego qubitu są oznaczane przez |0i oraz

|1i. Jeżeli utożsamimy jest z wektorami

|0i =

0
1

, |1i =

1
0

¸¾

(2.1)

to widać, iż tworzą one bazę ortonormalną przestrzeni C

. Tak więc dowolny

stan qubitu |ψi ∈ C

może być przedstawiony w postaci liniowej kombinacji

wektorów bazowych

|ψi = α|0i + β|1i,

(2.2)

gdzie liczby zespolone α oraz β nazywane są amplitudami stanu, a wektor
|ψi jest znormalizowany to znaczy

|α|

+ |β|

= 1.

2.1. QUBITY

Oznacza to, że qubit |ψi przyjmuje wartość logiczną 0 z prawdopodobień-

stwem |α|

oraz wartość logiczną 1 z prawdopodobienstwem |β|

. Stosowane

Rysunek 2.1: Sfera Blocha jest geomtryczną ilustracją qubitu.

tutaj oznaczenia są zaczerpnięte bezpośrednio z terminologii stosowanej w me-
chanice kwantowej. Wektory bazowe |0i oraz |1i reprezentują odpowiednio
wartości logiczne 0 oraz 1 klasycznego bitu algebry Boole’a. Zatem w przy-
padku ogólnym stan qubitu jest superpozycją tych dwóch wartości.

Ponadto stosuje się również następujący zapis dotyczący wektorów trans-

ponowanych (wektorów bra)

h0| =

1 0

1
0

(2.3)

h1| =

0 1

0
1

(2.4)

W przypadku klasycznego bitu pomiar jego aktualnej wartości logicznej,

któr1 może być tylko 0 lub 1 nie nastręcza żadnych trudności. Natomiast ina-
czej jest w przypadku kwantowego qubitu. Pomiar jego aktualnej wartości
może zniszczyć fizyczną strukturę qubitu – pomiar jest operacją nieodwra-
calną. Podczas pomiaru wartości qubitu dokonuje się ortogonalnej projekcji
wektora |ψi ∈ C

na wektory bazowe |0i oraz |1i.

ROZDZIAŁ 2. PODSTAWY MATEMATYCZNE

2.2

Układy złożone

Fundamentalną zasadą mechaniki kwantowej jest to, że przestrzenią stanów
dla 2 qubitów jest iloczynem tensorowym przestrzeni stanów kwantowych dla
pojedynczych qubitów.

Dla dwóch wektorów

|ai =

, |bi =

ich iloczyn tensorowy |ai ⊗ |bi zdefiniowany jest jako

|ai ⊗ |bi = |ai =











 .

Przestrzeń wektorowa będą iloczynem tensorowym dwóch przestrzeni ma

wymiar będący iloczynem wymiarów tych przestrzeni, a bazą tej przestrzeni
jest zbiór wektorów będących iloczynami wektorowymi wektorów baz tych
przestrzeni.

Zatem w przypadku 2 qubitów jest to 4-wymiarowa zespolona przestrzeń

Hilberta C

= C

⊗ C

. Elementami tej przestrzeni są wszystkie możliwe

superpozycje stanów kwantowych reprezentowane iloczynami tensorowymi
wektorów bazowych w C

. Ogólnie, stan układu kwantowego złożonego z n

qubitów można rozpatrywać jako element 2

-wymiarowej zespolonej prze-

strzeni Hilberta C

, będącej iloczynem tensorowym n przestrzeni C

, czyli

= C

⊗ C

⊗ . . . ⊗ C

}

n−razy

W ogólności przestrzeń stanów dla układu n qubitów jest rozpięta przez 2

wzajemnie ortogonalnych stanów bazowych postaci |ii, gdzie i jest n-bitową
liczbą binarną, i ∈ {0, 1, 2, ..., 2

− 1}. Ponadto, 2

-wymiarowe wektory

|ii =







0
0

...

1
0
0

...

0
0







←− i−ta pozycja

2.2. UKŁADY ZŁOŻONE

tworzą bazę ortogonalną w C

Elementami tej przestrzeni są wszystkie możliwe superpozycje stanów

kwantowych reprezentowane iloczynami tensorowymi odpowiednich wekto-
rów. Ponieważ wszystkie stany kwantowe są niezmiennicze względem mnoże-
nia przez dowolny skalar, więc bez utraty ogólności odpowiadające im wek-
tory mogą być znormalizowane do długości 1.

Zatem przestrzeń stanów dla n qubitów posiada 2

wzajemnie ortogo-

nalnych stanów postaci {|0i, |1i, |2i, . . . , |ii, . . . |2

− 1i}, gdzie i jest licz-

bą naturalną przedstawioną za pomocą n-bitowego kodu binarnnego, i ∈
{0, 1, 2, . . . , 2

− 1}. Stosuje się również równoważny zapis wykorzystujący

bezpośrednio wagowy kod binarny liczby naturalnej

i =

n−1

k=0

to znaczy |ii = |a

n−1

, a

n−2

, . . . , a

, a

i gdzie a

, k = 0, 1, 2, . . . , n − 1

przyjmujące wartości 0 lub 1 są współczynnikami odpowiadającymi wagom
2

, k = 0, 1, 2, . . . , n − 1. Zatem, wektor |ii ∈ C

posiada 1 na i + 1-pozycji,

a zera na wszystkich pozostałych. Wykorzystując iloczyn tensorowy wektor
|ii można przedstawić w następującej postaci

|ii = |a

n−1

, a

n−2

, . . . , a

, a

= |a

n−1

i ⊗ |a

n−2

i ⊗ . . . ⊗ |a

i ⊗ |a

Zgodnie z zasadami mechaniki kwantowej stany kwantowe są niezmien-

nicze względem mnożenia przez dowolny skalar, więc bez utraty ogólności
odpowiadające im wektory mogą być znormalizowane o normie 1.

Stan układu n qubitów jest znormalizowanym wektorem |ψi w przestrzeni

, który może być przedstawiony w postaci liniowej kombinacji 2

orto-

normalnych wektorów bazowych |0i, |1i, . . . , |2

− 1i.

|ψi =

−1

i=0

|ii,

(2.5)

przy czym

−1

i=0

|α

= 1.

(2.6)

Przykładowo, dla układu kwantowego złożonego z 2 qubitów 4 wektory

bazowe wzajemnie ortonormalne {|00i, |01i, |10i, |11i} są postaci

|00i = |0i ⊗ |0i =

1
0

⊗

1
0







1
0
0
0





 ,

ROZDZIAŁ 2. PODSTAWY MATEMATYCZNE

|01i = |0i ⊗ |1i =

1
0

⊗

0
1







0
1
0
0





 ,

|10i = |1i ⊗ |0i =

0
1

⊗

1
0







0
0
1
0





 ,

|11i = |1i ⊗ |1i =

0
1

⊗

0
1







0
0
0
1





 .

Natomiast dla układu kwantowego złożonego z 3 qubitów bazowe stany wza-
jemnie ortonormalne w 8-wymiarowej zespolonej przestrzeni C

są postaci

następującej

{|0i, |1i, |2i, |3i, |4i, |5i, |6i, |7i} ,

lub w zapisie binarnym

{|000i, |001i, |010i, |011i, |100i, |101i, |110i, |111i} .

Przykładowo bazowy stan kwantowy |2i = |010i jest reprezentowany

w przestrzeni C

następującym 8-wymiarowym wektorem:

|010i = |0i ⊗ |1i ⊗ |0i =

1
0

⊗

0
1

⊗

1
0







0
0
1
0
0
0
0
0







Natomiast bazowy stan kwantowy |5i = |101i jest reprezentowany w prze-

2.3. BARMKI KWANTOWE

strzeni C

następującym 8-wymiarowym wektorem:

|010i = |1i ⊗ |0i ⊗ |1i =

0
1

⊗

1
0

⊗

0
1







0
0
0
0
0
1
0
0







W podobny sposób można przedstawić pozostałe ortonormalne wektory ba-
zowe w przestrzeni C

2.3

Barmki kwantowe

Operacje komputera kwantowego są reprezentowane przez bramki kwanto-
we. Bramki te pełnią rolę analogiczą do roli klasycznych bramek logicznych.
Bramki kwantowe są reprezentowane przez macierze unitarne, a najważniej-
szą różnicą jaka się tu pojawia w stosunku do klasycznych operacji logicznych
jest unitarność tych bramek. Macierze unitarne spełniają następującą pod-
stawową równość

−1

= U

∗

(2.7)

gdzie symbol U

∗

oznacza sprzężenie Hermitowskie macierzy U czyli transpo-

zycję połączoną ze sprzężeniem zespolonym wszystkich elementów.

Wymaganie unitarności operacji komputera kwantowego wynika z zasad

mechaniki kwantowej gdzie operacji ewolucji są reprezentowane przez macie-
rze unitarne działające na wektory stanu.

2.3.1

Bramki 1-qubitowe

Podstawowe operacje kwantowe wykonywane na pojedynczym qubicie repre-
zentowane są 2 × 2-wymiarowymi macierzami unitarnymi U będącymi linio-
wymi, wzajemnie odwracalnymi odwzorowaniami w zespolonej przestrzeni
C

Ponadto, macierze te reprezentują w zespolonej przestrzeni C

obroty wo-

kół początku układu współrzędnych, które nie zmieniają długości poszcze-
gólnych wektorów. Zatem dla pojedynczego qubitu teoretycznie istnieje nie-
skończenie wiele różnych kwantowych bramek logicznych, odpowiadających
poszczególnym macierzom unitarnym U oraz realizujących zadaną kwantową
operację matematyczną.

ROZDZIAŁ 2. PODSTAWY MATEMATYCZNE

W praktyce wystarczy jednak posługiwać się kilkoma odpowiednio wy-

branymi podstawowymi kwantowymi bramkami logicznymi, którym odpo-
wiadają pewne odpowiednio dobrane macierze unitarne. Ponieważ macierze
U reprezentujące poszczególne operacje kwantowe są macierzami unitarny-
mi więc z definicji są one odwracalne, a zatem odpowiadające im operacje
kwantowe są operacjami rewersyjnymi to znaczy odwracalnymi.

Warto zaznaczyć, że w przypadku klasycznej algebry Boole’a w odniesie-

niu do jednego bitu istnieją tylko dwie operacje logiczne, to znaczy identycz-
ność I oraz negacja NOT. W układach kwantowych operacje te są reprezen-
towane odpowiednio następującymi macierzami:

I =

1 0
0 1

NOT =

0 1
1 0

(2.8)

Przykładowo, działanie bramki NOT dla wektorów bazowych |0i oraz |1i

zdefiniowane jest w następujący sposób

NOT|0i = |1i,

NOT|1i = |0i.

Pozwala to na znalezienie reprezentacji macierzowej bramki NOT

NOT =

0 1
1 0

(2.9)

Biorąc pod uwagę postać macierzy unitarnej NOT reprezentującej operację
negacji oraz stosując zapis wektorowy otrzymuje się następującą zależność:

NOT|ψi = NOT(α|0i + β|1i)

= αNOT|0i + βNOT|1i
= α|1i + β|0i

Zatem, działanie kwantowej bramki NOT dla dowolnego znormalizowanego
stanu kwantowego |ψi = α|0i + β|1i reprezentowanego wektorem o współ-
czynnikach zespolonych α, β, można przedstawić następująco:

NOT|ψi = α|1i + β|0i ≡ |¬ψi.

Do oznaczenia negacji stanu qubitu użyty został symbol ¬.

Bramka NOT jak każda bramka kwantowa jest odwracalna. Można to

łatwo pokazać za pomocą następujących przekształceń

NOT(NOT)

−1

0 1
1 0

¸ ·

0 1
1 0

−1

0 1
1 0

¸ ·

0 1
1 0

1 0
0 1

2.3. BARMKI KWANTOWE

Do podstawowych operacji kwantowych wykonywanych na jednym qubi-

cie oprócz opisanych powyżej operacji identyczności I oraz bramki negacji
NOT, należy także operacja realizowana przez tak zwaną bramkę Hadamar-
da i oznaczona w skrócie symbolem H. Bramka kwantowa Hadamarda jest
reprezentowana następującą 2 × 2-wymiarową macierzą unitarną

H =

√

1 −1

√

−

√

(2.10)

Działanie bramki Hadamarda H dla wektorów bazowych |0i oraz |1i moż-

na przedstawić następująco:

H|0i =

√

(|0i + |1i)

H|1i =

√

(|0i − |0i)

Wektory {H|0i, H|1i} stanowią bazę w przestrzeni stanów jednego qubitu –
bazę tą nazywa się bazą Hadamarda.

2.3.2

Bramki 2-qubitowe

W przypadku układu kwantowego złożonego z dwóch qubitów podstawo-
we operacje reprezentowane są 4 × 4-wymiarowymi macierzami unitarny-
mi. W tym przypadku spośród wszystkich możliwych podstawowych opera-
cji wykonywanych na parze qubitów w przestrzeni C

szczególne znaczenie

ma operacja, której działanie można przedstawić za pomocą następującej
4 × 4-wymiarowej unitarnej macierzy:







1 0

0 1

0 0 u





 ,

(2.11)

gdzie

D =

(2.12)

jest dowolną operacją na pojedynczyn qubicie reprezentowaną 2×2-wymiarową
unitarną macierzą D.

Operacja ta nosi nazwę „kontrolowanej bramki D”, gdyż operacja wyko-

nywana na drugim qubicie reprezentowana macierzą D zależy od tego czy
pierwszy qubit jest w stanie kwantowym |0i czy też w stanie kwantowym

ROZDZIAŁ 2. PODSTAWY MATEMATYCZNE

|1i. W przypadku, gdy pierwszy qubit jest w stanie |0i, wówczas drugi qubit
pozostaje bez zmian, natomiast gdy pierwszy qubit jest w stanie |1i, wów-
czas na drugim qubicie wykonywana jest operacja kwantowa reprezentowana
2 × 2-wymiarową macierzą unitarną D.

W szczególnym przypadku gdy macierz unitarna D jest macierzą odpo-

wiadającą operacji negacji NOT, to znaczy D = NOT uzyskuje się bram-
kę kwantową „kontrolowanej negacji” oznaczanej symbolem CNOT (ang.
controlled-NOT), której odpowiada 4×4-wymiarowa unitarna macierz CNOT.
Bramkę kwantową CNOT oznacza się również symbolem XOR gdyż jest ona
kwantowym odpowiednikiem operacji różnicy symetrycznej.

CNOT =







1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0





 .

(2.13)

Przykładowo, działanie 2-qubitowej bramki kwantowej CNOT na wektory
bazowe przestrzeni C

można przedstawić następująco:

CNOT|00i = |00i,
CNOT|01i = |01i,
CNOT|10i = |11i,

CNOT|11i = |10i.

W przypadku ogólnym działanie bramki CNOT na stan układu dwuqu-

bitowego jest dane jako

CNOT|ψi = CNOT (α|00i + β|01i + γ|10i + δ|11i)

= CNOT





α







1
0
0
0





 + β







0
1
0
0





 + γ







0
0
1
0





 + δ







0
0
0
1













= α







1
0
0
0





 + β







0
1
0
0





 + δ







0
0
1
0





 + γ







0
0
0
1







= α|00i + β|01i + δ|10i + γ|11i.

2.4. BRAMKI WIELOQUBITOWE

Proste obliczenia pokazują że bramka CNOT jest odwracalna.

CNOT CNOT

−1







1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0













1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0







−1







1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0













1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0













1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1





 = I.

2.4

Bramki wieloqubitowe

Elementarne operacje można również zdefiniować dla dowolnej liczby qubi-
tów, powiększając odpowiednio wymiary unitarnych macierzy U reprezentu-
jących poszczególne operacje kwantowe. W przypadku układu kwantowego
zawierającego n qubitów będą to unitarne macierze 2

× 2

-wymiarowe. Ma-

cierze te zatem zawierają tyle wierszy oraz tyle kolumn ile jest wzajemnie
ortogonalnych wektorów bazowych w 2

-wymiarowej zespolonej przestrzeni

Należy wyraźnie podkreślić, że w odróżnieniu od klasycznego nierewer-

syjnego boolowskiego funktora logicznego o n wejściach posiadającego jed-
no wyjście, kwantowa bramka logiczna o n wejściach jest elementem rewer-
syjnym posiadającym n wyjść. Zatem kwantowa bramka logiczna w przy-
padku podania na jej wejście stanów kwantowych odpowiadających warto-
ściom logicznym 0 lub 1, może realizować jednocześnie n funkcji logicznych
n-argumentowych.

Podobnie jak w przypadku jednego qubitu także w przypadku układu n

qubitów teoretycznie istnieje nieskończenie wiele różnych kwantowych bra-
mek logicznych reprezentowanych odpowiednio 2

× 2

-wymiarowymi macie-

rzami unitarnymi. Tym niemniej podstawową kwantową bramką logiczną dla
układu kwantowego zawierającego n qubitów jest tak zwana bramka Toffo-
liego, stanowiąca uogólnienie bramki CNOT i reprezentowana następującą

ROZDZIAŁ 2. PODSTAWY MATEMATYCZNE

macierzą

(NOT) =







1 0 . . . 0 0 0
0 1 . . . 0 0 0

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

0 0 . . . 1 0 0
0 0 . . . 0 0 1
0 0 . . . 0 1 0







(2.14)

Niech x

, x

, . . . , x

oznacza n wejść natomiast y

, y

, . . . , y

odpowiednio n wyjść bramki Toffoliego. Wówczas

= x

dla k = 1, 2, . . . , n − 1,

(2.15)

= (x

∧ x

∧ . . . ∧ x

n−1

) ⊕ x

(2.16)

Symbol ∧ oznacza iloczyn logiczny.

Zatem w szczególnym przypadku gdy n = 2 bramka Toffoliego dla do-

wolnych wektorów bazowych realizuje na drugim wyjściu znaną klasyczną
funkcję logiczną dwóch zmiennych suma modulo dwa” x

⊕ x

zwaną inaczej

kontrolowaną negacją CNOT lub bramką kwantową XOR.

W przypadku gdy x

= 1, wówczas wyjście y

zachowuje się jak klasycz-

ny funktor logiczny NAND. Natomiast w przypadku gdy x

= 0, wówczas

wyjście y

reprezentuje funktor logiczny AND. Zatem n-wejściowa kwantowa

bramka logiczna Toffoliego jest bramką uniwersalną. Za jej pomocą można
zrealizować dowolną n-argumentową funkcję logiczną.

Uogólnieniem kwantowej bramki Λ

(NOT) jest kwantowa bramka ozna-

czona symbolem Λ

(U), której działanie reprezentuje 2

× 2

-wymiarowa

macierz unitarna

(U) =







1 0 . . . 0

0 1 . . . 0

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

...

0 0 . . . 1

0 0 . . . 0 u

0 0 . . . 0 u21 u







(2.17)

gdzie

U =

(2.18)

reprezentującą wybraną kwantową bramkę logiczną dla jednego qubitu.

2.4. BRAMKI WIELOQUBITOWE

Przykładowo, mogą to być macierze następującej postaci:

F =

iπ/4

cos(π/8)

iπ/4

sin(π/8)

−e

−iπ/4

sin(π/8) e

−iπ/4

cos(π/8)

G =

cos(π/8) − sin(π/8)

sin(π/8)

cos(π/8)

H =

−iπ/4

iπ/4

J =

0 e

−iπ/4

Każda z przedstawionych macierzy unitarnych reprezentuje obrót o pewien
ustalony kąt wokół początku układu współrzędnych w zespolonej przestrzeni
C

. Zatem reprezentują one działanie jednoqubitowe. Ogólnie, dowolny obrót

(rotacja) w przestrzeni C

może być przedstawiona za pomocą następującej

2 × 2-wymiarowej macierzy unitarnej:

V (θ, φ) =

cos(θ/2)

−ie

−iφ

sin(θ/2)

−ie

iφ

sin(θ/2)

cos(θ/2)

(2.19)

Działanie ciągu kolejnych n-qubitowych operacji kwantowych można przed-
stawić w postaci iloczynu macierzy unitarnych odpowiadających poszczegól-
nym operacjom lub podobnie jak w klasycznej teorii automatów w postaci
schematu połączeń.

Ponieważ Λ

(U)

−1

= Λ

(U)

można pokazać, że bramka Toffoliego jest

operacją odwracalną.

Poniższe proste przykłady ilustrujące działanie bramek kwantowych. Roz-

patrzmy efekt działania bramki kwantowej Λ

(H) reprezentowanej 4 × 4-

wymiarową macierzą unitarną postaci:

(H) = U







1 0

0 1

0 0

√

0 0

√

−

√







(2.20)

Załóżmy, że stan |ψi jest superpozycją stanów kwantowych |2i = |10i

ROZDZIAŁ 2. PODSTAWY MATEMATYCZNE

oraz |3i = |11i.

|ψi =

√

(|2i + |3i) =

√

(|10i + |11i)

√

µ·

0
1

⊗

1
0

0
1

⊗

0
1

¸¶

√













0
0
1
0





 +







0
0
0
1











 =

√







0
0
1
1





 .

Działanie bramki U

na stan |ψi odpowiada wykonaniu mnożenia

|ψi =

√







1 0

0 1

0 0

√

0 0

√

−

√













0
0
1
1





 =







0
0
1
0





 = |10i

Analogicznie dla stanu |φi =

√

(|10i − |11i) możemy zapisać

|φi =

√

µ·

0
1

⊗

1
0

−

0
1

⊗

0
1

¸¶

√







0
0
1

−1





 ,

działanie bramki U

odpowiada wykonaniu mnożenia

|φi =

√







1 0

0 1

0 0

√

0 0

√

−

√













0
0
1

−1





 =







0
0
1
0





 = |11i.

Powyższe dwa przykłady ilustrują bardzo istotny dla konstrukcji algo-

rytmów obliczeń kwantowych efekt redukcji pewnych stanów kwantowych
w wyniku wykonywania operacji kwantowych reprezentowanych bramkami
kwantowymi.

2.5

Splątanie

Istotnym pojęciem związanym z dowolnym układami wieloqubitowymi jest
tak zwane splątanie (ang. entanglement) [27, 12]. Splątanie, zwane również

2.5. SPLĄTANIE

zawikłaniem, jest bezpośrednim efektem wykonania iloczynu tensorowego na
2-wymiarowych wektorach reprezentujących poszczególne qubity. Ze znanych
własności iloczynu tensorowego wynika, że na podstawie znajomości wektora
będącego iloczynem tensorowym dwóch lub więcej wektorów nie można, po-
za szczególnymi przypadkami (ortonormalne wektory bazowe), jednoznacznie
wyznaczyć wektorów stanowiących czynniki tego iloczynu tensorowego. Na-
leży wyraźnie zaznaczyć, że pojęcie splątanie nie występuje w standardowej
algebrze Boole’a.

Splątanie oznacza zatem, że dany stan kwantowy |ψi ∈ C

nie może

być przedstawiony jednoznacznie w postaci iloczynu tensorowego n stanów
kwantowych |ψ

i ∈ C

, i = 1, 2, . . . , n. Oznacza to, że między poszczególnymi

stanami kwantowymi |ψ

i istnieją wzajemne korelacje. Przykładowo, niech

|ψi =

√

(|1i − |2i) =

√

(|01i − |10i).

(2.21)

Wektor ten reprezentuje stan kwantowy będący wynikiem zawikłania,

gdyż nie można znaleźć dwóch stanów kwantowych |ψ

i oraz |ψ

is takich, że

|ψi = |ψ

i ⊗ |ψ

Pojęcie zawikłania wiąże się bezpośrednio z tak zwaną bazą ortogonalną Bel-
la, którą w zespolonej przestrzeni C4 tworzą następujące 4 wzajemnie orto-
gonalne wektory bazowe:

|ψ

i =

√

(|0i ⊗ |1i + |1i ⊗ |0i)

(2.22)

|ψ

−

i =

√

(|0i ⊗ |1i − |1i ⊗ |0i)

(2.23)

|φ

i =

√

(|0i ⊗ |0i + |1i ⊗ |1i)

(2.24)

|φ

−

i =

√

(|0i ⊗ |0i − |1i ⊗ |1i)

(2.25)

Dowolny układ kwantowy złożony z 2 qubitów jest zawikłany poprzez

pewną 4 × 4-wymiarową macierz unitarną. Można dowieść, że zawikłanie
układu kwantowego złożonego z 3 lub ogólnie większej liczby qubitów może
być zawsze rozpatrywane jako superpozycja zawikłań układów kwantowych
złożonych z 2 qubitów.

ROZDZIAŁ 2. PODSTAWY MATEMATYCZNE

2.6

Układy bramek kwantowych

Podobnie jak w przypadku klasycznych bramek logicznych, także bramki
kwantowe mogą być łączone ze sobą tworząc układy bramek kwantowych
[7]. Interesującym zagadnieniem z punktu widzenia ewentualnych zastosowań
bramek kwantowych jest możliwość sumulowania działania poszczególnych
bramek kwantowych przez sekwencje innych bramek kwantowych.

Problem ten wiąże się bezprośrednio z zagadnieniem tak zwanej uniwer-

salności bramek kwantowych, które polega na wyznaczeniu zbioru bramek
kwantowych, za pomocą których można zastępowac (przynajmniej z pew-
nym przybliżeniem) działanie dowolnych bramek kwantowych. Zagadnienie
uniwersalności bramek kwantowych było rozpatrywane w wielu publikacjach,
gdzie sformułowano różnego rodzaju warunki uniwersalności.

W oparciu o znane z algebry metody dekompozycji macierzy unitarnych,

można okreslić liczbę oraz rodzaj uniwersalnych bramek kwantowych po-
trzebnych do symulacji dowolnej bramki kwantowej. Rozpatrzmy najpierw
najprostszy przypadek gdy m = 1. Wiadomo [6, 5, 8] że dla dowolnej macie-
rzy unitarnej U, działanie bramki kwantowej Λ

(U) może być symulowane

za pomocą układu zawierającego co najwyżej sześć odpowiednio połączo-
nych bramek kwantowych, a mianowicie: cztery 1-qubitowe bramki kwantowe
Λ

), k = 1, 2, 3, 4 z odpowiednio dobranymi macierzami unitarnymi U

oraz dwie 2-qubitowe bramki kwantowe Λ

(CNOT).

Podobnie dla dowolnej macierzy unitarnej U, działanie bramki kwanto-

wej Λ

(U) może być symulowane za pomocą układu zawierająego co najwy-

żej szesnaście odpowiednio połączonych bramek kwantowych, a mianowicie:
osiem 1-bitowych bramek kwantowych Λ

), k = 1, 2, . . . , 8, z odpowied-

nio dobranymi macierzami unitarnymi U

, oraz osiem 2-bitowych bramek

kwantowych Λ

(CNOT).

W ogólnym przypadku, dla dowolnej macierzy unitarnej U, działanie

bramki kwantowej Λ

(U) może być symulowane za pomocą układu zawiera-

jącego co najwyżej 2

−1 bramek kwantowych typu Λ

), k = 1, 2, . . . , 2

−

1 z odpowiednio dobranymi macierzami unitarnymi U

, oraz 2

− 2 bramek

kwantowych typu Λ

(CNOT) [6, 4, 5, 8, 9].

Należy zaznaczyć, że w pewnych szczególnych przypadkach możliwe jest

symulowanie działania odpowiednich bramek kwantowych przez mniejszą
liczbę uniwersalnych bramek kwantowych. Rozpatrzmy kilka tego typu szcze-
gólnych przypadków.

1. Dla n ≥ 5 oraz m ∈ {3, ..., [n/2]}, (gdzie symbol [n/2] oznacza część cał-

kowitą liczby rzeczywistej n/2), działanie bramki kwantowej Λ

(CNOT)

2.6. UKŁADY BRAMEK KWANTOWYCH

może być symulowane za pomocą układu zawierającego 4(m − 2) bra-
mek kwantowych typu Λ

(CNOT).

2. Dla n ≥ 5 oraz m ∈ {2, ..., n − 3}, działanie bramki kwantowej Λ

n−2

(CNOT)

może być symulowane za pomocą układu zawierającego 2 bramki kwan-
towe typu Λ

(CNOT) oraz dwie bramki kwantowe typu Λ

n−m−1

(CNOT).

3. Dla m ≥ 7, działanie bramki kwantowej Λ

m−2

(CNOT) może być symu-

lowane za pomocą układu zawierającego 8(m − 5) bramek kwantowych
typu Λ

(CNOT).

W powyższych rozważaniach zakładano, że symulacja dzialania poszcze-

gólnych bramek kwantowych jest dokładna. Zakłada ona, ze macierze unitar-
ne reprezentujące symulowaną bramkę kwantową oraz symulujący układ bra-
mek kwantowych są identyczne. Możliwa jest jednak także symulacja przy-
bliżona zwana również aproksymacyjną. Symulacja aproksymacyjna z do-
kładnością ² > 0 oznacza, ze odległość euklidesowa pomiędzy macierzami
unitarnymi reprezentującymi symulowaną bramkę kwantową oraz układem
symulującym jest mniejsza od ².

W przypadku symulacji aproksymacyjnej liczba użytych bramek kwan-

towych w układzie symulującym w istotny sposób zależy nie tylko od wy-
miarowości m bramki kwantowej lecz także od przyjętej dokładności symu-
lacji ². Należy wyraźnie podkreslić, że liczba bramek kwantowych nawet w
przypadku bramek jednobitowych jest continuum. Symulacja aproksymacyj-
na może mieć zatem istotne znaczenie aplikacyjne gdyż w praktyce dysponuje
się uniwersalnymi bramkami logicznymi jedynie dla pewnej skończonej licz-
by macierzy unitarnych, a zatem możliwa jest wówczas jedynie symulacja
aproksymacyjna.

Rozdział 3

Algorytmy kwantowe

Podstawowym zagadnieniem związanym z obliczeniami wykonywanymi za
pomocą komputerów jest zaproponowanie odpowiedniego algorytmu oblicze-
niowego. Komputer kwantowy przeprowadza obliczenia w oparciu specjalne
algorytmy obliczeniowe nie stosowane w informatyce klasycznej. Kwantowe
algorytmy są sekwencjami kwantowych operacji reprezentowanych odpowied-
nio zdefiniowanymi macierzami unitarnymi. Algorytmy te dostosowane do
możliwości obliczeniowych komputera kwantowego w istotny sposób wyko-
rzystują prawa mechaniki kwantowej, a w szczególności zjawisko superpozycji
stanów kwantowych.

Istotnym problemem klasycznej teorii algorytmów jest określenie złożono-

ści obliczeniowej danego algorytmu. Ogólnie klasyczne algorytmy obliczenio-
we dzieli się na dwie podstawowe grupy: algorytmy o wielomianowej złożono-
ści obliczeniowej oraz algorytmy o eksponencjalnej złożoności obliczeniowej.
W przypadku algorytmów kwantowych różnica pomiędzy tymi dwoma rodza-
jami złożoności obliczeniowej nie ma tak istotnego znaczenia jak w przypadku
algorytmów klasycznych.

Do najważniejszych algorytmów kwantowych należą:

1. algorytm poszukiwań opracowany przez Grovera w 1997 roku,

2. algorytm faktoryzacji liczb naturalnych zaproponowany w 1993 roku

przez Shora.

3.1

Algorytm Grovera

W 1997 roku Grover zaproponował [16, 15, 17] kwantowy algorytm wyszuki-
wania informacji w dużych zbiorach danych. Problem polega na wyszukaniu
w nieuporządkowanym zbiorze danych {d

, i = 1, 2, . . . , N} zawierającym N

3.1. ALGORYTM GROVERA

elementów określonego elementu d

= y. Przykładowo, może to być wyszuka-

nie w spisie telefonów danego numeru telefonu nie znając nazwiska abonenta.

Klasyczne algorytmy poszukiwań potrzebuje średnio N/2 kroków na wy-

szukanie danej informacji w zbiorze danych zawieraj1cym N elementów. Al-
gorytm kwantowy zaproponowany przez Grovera jest w tym przypadku bar-
dziej efektywny i potrzebuje średnio N kroków na wyszukanie właściwego
elementu w zbiorze N elementów.

Każdy element zbioru, w którym prowadzimy poszukiwania ma określony

indeks i. Zatem problem wyszukiwania sprowadza się w zasadzie do wyzna-
czenia na drodze przekształceń unitarnych odpowiedniego indeksu określa-
jącego dany element w zbiorze. Inaczej mówiąc, należy wyznaczyć operacje
unitarną

U|ii =

|ii jeżeli i = j,
−|ii jeżeli i 6= j.

(3.1)

gdzie j jest indeksem poszukiwanego elementu.

Zatem wraz ze wzrostem liczby wykonanych iteracji k wzrasta również

amplituda stanu kwantowego a

(k), i uzyskuje ona swoje maksimum dla licz-

by iteracji odpowiadającej w przyblizeniu wartości k

max

≈

1
4

π2

L/2

O efektywności algorytmu Grovera najlepiej świadczy nastepujący przy-

kład. W zagadnieniach klasycznej kryptografii przy dekodowaniu nieznanych
szyfrów występuje konieczność wyszukiwania zadanych elementów w zbiorze
zawierającym około N = 10

nieuporządkowanych elementów. Najszybszy

z istniejących klasycznych komputerów wykonałby taką czynność w czasie
około tysiąca lat. Natomiast komputer kwantowy wykorzystujący przedsta-
wiony powyżej algorytm wyznaczył by poszukiwany element zbioru w ciągu
około czterech minut.

Algorytm Grovera może być uogólniony i zastososwany do jednoczesne-

go poszukiwania kilku wybranych elementów w nieuporz1dkowanym zbio-
rze danych, oraz do wyszukiwania największego lub najmniejszego elementu
w zbiorze.

3.1.1

Operator Grovera

Kwantowy algorytm poszukiwań składa się z trzech podstawowych kroków,
a mianowicie:

1. utworzenie początkowego stanu kwantowego, o jednakowych amplitu-

dach wszystkich qubitów bazowych,

2. wykonanie transformacji Hadamarda na początkowym stanie kwanto-

wym,

ROZDZIAŁ 3. ALGORYTMY KWANTOWE

3. dokonanie wielokrotnej selektywnej rotacji wokół począku układu współ-

rzędnych.

Bierwszym krok algorytmu Grovera polega na przygotowaniu płaskiej su-

perpozycji wszystkich stanów bazowych. Dokonujemy tego wykonując ope-
rację H

= H

⊗N

= H ⊗ H ⊗ . . . ⊗ H

}

N razy

na stanie |0 . . . 0i

⊗N

|0 . . . 0i =

√

N −1

i=0

|ii

(3.2)

Iteracje algorytmu Grovera są opisane za pomocą operacji G zdefiniowe-

anej jako ciąg operacji elementarnych. Operację tą nazywamy operatorem
Grovera.

1. Obrót fazy dla wszystkich stanów z wyjątkiem |x

|xi = −(−1)

xx0

|xi

(3.3)

gdzie

1 x = x

0 x 6= x

(3.4)

2. Wykonanie bramki −H

⊗n

3. Obrót fazy dla wszystkich stanów z wyjątkiem |0 . . . 0i

|xi = S − (−1)

|xi

(3.5)

gdzie

1 x = 0 . . . 0
0 x 6= 0 . . . 0

(3.6)

4. Drugie wykonanie bramki Hadamarda H

⊗n

Zatem operator Grovera jest używany do manipulacji amplitudą. Ze wzglę-

du na tożsamość

|xi = −(−1)

|xi =

−|xi x = 0 . . . 0

|xi x 6= 0 . . . 0

(3.7)

3.1. ALGORYTM GROVERA

and

(2|0 . . . 0ih0 . . . 0| − I)|xi =

2|xi − |xi x = 0 . . . 0

|xi

x 6= 0 . . . 0

(3.8)

−|xi x = 0 . . . 0

|xi x 6= 0 . . . 0

(3.9)

operacja G

może być zapisany jako G

= 2|0 . . . 0ih0 . . . 0| − 1

Operacje 2-4 stanowią elementy operatora nazywanego operatorem dyfuzji
lub operatorem obrotu wokół średniej. Zastosowanie operatora Grovera do
ogólnego stanu |αi =

|ni daje stan

|ni =

−|ni +

|yi

(−α

+ 2s) |ni,

(3.10)

gdzie

s =

(3.11)

to średnia arytmetyczna współczynników α

, i = 1, . . . , N .

Na rysumku 3.1 przedstawiony jest schemat wykonania algorytmu Grove-

ra. Ostatnim etapem wykonania algorytmu jest pomiar stanu układu. Licz-

Rysunek 3.1: Operacje elementarne wykorzystywane w algorytmie Grovera

ba iteracji musi być dobrana tak by prawdopodobieństwo zmierzenia układu
w wyróżnionym stanie było jak największe.

ROZDZIAŁ 3. ALGORYTMY KWANTOWE

Po wykonaniu pierwszej iteracji amplituda a

stanu |yi będzie nieco więk-

sza niż amplitudy a

pozostałych stanów kwantowych występujących w su-

perpozycji. Można wykazać, że po każdej wykonanej iteracji otrzymany w jej
wyniku stan kwantowy jest następującej postaci:

|ψi =

x6=y

+ α

|yi

(3.12)

Zatem w miarę wykonywania kolejnych iteracji amplituda α

stanu kwan-

towego |yi coraz bardziej różni się od amplitud ax pozostałych stanów kwan-
towych |xi. Przeprowadzając odpowiednie obliczenia można wykazać, że po
wykonaniu k-tej iteracji algorytmu amplituda stanu kwantowego wynosi

(k) = sin((2k + 1)j), gdzie sin

(j) = 2

−n

(3.13)

Zatem wraz ze wzrostem liczby wykonanych iteracji k wzrasta również

amplituda stanu kwantowego ay(k), oraz uzyskuje ona swoje maksimum dla
liczby iteracji odpowiadającej w przyblizeniu wartości k

max

= 1/4π2

n/2

Ilustracją algorytmu Grovera dla bazy danych złożonej z ośmiu elemntów

jest rysunek 3.2.

3.2

Algorytmy Shora

Peter Shor w pracach [24] oraz [25] podał algorytm pozwalający na przepro-
wadzenie z wykorzystaniem komputera kwantowego rozkładu liczby całkowi-
tej na czynniki pierwsze. W porównaniu z dotychczas znanymi algorytmami
klasycznymi, algorytm Shora odznacza się złożonością wielomianową wzglę-
dem rozmiaru danych wejściowych. W tej samej pracy podany został także
algorytm obliczania logarytmów dyskretnych.

Rodzina algorytmów zawierająca algorytm Shora wywodzi się z propo-

zycji D. Simona [26]. Na rysunku 3.3 przedstawione są schematy trzech naj-
prostszych algorytmów z tej grupy.

Algorytmy faktoryzacji i obliczania logarytmów dyskretnych podane przez

Shora stanowią uogólnienie metody wprowadzonej przez Simona.

3.2.1

Znajdowanie rzędu w grupie

Zasadniczą częścią algorytmu faktoryzacji jest, wykonywana na komputerze
kwantowym, procedura znajdowania rzędu. Tylko ta część musi być wyko-
nana na maszynie kwantowej – pozostałe części mogą być z powodzeniem

3.2. ALGORYTMY SHORA

Rysunek 3.2: Reprezentacja gometryczna algorytmu Grovera dla zbioru 8
elementów reprezentowanych przez trzy qubity

ROZDZIAŁ 3. ALGORYTMY KWANTOWE

|0i

|1i

|x,

→

|x,

)

⊕

Algorytm Deutscha

⊗n

|x,

→

|x,

)

⊕

⊗n

Algorytm Simona

|0 . . . 0i

QF T

|0 . . . 0i

|x,

→

|x,

QF T

Algorytm Shora

Rysunek 3.3: Sieci bramek kwantowych dla algorytmów ukrytej podgrupy.

3.2. ALGORYTMY SHORA

wykonane na maszynie klasycznej. W kolejnych paragrafach przedstawię pro-
cedurę znajdowania rzędu oraz jej wykorzystanie w problemach faktoryzacji
i obliczania logarytmów dyskretnych.

Rzędem elementu a w grupie (Z

, ·) nazywamy najmniejszą liczbę całko-

witą r spełniającą warunek

= 1 mod N.

Liczbę r oznaczamy pisząc r = ord

(a). Stosując zapis symboliczny

r = ord

(a) = min {x ∈ Z|m

= 1 mod N}

Jeżeli liczba a jest względnie pierwsza z N to ord

(a) istnieje. W przeciwnym

wypadku gcd(a, N ) 6= 1 więc a

− bN jest podzielne przez gcd(a, N ) dla

dowolnych m i b, gdzie gcd(a, b) oznacza największy wspólny dzielnik liczb
a i b.

Określmy funkcję f

(x) := a

( mod N), przy założeniu gcd(a, N ) = 1.

Zgodnie z definicją rzędu

(x + r) = a

x+r

( mod N) = a

( mod N) = f

(x),

co oznacza, że r = ord

(a) jest okresem funkcji f

. Pozwala to wykorzystać

własności transformaty Fouriera do znalezienia liczby r.

Naszym zadaniem jest rozwiązanie następującego problemu: Mając dane

liczby N oraz a, takie, że gcd(a, N ) = 1, znajdź okres funkcji f

: Z → Z

określonej wzorem f

(x) = a

( mod N).

Pierwsza przeszkoda jaka się pojawia wynika z ograniczenia reprezentacji

liczb. Nie możemy w pamięci komputera kwantowego umieścić wszystkich
liczb całkowitych. Musimy zatem rozpatrywać tylko obcięcie funkcji f

pewnego skończonego podzbioru Z

⊂ Z i na nim badać okresowość funkcji

Przestrzeń Hilberta komputera kwantowego, na którym ma się odbywać

algorytm znajdowania okresu, można przedstawić w postaci H

⊗ H

, przy

czym pierwsza podprzestrzeń odpowiada rejestrowi, w którym przechowy-
wane są argumenty funkcji f

, a druga – rejestrowi zawierającemu wartości.

Rejestry te – a co za tym idzie wymiary q = dim H

oraz d = dim H

pod-

przestrzeni – muszą być dobrane tak aby pomieściły odpowiednio duże liczby.
Dobór odpowiednich wymiarów przestrzeni wynika z oszacowania szans po-
wodzenia algorytmu.

3.2.2

Szybka faktoryzacja

Problem (efektywnego) znajdowania dzielników liczby N można rozwiązać
jeżeli potrafimy (efektywnie) obliczać rząd elementu w multiplikatywnej gru-
pie Z

. Mówiąc precyzyjnie, zastępujemy zagadnienie znalezienia dzielników

ROZDZIAŁ 3. ALGORYTMY KWANTOWE

liczby N, zagadnieniem następującym Mając daną liczbę N oraz liczbę a,
względnie pierwszą z N, znajdź rząd ord

(a)

Załóżmy, że znamy efektywny sposób rozwiązania tego problemu.
Pierwszą czynnością jaką musimy wykonać jest wybranie losowej liczby

a takiej, że gcd(a, N) = 1. Liczba a musi być względnie pierwsza z N aby
istniał rząd ord

(a).

Okres funkcji f (x) = a

( mod N) jest rzędem elementu a.

f (x + r) = a

x+r

( mod N) = a

( mod N) = f (x)

(3.14)

Ponieważ nie jest możliwa reprezentacja całej dziedziny całkowitej w pa-

mięci (stanach) komputera kwantowego, wybieramy pewną poddzedzinę Z

funkcji f , z q będącą potęgą dwójki spełniającą warunek N < q < 2N.

Algorytm znajdowania rzędu jest zatem algorytmem znajdowania okresu

funkcji f . Wymaga on dwóch rejestrów kwantowych i przebiega w następu-
jący sposób:

1. Ustaw w superpozycji wszystkie elementy Z

wykonując transformatę

Fouriera

√

q−1

k=0

|xi|0i

(3.15)

2. Umieść wartość funkcji f (x) = a

( mod N) w drugim rejestrze

√

q−1

k=0

|xi|f (k)i

(3.16)

3. Wykonaj drugi raz transformatę Fouriera

√

q−1

k=0

q−1

l=0

exp

2iπkl

|li|f (k)i.

(3.17)

Otrzymane w wyniku pomiarów liczby mogą zostać użyte do uzyskania

za pomocą rozwinięć ułamków ciągłych rzędu liczby a. Natomiast znajomość
rzędu a pozwala na znalezienie nietrywialnych dzielników N.

3.3

Kwantowa transformata Fouriera

Do reprezentacji danych wejściowych dla algorytmów kwantowych wykorzy-
stujemy stany układów kwantowych – operacja QFT jest przykładem trans-
formaty, która może być wykonana na stanach kwantowych efektywniej niż
na stanach układu klasycznego [18].

3.3. KWANTOWA TRANSFORMATA FOURIERA

Poniżej ograniczymy się do przypadku, gdy w zbiorze danych wejścio-

wych algorytmu możemy określić strukturę grupy abelowej. Uogólnienie na
przypadek grup nieabelowych można znaleźć w pracach [23, 20].

W skończeniewymiarowej przestrzeni Hilberta H odpowiadającej ukła-

dowi wybieramy bazę ortonormalną {|gi|g ∈ G} ponumerowaną elementami
g ∈ G, gdzie G jest pewną skończoną grupą abelową. Wymiar przestrzeni wy-
nosi w takim wypadku |G|, gdzie przez | · | oznaczamy rząd grupy. Dowolny
wektor stanu układu |ψi ma rozkład w bazie {|gi|g ∈ G}

|ψi =

|G|

i=1

(3.18)

W zbiorze odwzorowań liniowych {f : G → C} definiujemy iloczyn ska-

larny

i :=

g∈G

(g)f

(g)

(3.19)

Współczynniki rozkładu 3.18 mogą być potraktowane jako wartości pew-

nej funkcji f : G → C określonej wzorem

f (g

) = c

(3.20)

oraz spełniającej warunek

||f || = 1

(3.21)

z normą wyznaczaną przez iloczyn skalarny 3.19.

Transformata Fouriera ˆ

f funkcji f określona jest wzorem

f (g

) =

|G|

|G|−1

k=0

2iπgj gk

|G|

f (g

(3.22)

Jednocześnie każde odwzorowanie 3.20 w sposób jednoznaczny definiu-

je stan na H. Dzięki tej jednoznaczności możemy sformułować następującą
definicję

Definicja 2 Kwantowa transformata Fouriera jest to transformata Fouriera
funkcji f zadającej stan układu kwantowego.

Działanie transformaty Fouriera na stan bazowy |ji ∈ H w d-wymiarowej

przestrzeni wektorowej, określone jest wzorem

QFT|ji =

√

d−1

k=0

2iπjk

|ki

(3.23)

ROZDZIAŁ 3. ALGORYTMY KWANTOWE

Dzięki liniowości transformaty Fouriera, wzór ten może być rozszerzony na
dowolny wektor i przyjęty za definicją transformaty.

Ponieważ dla funkcji f i jej transformaty zachodzi tożsamość Parsevala

||f || = || ˆ

f ||

(3.24)

kwantowa transformata Fouriera jest operacją unitarną.

Transformata Hadamarda Najprostszym i najczęściej spotykanym przy-
kładem kwantowej transformaty Fouriera jest transformata Hadamarda. W tym
wypadku G = B = {0, 1}, a działaniem grupowym jest dodawanie modulo 2.
Przestrzeń Hilberta odpowiadająca zbiorowi B ma bazę {|0i, |1i}.

Transformata Fouriera na B jest określona jako odwzorowanie

f (x) =

√

(−1)

0·x

f (0) + (−1)

1·x

f (1)

√

f (0) + (−1)

f (1)

Odpowienio kwantowa transformata Fouriera działa na stany bazowe zgod-

nie ze wzorem

QF T

|xi =

√

(−1)

0·x

|0i + (−1)

1·x

|1i

√

|0i) + (−1)

|1i

i jest reprezentowana przez macierz unitarną H

H =

√

1 −1

(3.25)

Bramka Hadamarda jest przydatna przy konstrukcji transformaty Fouriera
dla dowolnej ilości qubitów.

3.3.1

Złożoność obliczeniowa

Algorytmy ukrytej podgrupy mają złożoność wielomianową dzięki możliwości
zaimplementowania szybkiej transformaty Fouriera na komputerze kwanto-
wym. Dokonajmy oszacowania złożoności tej operacji [22]. Poniższe wyprowa-
dzenie daje jednocześnie przepis na konstrukcję układu bramek kwantowych
implementującego QFT.

3.3. KWANTOWA TRANSFORMATA FOURIERA

Pierwszym krokiem jest wykonanie kilku prostych przekształceń. Niech j

będzie liczbą n-bitową, reprezentowaną przez stan bazowy |ji ∈ H. W postaci
dwójkowej liczbę tę można zapisać jako

j =

k=1

n−k

(3.26)

gdzie j

∈ {0, 1} oznacza n-ty bit liczby j.

Wychodząc ze wzoru 3.23 możemy zapisać

QFT|ji =

√

−1

k=0

2iπjk

|ki

√

. . .

2iπj(

l=1 kl2

. . . k

√

. . .

l=1

2iπjkl2

. . . k

Otrzymany stan nie jest stanem splątanym. Można go zapisać w postaci

iloczynu tensorowego odpowiednich superpozycji stanów bazowych.

QFT|ji =

√

l=1

2iπjk

−l

√

l=1

|0i + e

2iπj2

−l

|1i

Oznaczając przez 0.j

. . . j

ułamek binarny o wartości

k=l

k−l+1

(3.27)

ostatecznie zapisujemy stan QF T |ji jako

(|0i + e

2iπ0.j

|1i)(|0i + e

2iπ0.j

n−1

|1i) . . . (|0i + e

2iπ0.j

...j

|1i)

√

(3.28)

Dla przypadku trzech qubitów i j = 4j

+ 2j

+ j

można ostatni krok po-

ROZDZIAŁ 3. ALGORYTMY KWANTOWE

wyższego wyprowadzenia rozpisać bezpośrednio

QF T |ji =

(|0i + e

2iπj/2

|1i)(|0i + e

2iπj/4

|1i)(|0i + e

2iπj/8

|1i)

√

(|0i + e

2iπ(2j

/2)

|1i)(|0i + e

2iπ(j

/2+j

/4)

|1i)(|0i + e

2iπ(j

/2+j

/4+j

/8)

|1i)

√

(|0i + e

2iπ0.j

|1i)(|0i + e

2iπ0.j

|1i)(|0i + e

2iπ0.j

|1i)

√

gdzie wykorzystana została okresowość funkcji e

Na Rysunku 3.4 przedstawiony jest układ realizujący kwantową transfor-

matę Fouriera dla układu trzech qubitów.

F (4)

F (8)

F (4)

Rysunek 3.4: Transformata Fouriera dla trzech qubitów.

Bramka F (n) jest zdefiniowana dla n ∈ N jako operacja

F (n) =

0 e

2iπ

(3.29)

W tym wypadku mamy

F (4) =

1 0
0 i

, F (8) =

0 e

πi

(3.30)

Ponieważ e

2iπ

= −1, bramka Hadamarda odpowiada przy takim oznaczeniu

bramce F (2).

Ostatnia operacja oznacza bramkę SWAP, powodującą zamianę qubitów.

Bramka taka może być zrealizowana za pomocą trzech bramek CNOT.

Do wykonania operacji QFT zgodnie z podanym przepisem trzeba wyko-

nać n-krotnie bramkę Hadamarda oraz dla każdego z qubitów odpowiednią
liczbę kontrolowanych bramek F (x). Dla n-tego qubitu wykonujemy bramkę
C − F (. . .), n − 1-krotnie, dla n − 1 qubitu – n − 2 krotnie, a dla drugie-
go – jednokrotnie. Zamiana kolejności qubitów wymaga

bramek SWAP.

3.4. INNE ALGORYTMY KWANTOWE

Łącznie, musimy wykonać

(n+1)n

bramek, co oznacza, iż algorytm QFT ma

złożoność O(n

), gdzie n jest liczbą qubitów.

Warto zauważyć, że wykonywana przez nas operacja jest, ze względu

na skończoną pamięć, przybliżeniem transformaty Fouriera. Jest to sytuacja
identyczna jak w przypadku komputerów klasycznych, gdyż komputer kwan-
towy, operuje jedynie na skończonej pamięci (liczbie qubitów). To przybliże-
nie jest wystarczające do przeprowadzenia obliczeń [11].

Operowanie na skończonych ciągach symboli jest jednym z warunków

„rozsądności” modelu obliczeń. Ponieważ stany układu kwantowego i ope-
racje unitarne na nich wykonywane są zadawane przez kombinacje liniowe
wektorów oraz macierze nad ciałem C, aby mówić o skończonych obliczeniach
musimy się ograniczyć do przybliżonego przeprowadzania ewolucji. Ograni-
czamy także możliwe amplitudy, przy czym okazuje się, że zestaw amplitud
wystarczający do przeprowadzenia obliczeń kwantowych można bardzo ogra-
niczyć [11]. Otrzymujemy wówczas model równoważny pod względem mocy
obliczeniowe i bardziej realistyczny w potencjalnych implementacjach.

3.4

Inne algorytmy kwantowe

Algorytmy ukrytej podgrupy mogą znaleźć zastosowanie do szerokiej gamy
problemów matematycznych. Jako problem ukrytej podgrupy można sformu-
łować zagadnienia [21, 22]

• Znajdowanie okresu

Zastosowanie to jest pokazane w szczególności w algorytmie Shora znaj-
dowania rzędu – wówczas szukamy okresu funkcji f (x) = a

mod N.

• Ukryta funkcja liniowa

Dla funkcji f (x, y) = x + ay określonej na (Z × Z, +) o wartościach
w Z

i permutacji π : Z

→ Z

określmy

h = π ◦ f

W tym wypadku ukryta podgrupa ma posać:

{(−ta, t)|t = 1, . . . , N − 1} .

• Rząd permutacji

Dla G = (Z

× Z

, ⊕) i funkcji f : G → Z

określonej jako

f (x, y) = π

(y)

ROZDZIAŁ 3. ALGORYTMY KWANTOWE

gdzie π jest permutacją zbioru Z

. Szukamy ukrytej podgrupy

{r ∈ Z

|f (x + r, y) = f (x, y)} .

• Stabilizator grupy abelowej

Niech elementami grupy abelowej G będą odwzorowania zbioru X →
X, ze składaniem odwzorowań

a,b∈G

x∈X

(ab)(x) = a(b(x))

jako działaniem grupowym. Podzbiór St ⊂ G złożony z elementów G
dla których przy ustalonym x ∈ X

g(x) = x

tworzy podgrupę. Podgrupę ta nazywamy stabilizatorem elementu x w G
i oznaczamy St

(x). Oznaczmy przez f

odwzorowanie przeprowadza-

jące element grupy G w wartość tego elementu na x , f

(g) = g(x).

Odwzorowaniu temu odpowiada ukryta podgrupa St

(x). Stabilizator

(x) jest ukryta podgrupą dla odwzorowania f

: G → X określonego

jako

(g) = g(x) g ∈ G

W pracy [19] został podany sposób znalezienia St

(x) dla przypadku

grup albelowych. Zadanie to zawiera jako przypadki szczególne zadania
faktoryzacji i obliczania logarytmów dyskretnych.

Rozdział 4

Kwantowa teoria informacji

Kolejnym obszarem, na który wpływ może mieć zastosowanie w informatyce
praw mechaniki kwantowej, jest komunikacja i przesyłanie informacji. Nowe
spojrzenie na przesyłanie i kodowanie informacji daje nadzieje praktycznego
zastosowania w krótkim czasie protokołów kwantowych.

4.1

Gęste kodowanie

Gęste kodowanie (ang. dense coding) jest prostym przykładem potencjalnego
wykorzystania stanów splątanych do efektywniejszego (niż w przypadku kla-
sycznym) przesyłania informacji. Jak sama nazwa wskazuje, w tym wypadku
splątanie pozwala na wydajniejsze kodowanie symboli podczas przesyłania
informacji.

Załóżmy, że Ania i Bartek mają do dyspozycji stan splątany |φ

i. Ania

może wykonać na swoim podukładzie jedną z operacji unitarnych reprezen-
towanych przez macierze Pauliego

1. I =

1 0
0 1

2. σ

0 1
1 0

3. σ

0 −i

4. σ

0 −1

Odpowiada to odpowiednio przejściu w jeden ze stanów:

ROZDZIAŁ 4. KWANTOWA TEORIA INFORMACJI

1. |φ

i = I ⊗ I|φ

2. |ψ

i = σ

⊗ I|φ

3. |ψ

−

i = σ

⊗ I|φ

4. |φ

−

i = σ

⊗ I|φ

Jeżeli teraz Bartek dokona pomiaru stanu całości w bazie {|φ

i, |ψ

i} jed-

noznacznie rozróżni operację jaką wykonała Ania. Cała informacji jest tu
zawarta w korelacjach pomiędzy stanami qubitów Ani i Bartka. Zatem prze-
słanie od Ani do Bartka jednego qubitu umożliwia przesłane dwóch bitów
informacji.

4.2

Teleportacja kwantowa

Mechanika kwantowa nie zezwala na dokonanie kopii nieznanego stanu – jest
to treścią twierdzenie o nie-klonowaniu (ang. no-cloning theorem) [3]. Moż-
liwe jest jednak przesyłanie na odległość dokładnej kopii nieznanego stanu
kwantowego |xi, o ile dysponujemy kanałem kwantowym.

Załóżmy, że Ania i Bartek mają do dyspozycji stan splątany |φ

i. Aby

przesłać dokładną kopię stanu |xi = α|0i + β|1i Ania musi wykonać nastę-
pujące kroki:

1. Utworzyć układ w stanie |xi|φ

2. Dokonać pomiaru stany podukładu dwóch pierwszych qubitów w bazie

{|φ

i, |ψ

i}.

3. Przesłać do Bartka kanałem klasycznym dwa bity opisujące jej pomiar

poprzez numer wektora bazowego.

Z kolei Bartek, aby odtworzyć stan |xi, wykonuje następującą operację

na swoim podukładzie, w zależności od otrzymanej wiadomości klasycznej:

1. |φ

i → I,

2. |ψ

i → σ

3. |ψ

−

i → σ

4. |φ

−

i → σ

4.3. KWANTOWA DYSTRYBUCJA KLUCZA

Przykładowo, jeżeli Ania wybierze pomiar na stan |φ

i, musi wykonać

następujący ciąg operacji:

(|φ

ihφ

| ⊗ I)|xi|φ

i =

1
2

|00ih00| ⊗ I + |00ih11| ⊗ I + |11ih00| ⊗ I + |11ih11| ⊗ I

|xi|φ

√

|00ih00| ⊗ I|xi|00i + |00ih11| ⊗ I|xi|11i

+ |11ih00| ⊗ I|xi|00i + |11ih11| ⊗ I|xi|11i

W ten sposób Bartek otrzymuje stan

√

β|001i + α|000i + α|000i + β|111i

|00i|xi + |11i|xi

√

czyli stan zostanie przeniesiony do rejestru Bartka. Przykład obwodu kwan-
towego realizującego procedurę teleportacji można znaleźć w [14].

Teleportacja i gęste kodowanie są wzajemnie dopełniającymi się proce-

durami. W pierwszym przypadku korzystamy ze splątania do przenoszenia
stanów przy wykorzystaniu informacji klasycznej, natomiast w drugim wy-
korzystujemy splątanie do przesyłania informacji klasycznej.

4.3

Kwantowa dystrybucja klucza

Kwantowa dystrybucja klucza nie jest sensus stricte algorytmem kwanto-
wym. Jest to protokół wymiany danych. Jednakże można taki protokół rów-
nież traktować jako specyficzny rodzaj algorytmu przeznaczony do działania
w środowisku rozproszonym.

Wyobraźmy sobie, że istnieją dwie osoby oddalone od siebie fizycznie,

które chcą przesłać pomiędzy sobą pewną informację w postaci ciągu bi-
tów. Informacja ta jest tajna i nie powinna zostać przechwycona przez osoby
trzecie. Tradycyjnie osobę nadającą nazywamy Alicją, odbierającą Bobem,
a próbującą przechwycić informację Ewą.

Klasyczne rozwiązanie tego problemu polega wykorzystaniu któregoś z

algorytmów szyfrujących oraz klasycznego kanału informacyjnego. Wadą te-
go rozwiązania jest to, iż nie mamy pewności czy algorytmy szyfrujące na
pewno są bezpieczne. Nasza wiara w ich bezpieczeństwo wynika tylko i wy-
łącznie z przekonania iż nie wiadomo jak dokonywać szybko pewnych operacji
matematycznych jak np. faktoryzacji liczb pierwszych w algorytmie RSA.

ROZDZIAŁ 4. KWANTOWA TEORIA INFORMACJI

W roku 1984 przez Benetta i Brassaeda został opublikowany protokół,

który wykorzystuje kwantowy kanał informacyjny do dystrybucji klucza.

Aby przybliżyć to zagadnienie trzeba omówić parę właściwości mechaniki

kwantowej.

W algorytmie BB84 [10] stosuje się dwie wyróżnione bazy:

• {|0i, |1i} – zwaną kanoniczną (K),

•

|0i+|1i

√

|0i−|1i

√

– zwaną diagonalną (D), przy czym oznacza się jej wek-

tory odpowiednio przez: |+i i |−i.

Dobór takich baz nie jest oczywiście przypadkowy.

Qubity nadawane przez Alicję są jednym z czterech stanów bazowych:

|0i, |1i, |+i, |−i. A Bob dokonuje pomiaru jednej z dwóch baz: kanonicznej
lub diagonalnej. Zależność wyniku pomiaru od wysłanego stanu qubitu i bazy
w której został on dokonany przedstawia tabela 4.1.

stan baza

wynik

|0i

|1i

|+i

|−i

|0i

50%|+i 50%|−i

|0i

50%|+i 50%|−i

|0i

50%|0i 50%|1i

|0i

50%|0i 50%|1i

Tabela 4.1: Zależność wyniku pomiaru od stanu i bazy pomiaru.

Jak widać jeżeli stan nadawany nie jest wektorem bazowym, to wynik

jego pomiaru jest całkowicie losowy. Po pomiarze qubit przechodzi do sta-
nu będącego wektorem bazy, w której został zmierzony. Ważne jest również
następujące twierdzenie o nie-klonowniu (ang. no cloning theorem)

Twierdzenie 1 Nie jest możliwe skopiowanie dowolnego stanu kwantowego.

Czyli nie jesteśmy w stanie zduplikować nieznanego nam pojedynczego stanu.
Sytuacja wygląda kompletnie inaczej jeżeli mamy dużą ilość identycznych
stanów. Wtedy przez serię pomiarów możemy znaleźć pewne przybliżenie
nieznanego nam stanu. Dowód twierdzenia można znaleźć np. w [22].

Celem wykorzystania protokołu BB84 jest bezpieczna dystrybucja klucza,

rozumianego jako ciąg bitów 0 i 1, pomiędzy dwoma punktami. Dystrybucja

4.3. KWANTOWA DYSTRYBUCJA KLUCZA

klucza polega na wymianie losowego ciągu bitów, który następnie może zo-
stać wykorzystany do szyfrowania danych przesyłanych klasycznym kanałem
komunikacyjnym. Możliwe metody szyfrowania, to: dokonanie operacji XOR
bit po bicie, lub zastosowanie któregoś z symetrycznych algorytmów szy-
frujących typu DES [1]. Do realizacji protokołu BB84 wykorzystywany jest
niezabezpieczony kanał kwantowy – czyli taki, który daje możliwość prze-
syłania qubitów, oraz niezabezpieczony klasyczny kanał transmisyjny, czyli
taki którym przesyłane są informacje w postaci ciągu bitów. W szczególno-
ści kanał kwantowy może być realizowany poprzez transmisję światłowodową
lub transmisję fotonów w powietrzu. Kanał klasyczny, to dowolna sieć kom-
puterowa np:. oparta na przewodach miedzianych lub światłowodach. Kanał
niezabezpieczony, to taki do którego dostęp mogą mieć osoby trzecie i mogą
one swobodnie manipulować sygnałami, tzn je odczytywać, a nawet zmieniać.
O komunikacji przez taki kanał mówimy, że jest publiczna.

Kroki protokołu:

1. Alicja wysyła sekwencję qubitów, z których każdy jest w losowo i nie-

zależnie wybranym stanie: |0i, |1i, |+i =

|0i+|1i

√

lub |−i =

|0i−|1i

√

2. Dla każdego qubitu Bob wybiera losowo i niezależnie bazę (kanoniczną

lub diagonalną), w której będzie dokonywał pomiaru.

3. Bob zapisuje wyniki pomiarów i bazy w których zostały one dokonane.

4. Bob wysyła do Alicji klasycznym jawnym kanałem informacyjnym ba-

zy, w których został dokonany pomiar.

5. Alicja przekazuje Bobowi informację których pomiarów dokonał w do-

brej bazie.

6. Alicja i Bob dzielą dane na dwie części, względem zgodności użytych

baz. Możemy zauważyć, że średnio w połowie przypadków została użyta
zła baza. Przez złą bazę pomiaru rozumiemy taką, że dla Alicja i Bo-
ba są one różne. W takim przypadku dane muszą zostać odrzucone,
gdyż wynik pomiaru w złej bazie jest całkowicie losowy. Wynika z tego
natychmiastowy wniosek, że sprawność protokołu BB84 nie przekracza
50%. Można też zauważyć, że jeżeli nie zaistniały przekłamania i nikt
nie ingerował w proces transmisji, to pozostałe 50% qubitów zmierzo-
nych przez Boba posiada ten sam stan jaki został nadany przez Alicję.
Zatem są one kandydatami do surowego klucza.

7. Alicja i Bob wybierają pewien wspólny podzbiór qubitów spośród tych,

które zostały zmierzone w zgodnych bazach i jawnie je porównują, qubi-
ty te są oczywiście odrzucone jako, że zostały ujawnione. W przypadku

ROZDZIAŁ 4. KWANTOWA TEORIA INFORMACJI

idealnym, jeżeli nie nastąpił podsłuch informacji, to porównanie po-
winno dać całkowicie zgodne wyniki. Jednakże w rzeczywistości w wy-
niku niedoskonałości kwantowego kanału informacyjnego, porównanie
to może wykazać różnice pomiędzy stanami nadanymi przez Alicję i
zmierzonymi przez Boba. Istnieją liczne metody, które dają możliwość
eliminacji błędów transmisji w kanale kwantowym. Polegają one na wy-
mianie częściowej informacji, poprzez kanał klasyczny pomiędzy Alicją
i Bobem, o posiadanych ciągach bitów.

Najprostsze metody ataku, czyli strategie działania Ewy:

1. Ewa może wpiąć się do kwantowego kanału transmisji i przechwytywać

wszystkie qubity nadesłane przez Alicję, dokonywać na nich pomiaru i
następnie odsyłać do Boba. Taka technika podsłuchu jest bardzo łatwa
do zdemaskowania, gdyż nieznając bazy, w której zostały nadane qubity
Ewa doprowadza do zmiany stanów qubitów, co jest łatwe do wykrycia
dla Alicji i Boba po wymianie klucza.

2. Drugą techniką, jaką może zastosować Ewa jest wyłapywanie tylko nie-

których fotonów w ten sposób udając niedoskonałość kanału kwanto-
wego. Metoda ta może przynieść wydobycie pewnej ilości informacji
z transmisji, jednakże techniki zwane wzmocnieniem prywatności [2]
chronią w pewnej mierze przed takim atakiem.

3. Trzecia metoda jaką może zastosować Ewa jest wykorzystanie niedosko-

nałości nadajnika Alicji. W rzeczywistości nie mamy pewności nadania
tylko jednego qubitu, urządzenie nadające może wysłać kilka identycz-
nych stanów (w tym wypadku np. koherentnych fotonów), co może spo-
wodować, że Ewa będzie w stanie wydzielić jeden foton i go zmierzyć,
nie operując na pozostałych.

Rozdział 5

Implementacje obliczeń
kwantowych

Celem tego rozdziału jest przedstawienie wyników doświadczalnych uzyska-
nych w dziedznieie informatyki kwantowej. Zebrane są także proponopwane
modele fizycznej realizacji obliczeń kwantowych.

5.1

Jakie warunki musi spełniać komputer kwan-
towy?

Aby można przeprowadzać w układzie kwantowym obliczenia konieczne jest
spełnienie kilku warunków. Wynikają one z modelu jakim posługujemy się
do opisu algorytmów kwantowych.

a) Reprezentacja qubitu Qubit jest reprezentowany przez układ o do-

brze określonych dwóch stanach. Jednocześnie układ musi być odporny
na dekoherencję aby można było przeprowadzać obliczenia.

b) Przygotowanie stanu Oznacza to, że musimy mieć możliwość wy-

startowania z dowolnego stanu początkowego. Najczęściej jest to stan
podstawowy układu.

c) Przeprowadzanie operacji unitarnych Teoretycznie konieczna jest

jedynie możliwość wykonania operacji CNOT i operacji zmiany fazy
jednego qubitu. Te operacje stanowią zbiór zupełny dla operacji kwan-
towych.

d) Odczyt stanu końcowego Po przeprowadzeniu obliczeń (ewolucji)

musimy mieć możliwość odczytania wyników zapisanych w stanie ukła-
du. Największym problemem jaki pojawia się przy realizacji komputera

ROZDZIAŁ 5. IMPLEMENTACJE OBLICZEŃ KWANTOWYCH

kwantowego jest konieczność odizolowania go od wpływu środowiska.
Jednocześnie jednak musimy zachować możliwość kontrolowania prze-
biegu ewolucji układu.

5.2

Magnetyczny rezonans jądrowy

W ostatnim okresie szczególnie dużo uwagi w badaniach naukowych informa-
tyki kwantowej poświęcono zagadnieniom magnetycznego rezonansu jądrowe-
go, którego możliwości praktycznego zastosowania w informatyce kwantowej
są najlepiej zbadane.

Jądrowy rezonans magnetyczny (ang. NMR - Nuclear Magnetic Resonan-

ce) wykorzystuje zachowanie się cząstek kwantowych w jądrach atomowych.
Cząsteczki posiadające spin zachowują się jak zwykłe magnesy sztabkowe
i układają się wzdłuż linii sił zewnętrznego pola magnetycznego. Dwa moż-
liwe ustawienia (równoległe lub antyrównoległe) odpowiadają dwóm stanom
kwantowym tworzacym qubit. Można założyć, że spin ustawiony równole-
gle odpowiada liczbie 1, natomiast spin antyrównoległy odpowiada liczbie
0. Poszczególne spiny (równoległy oraz antyrównoległy) mają różną ener-
gie, zależną od natężenia zewnętrznego pola magnetycznego. W normalnych
warunkach to znaczy przy braku zewnętrznego pola magnetycznego taka sa-
ma liczba spinów ułożona jest w każdym kierunku. Przyłożenie pola magne-
tycznego powoduje nierównowage w ułożeniu spinów, którą można mierzyć
w eksperymencie z jądrowym rezonansem magnetycznym.

Oprócz stałego pola magnetycznego w procedurach wykorzystujących

jądrowy rezonans magnetyczny stosuje się również dodatkowo zewnętrzne
zmienne pole elektromagnetyczne. Pozwala to na planową zmiane kierunku
spinów jądrowych. Przykładając zewnętrzne oscylujące pole elektromagne-
tyczne o dokładnie ustalonej częstotliwości można zmieniać kierunek niektó-
rych spinów na przeciwny. Zatem możliwa jest sterowana zewnętrznie zmiana
kierunków wybranych spinów jądrowych. Liczba odwróconych spinów jądro-
wych zależy od częstotliwości zewnętrznego pola elektromagnetycznego. Do-
bierając odpowiednio częstotliwość zewnętrznego pola elektromagnetycznego
możliwe jest również ustawienie spinów w kierunku prostopadłym do stałe-
go pola magnetycznego. W tym przypadku oś spinu obraca się (wykonuje
precesje) wokół linii stałego pola magnetycznego z pewną charakterystyczna
częstotliwością. W trakcie trwania precesji emitowane są fale radiowe wykry-
wane przez aparaturę wykorzystującą rezonans magnetyczny.

W rzeczywistości na cząsteczki oddziaływuje nie tylko zewnętrzne pole

elektromagnetyczne lecz również pole magnetyczne wytwarzane przez inne
cząsteczki znajdujące się w najbliższym otoczeniu danej cząsteczki. Oddzia-

5.2. MAGNETYCZNY REZONANS JĄDROWY

ływanie takie umożliwia konstrukcje kwantowej bramki logicznej, podstawo-
wego elementu służącego do wykonywania obliczeń za pomocą dwóch spinów
jądrowych. Przyjmijmy, że spin jednej cząsteczki skierowany jest do góry lub
do dołu to znaczy równolegle lub antyrównolegle do kierunku stałego pola
magnetycznego, natomiast spin drugiej cząsteczki ustawiony jest zawsze do
góry czyli równolegle do kierunku stałego pola magnetycznego. Zewnętrz-
ny impuls pola elektromagnetycznego może obrócić spin drugiej cząsteczki
do płaszczyzny poziomej. Zacznie on wówczas wykonywać ruch precesyjny
wokół osi równoległej do kierunku stałego pola magnetyczego, a prędkość
obrotu zależeć będzie od tego jak ustawiony jest spin pierwszej cząsteczki
(równolegle czy antyrównolegle do kierunku stałego pola magnetycznego).
Po pewnym krótkim okresie czasu emituje się następny zewnętrzny impuls
pola elektromagnetycznego, który ustawia spin drugiej cząsteczki równole-
gle lub antyrównolegle do kierunku stałego pola magnetycznego odwrotnie
do kierunku ustawienia spinu pierwszej cząsteczki. Odpowiada to klasycznej
operacji logicznej realizowanej przez tak zwaną bramkę logiczną sterowanej
negacji zwaną również w skrócie CNOT lub XOR.

Jądrowy rezonans magnetyczny wykorzystuje zachowanie się cząstek kwan-

towych w jądrach atomowych. Cząsteczki posiadające spin zachowują się po-
dobnie jak magnesy sztabkowe i układają się wzdłuż linii sił zewnętrznego
pola magnetycznego. Dwa możliwe ustawienia (równoległe lub antyrównole-
głe) odpowiadają dwóm stanom kwantowym, tworząc w ten sposób qubit.
Można przyjąć, że spin ustawiony równolegle odpowiada liczbie 1, natomiast
spin antyrównoległy odpowiada liczbie 0. Poszczególne stany (równoległy
bądź antyrównoległy) mają różną energię, zależną od natężenia zewnętrzne-
go pola magnetycznego. W normalnych warunkach oznacza to, że przy bra-
ku zewnętrznego pola magnetycznego taka sama liczba spinów ułożona jest
w każdym kierunku. Przyłożenie pola magnetycznego powoduje nierównowa-
gę w ułożeniu spinów, którą można mierzyć w eksperymencie z jądrowym
rezonansem magnetycznym.

Oprócz stałego pola magnetycznego w procedurach wykorzystujących

jądrowy rezonans magnetyczny stosuje się również dodatkowo zewnętrzne
zmienne pole elektromagnetyczne. Pozwala to na planową zmianę kierunku
spinów jądrowych. Przykładając zewnętrzne oscylujące pole elektromagne-
tyczne o dokładnie ustalonej częstotliwości można zmieniać kierunek niektó-
rych spinów na przeciwny. Zatem możliwa jest sterowana zewnętrznie zmiana
kierunków wybranych spinów jądrowych. Liczba odwróconych spinów jądro-
wych zależy od częstotliwości zewnętrznego pola elektromagnetycznego. Do-
bierając odpowiednio częstotliwość zewnętrznego pola elektromagnetycznego
możliwe jest również ustawienie spinów w kierunku prostopadłym do stałe-
go pola magnetycznego. W tym przypadku oś spinu obraca się (wykonuje

ROZDZIAŁ 5. IMPLEMENTACJE OBLICZEŃ KWANTOWYCH

precesję) wokół linii stałego pola magnetycznego z pewną charakterystyczna
częstotliwością. W trakcie trwania precesji emitowane są fale radiowe wykry-
wane przez aparaturę wykorzystującą rezonans magnetyczny.

W rzeczywistości na cząsteczki oddziaływuje nie tylko zewnętrzne pole

elektromagnetyczne lecz również pole magnetyczne wytwarzane przez inne
cząsteczki znajdujące się w najbliższym otoczeniu danej cząsteczki. Oddzia-
ływanie takie umożliwia konstrukcję kwantowej bramki logicznej, podstawo-
wego elementu służącego do wykonywania obliczeń za pomocą dwóch spinów
jądrowych. Przyjmijmy, że spin jednej cząsteczki skierowany jest do góry lub
do dołu to znaczy równolegle lub antyrównolegle do kierunku stałego pola
magnetycznego, natomiast spin drugiej cząsteczki ustawiony jest zawsze do
góry czyli równolegle do kierunku stałego pola magnetycznego. Zewnętrz-
ny impuls pola elektromagnetycznego może obrócić spin drugiej cząsteczki
do płaszczyzny poziomej. Zacznie on wówczas wykonywać ruch precesyjny
wokół osi równoległej do kierunku stałego pola magnetyczego, a prędkość
obrotu zależeć będzie od tego jak ustawiony jest spin pierwszej cząsteczki
(równolegle czy antyrównolegle do kierunku stałego pola magnetycznego). Po
pewnym krótkim okresie czasu emituje się następny zewnętrzny impuls pola
elektromagnetycznego, który ustawia spin drugiej cząsteczki równolegle lub
antyrównolegle do kierunku stałego pola magnetycznego, odwrotnie do kie-
runku ustawienia spinu pierwszej czasteczki. Odpowiada to klasycznej ope-
racji logicznej doskonale znanej w algebrze Boole’a i realizowanej przez tak
zwaną bramkę logiczną sterowanej negacji zwaną również w skrócie CNOT
lub XOR.

5.3

Pułapkowanie jonów

Technika pułapkowania jonów opiera się na manipulacji stanami jonów uwię-
zionych w polu elektromagnetycznym.

• Ruch grupy jonów zostaje zamorzony,

• Qubity są reprezentowane przez stany (spiny) atomów i drgania łańcu-

cha jonów. Impulsy laserowe służą do konstrukcji transformacji unitar-
nych. Oddziaływanie jonów odbywa się poprzez fotony.

• Przygotowanie stanów odbywa się poprzez złapanie jonów w polu elek-

tromagnetycznym, a następnie schłodzenie ich światłem laserowym.

Zaleta tej metody jest dobrze rozwinięta technika operowania światłem

laserowym na poszczególnych jonach. Wiemy także jak odczytać odczytać
stany wewnętrzne z niemal 100% dokładnością.

5.3. PUŁAPKOWANIE JONÓW

Rysunek 5.1: Schemat układu kropek kwantowych w ciele stałym.

Pułapkowane jony sa także stosunkowo odporne na zakłócenia pocho-

dzące ze środowiska – wynika to ze struktury stanów wewnętrznych jonów.
Główna trudnością jest przygotowanie jonów w stanie podstawowym. Prze-
szkoda jest także krótki czas życia stanów wzbudzonych. Największa trudno-
ścią związaną ze skalowaniem komputera jonowego jest dobranie odpowied-
niego kształtu potencjału.

5.3.1

Budowa pułapki jonowej

Pułapka ma za zadanie przygotować jony do wykonania na nich obliczeń
kwantowych. Oddziaływując laserem na poszczególne jony możemy zmieniać
ich stan oraz, poprzez oddziaływanie, stan całego układu.

Rodzaje pułapek jonowych

1. Typu Penninga – kombinacja stałego pola elektrycznego i magnetycz-

nego.

2. Typu Paula – niejednorodne zmienne pole elektryczne. Te pułapki mogą

być wykorzystane do eksperymentów na pojedynczych jonach.

Do zastosowań obliczeniowych konieczne jest utworzenie łańcucha jonów.

Wykorzystywana jest w tym celu liniowa odmiana pułapki Paula. Nie każdy
rodzaj jonów nadaje się do realizacji komputera kwantowego. Jon powinien
mieć poziomy odpowiednie do realizacji układu dwustanowego (qubitu) i wy-
starczająco długim czasie życia.

5.3.2

Model pułapki jonowej

Kombinacja stałego i szybko zmiennego pola magnetycznego pozwala na
uwięzienie jonów. Jednocześnie oddziałują one ze sobą elektrostatycznie. Ha-
miltonian układu ma postać Aby wykonać obliczenia kwantowe układ musi
spełnic kilka warunków. Wypadku implementacji przekładaja sie one na spo-
sób w jaki oddziałujemy z układem.

ROZDZIAŁ 5. IMPLEMENTACJE OBLICZEŃ KWANTOWYCH

1. Przygotowanie układu

– Układ musi byc odpowiednio schłodzony
– Stan całosci musi byc stanem podstawowym
– Poszczególne jony musza byc w odpowiednich stanach poczatko-wych

2. Wykonywanie bramek kwantowych

– Oddziaływanie ze srodowiskiem musi byc odpowiednio małe.
– Pole elektromagnetyczne i drgania cieplne powoduja pojawienie sie
szumów, a co za tym idzie utrate informacji (zjawisko dekohe-rencji).

3. Odczyt wyników

– Odczyt uzyskujemy poprze obserwacje widma swiatła emitowa-nego
przez jony.

5.4

Kropki kwantowe

Kropką kwantową nazywamy sturkturę w półprzewodniku w której mogą być
„zamykane” nośniki ładunku. Proponowana realizacja komputera kwantowe-
go [13] polega na połączeniu takich struktur w tablicę (ang. quantum dot
array).

Kropka kwantowa jest to studnia potencjału w krysztale, ograniczają-

ca ruch swobodnego elektronu. Qubitem moze byc spin elektrony w kropce
kwantowej lub ładunek elektryczny.

Do obliczen planuje sie uzywac macierzy kropek kwantowych.

5.4.1

Działania na kropkach kwantowych

Bramki jednoqubitowe są relizowane poprzez zmiany bądź pola magnetyczne-
go, bądź parametrów w pewnych obszarach próbki. Oddziaływanie pomiędzy
kropkami może być uzyskane poprzez modyfikację bariery oddzielającej je.

5.5

Realizacje doświadczalne

1. Dotychczas udało się zrealizować przy wykorzystaniu techniki pułap-

kowania jonów jedynie pojedyńcze bramki. Do relizacji bramki CNOT
potrzeba 5 impulsów laserowych.

2. W kropkach kwantowych zaobserwowano wiele efektów które wskazują

na ich użyteczność w relizacji obliczeń kwantowych.

5.6. PODSUMOWANIE

5.6

Podsumowanie

Wydaje się osiągalna realizacja obliczeń kwantowych przy wykorzystaniu
technik kropek kwantowych. Postępująca miniaturyzacja jest bodźcem do
prowadzenia badań nad wykorzystaniem kwantowych właściwości materii
w obliczeniach klasycznych. Badania te pozwalają snuć przypuszczenia, iż
stanie się wkrótce możliwa łatwa manipulacja stanami układów mikroskopo-
wych.

Bibliografia

[1] Data Encryption Standard (DES). Technical Report FIPS PUB 46-3,

Federal Information Processing Standards Publication, 1999.

[2] Mohammed Ardehali, Gilles Brassard, H.F. Chau, and Hoi-Kwong Lo.

Eficient quantum key distribution. Technical Report HPL-98-29, HP
Laboratories Bristol, 1998.

[3] Leslie E. Ballenetiene. Quantum Mechanics. A Modern Development.

World Scientific, 1998.

[4] A. Barenco. Quantum physics and computers. Contemporary Physics,

37:375–389, 1996.

[5] A. Barenco, T. Brun, R. Schak, and T. Spiller. Effects of noise on

quantum error correction algorithms. Physical Reviews, 56:1177–1188,
1997.

[6] A. Barenco and A. Ekert. Dense coding based on quantum entanglement.

Journal Modern Optimization, 42:1253–1259, 1995.

[7] Adriano Barenco, Charles H. Bennet, Richard Cleve, David P. DiVi-

cenzo, Norman Margolus, Peter Shor, Tycho Sleator, John Smolin, and
Harald Weinfurter. Elementary gates for quantum computation. Phys.
Rev. A, 52:3457, 1995.

[8] H. Barnum, C. Fuchs, R. Jozsa, and B. Schumacher. A general fidelity

limit for quantum channels. Physical Reviews, 54:4707–4711, 1996.

[9] D. Beckman, A. Chari, S. Devabhaktuni, and John Preskill. Efficient

networks for quantum factoring. Physical Reviews, 54:1034–1063, 1996.

[10] Charles Bennett and Gilles Brassard. Quantum cryptography: Public

key distribution and coin tossing. In IEEE, editor, Proceedings of IEEE
International Conference on Computers, Systems, and Signal Proces-
sing, pages 175–179, 1984.

BIBLIOGRAFIA

[11] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory.

SIAM Journal on Computing, 26(5):1411–1473, 1997.

[12] Dagmar Bruß. Characterizing entanglement. J. Math. Phys, 43:4327,

2002.

[13] David P. DiVincenzo and D. Loss. J. Magn. Magn. Mater., 200:202,

1999.

[14] Paul Dumais and Hugo Touchette. QuCalc – Quantum Calculator, 2000.

[15] Lov K. Grover. A fast quantum mechanical algorithm for database

search. In Proceedings of the 28th ACM Symposium on Theory of Com-
putations, pages 212–219, 1996.

[16] Lov K. Grover. Quantum mechanics helps in searching for a needle in a

haystack. Phys. Rev. Lett., 79:325, 1997.

[17] Lov K. Grover. A framework for fast quantum mechanical algorithms. In

Proceedings of 30th Annual ACM Symposium on Theory of Computing
(STOC), pages 53–62, 1998.

[18] Peter Hoyer. Efficient quantum transforms. 1997.

[19] Alexei Kitaev. Quantum measurements and the abelian stabilizer pro-

blem. Electronic Colloquium on Computational Complexity (ECCC),
3(3), 1996.

[20] David K. Maslen and Daniel N. Rockmore. Generalized FFTS - A su-

rvey of some recent results. Technical Report TR96-281, Mathematics
Department, Dartmouth College, Hanover, 1996.

[21] Michele Mosca. Quantumu Computer Algorithms. PhD thesis, Univer-

sity of Oxford, 1999.

[22] M. A. Nielsen and Isaac L. Chuang. Quantum Computation and Quan-

tum information. Cambridge University Press, 2000.

[23] Markus Pueschel, Martin Roetteler, and Thomas Beth. Fast quantum

Fourier transforms for a class of non-abelian groups. 1998.

[24] Peter W. Shor. Algorithms for quantum computation: Discrete logari-

thms and factoring. In IEEE Symposium on Foundations of Computer
Science, pages 124–134, 1994.

BIBLIOGRAFIA

[25] Peter W. Shor. Polynomial-time algorithms for prime factorization and

discrete logarithms on a quantum computer. SIAM Journal of Compu-
ting, pages 1484–1509, 1997.

[26] David R. Simon. On the power of quantum computation. In Proceedings

of the 35th Annual Symposium on Foundations of Computer Science, pa-
ges 116–123, Los Alamitos, CA, 1994. Institute of Electrical and Elec-
tronic Engineers Computer Society Press.

[27] Reinhard F. Werner. Quantum states with Einstein-Rosen-Podolsky

correlations admitting a hidden-variable model. Phys. Rev. A, 40:4277–
4281, 1989.

Wyszukiwarka

Podobne podstrony:
Wykorzystanie modelu procesow w projektowaniu systemow informatycznych
OK W2 System informacyjny i informatyczny
SYSTEMY INFORMATYCZNE ORGANIZACJI WIRTUALNEJ1
Metodyka punktow wezlowych w realizacji systemu informatycznego
ZINTEGROWANE SYSTEMY INFORMATYCZNE ZARZĄDZANIA
SYSTEMY INFORMATYCZNE MIS
4 Systemy informatyczne 2 ppt
Wykład VII, politechnika infa 2 st, Projektowanie Systemów Informatycznych
Systemy informatyczne
Atrybuty uzytecznosci systemow informatycznych R R Lis
Rekord bibliograficzny, Studia INiB, Formaty danych w systemach informacyjno-wyszukiwawczych
Metodyka punktow wezlowych w realizacji systemu informatycznego, Informatyka, Studia dodać do folder
System informatyczny zarządzania, WSB Bydgoszcz, Informatyka wykłady
Opracowanie ekofizjograficzne, Studia - IŚ - materiały, Semestr 06, Systemy informacji przestrzennej
Finansowe systemy informacyjne prof Kisielnicki

więcej podobnych podstron