Kwantowe systemy informatyki
Stefan Węgrzyn, Jerzy Klamka, Jarosław A. Miszczak
25 czerwca 2003
Spis treści
1 Wprowadzenie 4
2 Podstawy matematyczne 6
2.1 Qubity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Układy złożone . . . . . . . . . . . . . . . . . . . . . . . . . . 8
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 22
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 37
4.1 Gęste kodowanie . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Teleportacja kwantowa . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Kwantowa dystrybucja klucza . . . . . . . . . . . . . . . . . . 39
5 Implementacje obliczeń kwantowych 43
5.1 Jakie warunki musi spełniać komputer kwantowy? . . . . . . . 43
5.2 Magnetyczny rezonans jądrowy . . . . . . . . . . . . . . . . . 44
5.3 Pułapkowanie jonów . . . . . . . . . . . . . . . . . . . . . . . 46
2
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
3
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 2n 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 2n 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-
4
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.
5
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 C2.
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 |0 oraz
|1 . Jeżeli utożsamimy jest z wektorami
0 1
|0 = , |1 = , (2.1)
1 0
to widać, iż tworzą one bazę ortonormalną przestrzeni C2. Tak więc dowolny
stan qubitu |� " C2 może być przedstawiony w postaci liniowej kombinacji
wektorów bazowych
|� = ą|0 + �|1 , (2.2)
gdzie liczby zespolone ą oraz � nazywane są amplitudami stanu, a wektor
|� jest znormalizowany to znaczy
|ą|2 + |�|2 = 1.
6
2.1. QUBITY
Oznacza to, że qubit |� przyjmuje wartość logiczną 0 z prawdopodobień-
stwem |ą|2 oraz wartość logiczną 1 z prawdopodobienstwem |�|2. 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 |0 oraz |1 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)
T
1
0| = 1 0 = (2.3)
0
T
0
1| = 0 1 = (2.4)
1
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 |� " C2 na wektory bazowe |0 oraz |1 .
7
ROZDZIAA
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
a1 b1
|a = , |b =
a2 b2
ich iloczyn tensorowy |a " |b zdefiniowany jest jako
�ł łł
a1b1
�ł śł
a1b2
�ł śł
|a " |b = |a = .
�ł �ł
a2b1
a2b2
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 C4 = C2 " C2. Elementami tej przestrzeni są wszystkie możliwe
superpozycje stanów kwantowych reprezentowane iloczynami tensorowymi
wektorów bazowych w C2. Ogólnie, stan układu kwantowego złożonego z n
qubitów można rozpatrywać jako element 2n-wymiarowej zespolonej prze-
n
strzeni Hilberta C2 , będącej iloczynem tensorowym n przestrzeni C2, czyli
n
C2 = C2 " C2 " . . . " C 2 .
n-razy
W ogólności przestrzeń stanów dla układu n qubitów jest rozpięta przez 2n
wzajemnie ortogonalnych stanów bazowych postaci |i , gdzie i jest n-bitową
liczbą binarną, i " {0, 1, 2, ..., 2n - 1}. Ponadto, 2n-wymiarowe wektory
�ł łł
0
�ł śł
0
�ł śł
.
�ł śł
.
.
�ł śł
�ł śł
1 �!- i-ta pozycja
�ł śł
�ł śł
|i = 0
�ł śł
�ł śł
0
�ł śł
�ł śł
.
�ł śł
.
.
�ł śł
�ł �ł
0
0
8
2.2. UKA
ADY ZA
OŻONE
n
tworzą bazę ortogonalną w C2 .
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 2n wzajemnie ortogo-
nalnych stanów postaci {|0 , |1 , |2 , . . . , |i , . . . |2n - 1 }, gdzie i jest licz-
bą naturalną przedstawioną za pomocą n-bitowego kodu binarnnego, i "
{0, 1, 2, . . . , 2n - 1}. Stosuje się również równoważny zapis wykorzystujący
bezpośrednio wagowy kod binarny liczby naturalnej
n-1
i = ak2k
k=0
to znaczy |i = |an-1, an-2, . . . , ak, . . . , a1, a0 gdzie ak, k = 0, 1, 2, . . . , n - 1
przyjmujące wartości 0 lub 1 są współczynnikami odpowiadającymi wagom
n
2k, k = 0, 1, 2, . . . , n - 1. Zatem, wektor |i " C2 posiada 1 na i + 1-pozycji,
a zera na wszystkich pozostałych. Wykorzystując iloczyn tensorowy wektor
|i można przedstawić w następującej postaci
|i = |an-1, an-2, . . . , ak, . . . , a1, a0
= |an-1 " |an-2 " . . . " |ak " . . . " |a1 " |a0 .
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 |� w przestrzeni
n
C2 , który może być przedstawiony w postaci liniowej kombinacji 2n orto-
normalnych wektorów bazowych |0 , |1 , . . . , |2n - 1 .
2n-1
|� = ąi|i , (2.5)
i=0
przy czym
2n-1
|ąi|2 = 1. (2.6)
i=0
Przykładowo, dla układu kwantowego złożonego z 2 qubitów 4 wektory
bazowe wzajemnie ortonormalne {|00 , |01 , |10 , |11 } są postaci
�ł łł
1
�ł śł
1 1 0
�ł śł
|00 = |0 " |0 = " = ,
�ł �ł
0 0 0
0
9
ROZDZIAA
2. PODSTAWY MATEMATYCZNE
�ł łł
0
�ł śł
1 0 1
�ł śł
|01 = |0 " |1 = " = ,
�ł �ł
0 1 0
0
�ł łł
0
�ł śł
0 1 0
�ł śł
|10 = |1 " |0 = " = ,
�ł �ł
1 0 1
0
�ł łł
0
�ł śł
0 0 0
�ł śł
|11 = |1 " |1 = " = .
�ł �ł
1 1 0
1
Natomiast dla układu kwantowego złożonego z 3 qubitów bazowe stany wza-
jemnie ortonormalne w 8-wymiarowej zespolonej przestrzeni C8 są postaci
następującej
{|0 , |1 , |2 , |3 , |4 , |5 , |6 , |7 } ,
lub w zapisie binarnym
{|000 , |001 , |010 , |011 , |100 , |101 , |110 , |111 } .
Przykładowo bazowy stan kwantowy |2 = |010 jest reprezentowany
w przestrzeni C8 następującym 8-wymiarowym wektorem:
�ł łł
0
�ł śł
0
�ł śł
�ł śł
1
�ł śł
�ł śł
1 0 1 0
�ł śł
|010 = |0 " |1 " |0 = " " = .
�ł śł
0 1 0 0
�ł śł
�ł śł
0
�ł śł
�ł �ł
0
0
Natomiast bazowy stan kwantowy |5 = |101 jest reprezentowany w prze-
10
2.3. BARMKI KWANTOWE
strzeni C8 następującym 8-wymiarowym wektorem:
�ł łł
0
�ł śł
0
�ł śł
�ł śł
0
�ł śł
�ł śł
0 1 0 0
�ł śł
|010 = |1 " |0 " |1 = " " = .
�ł śł
1 0 1 0
�ł śł
�ł śł
1
�ł śł
�ł �ł
0
0
W podobny sposób można przedstawić pozostałe ortonormalne wektory ba-
zowe w przestrzeni C8.
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ść
U-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
C2.
Ponadto, macierze te reprezentują w zespolonej przestrzeni C2 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ą.
11
ROZDZIAA
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:
1 0 0 1
I = , NOT = . (2.8)
0 1 1 0
Przykładowo, działanie bramki NOT dla wektorów bazowych |0 oraz |1
zdefiniowane jest w następujący sposób
NOT|0 = |1 ,
NOT|1 = |0 .
Pozwala to na znalezienie reprezentacji macierzowej bramki NOT
0 1
NOT = . (2.9)
1 0
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|� = NOT(ą|0 + �|1 )
= ąNOT|0 + �NOT|1
= ą|1 + �|0
Zatem, działanie kwantowej bramki NOT dla dowolnego znormalizowanego
stanu kwantowego |� = ą|0 + �|1 reprezentowanego wektorem o współ-
czynnikach zespolonych ą, �, można przedstawić następująco:
NOT|� = ą|1 + �|0 a" |Ź� .
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ń
-1
0 1 0 1 0 1 0 1 1 0
NOT(NOT)-1 = = = .
1 0 1 0 1 0 1 0 0 1
12
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ą
1 1
" "
1
1 1
2 2
H = " = . (2.10)
1 1
"
1 -1 -"2
2
2
Działanie bramki Hadamarda H dla wektorów bazowych |0 oraz |1 moż-
na przedstawić następująco:
1
"
H|0 = (|0 + |1 )
2
1
"
H|1 = (|0 - |0 )
2
Wektory {H|0 , H|1 } 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 C4 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 0
�ł śł
0 1 0 0
�ł śł
UD = , (2.11)
�ł
0 0 u11 u12 �ł
0 0 u21 u22
gdzie
u11 u12
D = (2.12)
u21 u22
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 |0 czy też w stanie kwantowym
13
ROZDZIAA
2. PODSTAWY MATEMATYCZNE
|1 . W przypadku, gdy pierwszy qubit jest w stanie |0 , wówczas drugi qubit
pozostaje bez zmian, natomiast gdy pierwszy qubit jest w stanie |1 , 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.
�ł łł
1 0 0 0
�ł śł
0 1 0 0
�ł śł
CNOT = . (2.13)
�ł �ł
0 0 0 1
0 0 1 0
Przykładowo, działanie 2-qubitowej bramki kwantowej CNOT na wektory
bazowe przestrzeni C4 można przedstawić następująco:
CNOT|00 = |00 ,
CNOT|01 = |01 ,
CNOT|10 = |11 ,
CNOT|11 = |10 .
W przypadku ogólnym działanie bramki CNOT na stan układu dwuqu-
bitowego jest dane jako
CNOT|� = CNOT (ą|00 + �|01 + ł|10 + �|11 )
�ł �ł łł �ł łł �ł łł �ł łł�ł
1 0 0 0
�ł �ł śł �ł śł �ł śł �ł śł�ł
0 1 0 0
�łą �ł śł �ł śł �ł śł �ł śł�ł
= CNOT + � + ł + �
�ł �ł �ł �ł �ł �ł �ł �ł �łłł
0 0 1 0
0 0 0 1
�ł łł �ł łł �ł łł �ł łł
1 0 0 0
�ł śł �ł śł �ł śł �ł śł
0 1 0 0
�ł śł �ł śł �ł śł �ł śł
= ą + � + � + ł
�ł �ł �ł �ł �ł �ł �ł �ł
0 0 1 0
0 0 0 1
= ą|00 + �|01 + �|10 + ł|11 .
14
2.4. BRAMKI WIELOQUBITOWE
Proste obliczenia pokazują że bramka CNOT jest odwracalna.
�ł łł �ł łł-1
1 0 0 0 1 0 0 0
�ł śł �ł śł
0 1 0 0 0 1 0 0
�ł śł �ł śł
CNOT CNOT-1 =
�ł �ł �ł �ł
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0
�ł łł �ł łł
1 0 0 0 1 0 0 0
�ł śł �ł śł
0 1 0 0 0 1 0 0
�ł śł �ł śł
=
�ł �ł �ł �ł
0 0 0 1 0 0 0 1
0 0 1 0 0 0 1 0
�ł łł
1 0 0 0
�ł śł
0 1 0 0
�ł śł
= = I.
�ł �ł
0 0 1 0
0 0 0 1
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 2n � 2n-wymiarowe. Ma-
cierze te zatem zawierają tyle wierszy oraz tyle kolumn ile jest wzajemnie
ortogonalnych wektorów bazowych w 2n-wymiarowej zespolonej przestrzeni
n
C2 .
Należy wyraz
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 2n � 2n-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ą
15
ROZDZIAA
2. PODSTAWY MATEMATYCZNE
macierzą
�ł łł
1 0 . . . 0 0 0
�ł śł
0 1 . . . 0 0 0
�ł śł
�ł śł
. . . . .
.
. . . . . .
�ł śł
.
. . . . .
�n (NOT) = . (2.14)
�ł śł
�ł śł
0 0 . . . 1 0 0
�ł śł
�ł �ł
0 0 . . . 0 0 1
0 0 . . . 0 1 0
Niech x1, x2, . . . , xk, . . . , xn oznacza n wejść natomiast y1, y2, . . . , yk, . . . , yn
odpowiednio n wyjść bramki Toffoliego. Wówczas
yk = xk dla k = 1, 2, . . . , n - 1, (2.15)
yn = (x1 '" x2 '" . . . '" xk '" . . . '" xn-1) �" xn. (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 x1 �" x2 zwaną inaczej
kontrolowaną negacją CNOT lub bramką kwantową XOR.
W przypadku gdy xn = 1, wówczas wyjście yn zachowuje się jak klasycz-
ny funktor logiczny NAND. Natomiast w przypadku gdy xn = 0, wówczas
wyjście yn 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 �n (NOT) jest kwantowa bramka ozna-
czona symbolem �n (U), której działanie reprezentuje 2n � 2n-wymiarowa
macierz unitarna
�ł łł
1 0 . . . 0 0 0
�ł śł
0 1 . . . 0 0 0
�ł śł
�ł śł
. . . . .
.
. . . . . .
�ł śł
.
. . . . .
�n (U) = , (2.17)
�ł śł
�ł śł
0 0 . . . 1 0 0
�ł śł
�ł
0 0 . . . 0 u11 u12 �ł
0 0 . . . 0 u21 u22
gdzie
u11 u12
U = (2.18)
u21 u22
reprezentującą wybraną kwantową bramkę logiczną dla jednego qubitu.
16
2.4. BRAMKI WIELOQUBITOWE
Przykładowo, mogą to być macierze następującej postaci:
eiĄ/4 cos(Ą/8) eiĄ/4 sin(Ą/8)
F = ,
-e-iĄ/4 sin(Ą/8) e-iĄ/4 cos(Ą/8)
cos(Ą/8) - sin(Ą/8)
G = ,
sin(Ą/8) cos(Ą/8)
e-iĄ/4 0
H = ,
0 eiĄ/4
1 0
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
C2. Zatem reprezentują one działanie jednoqubitowe. Ogólnie, dowolny obrót
(rotacja) w przestrzeni C2 może być przedstawiona za pomocą następującej
2 � 2-wymiarowej macierzy unitarnej:
cos(�/2) -ie-iĆ sin(�/2)
V (�, Ć) = . (2.19)
-ieiĆ sin(�/2) cos(�/2)
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ż �n (U)-1 = �n (U)T 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 �n (H) reprezentowanej 4 � 4-
wymiarową macierzą unitarną postaci:
�ł łł
1 0 0 0
�ł śł
0 1 0 0
�ł śł
�n (H) = UH = (2.20)
1 1
" "
�ł �ł
0 0
2 2
1 1
"
0 0 -"2
2
Załóżmy, że stan |� jest superpozycją stanów kwantowych |2 = |10
17
ROZDZIAA
2. PODSTAWY MATEMATYCZNE
oraz |3 = |11 .
1 1
" "
|� = (|2 + |3 ) = (|10 + |11 )
2 2
1
0 1 0 0
= " " + "
1 0 1 1
2
�ł�ł łł �ł łł�ł �ł łł
0 0 0
�ł�ł śł �ł śł�ł �ł śł
1 1
0 0 0
�ł�ł śł �ł śł�ł �ł śł
= " + = " .
�ł�ł �ł �ł �łłł �ł �ł
1 0 1
2 2
0 1 1
Działanie bramki UH na stan |� odpowiada wykonaniu mnożenia
�ł łł �ł łł �ł łł
1 0 0 0
0 0
�ł śł �ł śł �ł śł
0 1 0 0
1
0 0
�ł śł �ł śł �ł śł
UH|� = " = = |10
1 1
" "
�ł �ł �ł �ł �ł �ł
0 0
1 1
2
2 2
1 1
"
0 0 -"2 1 0
2
1
"
Analogicznie dla stanu |Ć = (|10 - |11 ) możemy zapisać
2
�ł łł
0
�ł śł
1 1
0 1 0 0 0
�ł śł
|Ć = " " - " = " ,
�ł �ł
1 0 1 1 1
2 2
-1
działanie bramki UH odpowiada wykonaniu mnożenia
�ł łł �ł łł �ł łł
1 0 0 0
0 0
�ł śł �ł śł �ł śł
0 1 0 0
1
0 0
�ł śł �ł śł �ł śł
UH|Ć = " = = |11 .
1 1
" "
�ł �ł �ł �ł �ł �ł
0 0
1 1
2
2 2
1 1
"
0 0 -"2 -1 0
2
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ż
18
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 wyraz
nie zaznaczyć, że pojęcie splątanie nie występuje w standardowej
algebrze Boole a.
n
Splątanie oznacza zatem, że dany stan kwantowy |� " C2 nie może
być przedstawiony jednoznacznie w postaci iloczynu tensorowego n stanów
kwantowych |�i " C2, i = 1, 2, . . . , n. Oznacza to, że między poszczególnymi
stanami kwantowymi |�i istnieją wzajemne korelacje. Przykładowo, niech
1 1
" "
|� = (|1 - |2 ) = (|01 - |10 ). (2.21)
2 2
Wektor ten reprezentuje stan kwantowy będący wynikiem zawikłania,
gdyż nie można znalez
ć dwóch stanów kwantowych |�1 oraz |�2 s takich, że
|� = |�1 " |�2 .
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:
1
"
|�+ = (|0 " |1 + |1 " |0 ) (2.22)
2
1
"
|�- = (|0 " |1 - |1 " |0 ) (2.23)
2
1
"
|Ć+ = (|0 " |0 + |1 " |1 ) (2.24)
2
1
"
|Ć- = (|0 " |0 - |1 " |1 ) (2.25)
2
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.
19
ROZDZIAA
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 �1(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
�1 (Uk), k = 1, 2, 3, 4 z odpowiednio dobranymi macierzami unitarnymi Uk,
oraz dwie 2-qubitowe bramki kwantowe �2 (CNOT).
Podobnie dla dowolnej macierzy unitarnej U, działanie bramki kwanto-
wej �3(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 �1 (Uk), k = 1, 2, . . . , 8, z odpowied-
nio dobranymi macierzami unitarnymi Uk, oraz osiem 2-bitowych bramek
kwantowych �2 (CNOT).
W ogólnym przypadku, dla dowolnej macierzy unitarnej U, działanie
bramki kwantowej �n (U) może być symulowane za pomocą układu zawiera-
jącego co najwyżej 2n-1 bramek kwantowych typu �2 (Uk), k = 1, 2, . . . , 2n-
1 z odpowiednio dobranymi macierzami unitarnymi Uk, oraz 2n - 2 bramek
kwantowych typu �2 (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 e" 5 oraz m " {3, ..., [n/2]}, (gdzie symbol [n/2] oznacza część cał-
kowitą liczby rzeczywistej n/2), działanie bramki kwantowej �m (CNOT)
20
2.6. UKA
ADY BRAMEK KWANTOWYCH
może być symulowane za pomocą układu zawierającego 4(m - 2) bra-
mek kwantowych typu �3 (CNOT).
2. Dla n e" 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 �m (CNOT) oraz dwie bramki kwantowe typu �n-m-1 (CNOT).
3. Dla m e" 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 �3 (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 wyraz
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.
21
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 {di, i = 1, 2, . . . , N} zawierającym N
22
3.1. ALGORYTM GROVERA
elementów określonego elementu dj = 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ą
|i jeżeli i = j,
U|i = (3.1)
-|i jeżeli i = j.

gdzie j jest indeksem poszukiwanego elementu.
Zatem wraz ze wzrostem liczby wykonanych iteracji k wzrasta również
amplituda stanu kwantowego av(k), i uzyskuje ona swoje maksimum dla licz-
1
by iteracji odpowiadającej w przyblizeniu wartości kmax H" Ą2L/2.
4
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 = 1016 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,
23
ROZDZIAA
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ę HN = H"N
H"N = H " H " . . . " H
N razy
na stanie |0 . . . 0
N-1
1
H"N|0 . . . 0 = " |i (3.2)
N
i=0
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 |x0
xx0
Ix |x = -(-1)� |x (3.3)
0
gdzie
1 x = x0
�xx = . (3.4)
0
0 x = x0

2. Wykonanie bramki -H"n
3. Obrót fazy dla wszystkich stanów z wyjątkiem |0 . . . 0
x0
I0|x = S - (-1)� |x (3.5)
gdzie
1 x = 0 . . . 0
�x0 = . (3.6)
0 x = 0 . . . 0

4. Drugie wykonanie bramki Hadamarda H"n
Zatem operator Grovera jest używany do manipulacji amplitudą. Ze wzglę-
du na tożsamość
-|x x = 0 . . . 0
x0
G2|x = -(-1)� |x = (3.7)
|x x = 0 . . . 0

24
3.1. ALGORYTM GROVERA
and
2|x - |x x = 0 . . . 0
(2|0 . . . 0 0 . . . 0| - I)|x = (3.8)
|x x = 0 . . . 0

-|x x = 0 . . . 0
= (3.9)
|x x = 0 . . . 0

operacja G2 może być zapisany jako G2 = 2|0 . . . 0 0 . . . 0| - 1
Operacje 2-4 stanowią elementy operatora nazywanego operatorem dyfuzji
lub operatorem obrotu wokół średniej. Zastosowanie operatora Grovera do
ogólnego stanu |ą = ąn|n daje stan
n
2
D ąn|n = ąn -|n + |y = (-ąn + 2s) |n , (3.10)
N
n n y n
gdzie
1
s = ąi (3.11)
N
i
to średnia arytmetyczna współczynników ąi, 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.
25
ROZDZIAA
3. ALGORYTMY KWANTOWE
Po wykonaniu pierwszej iteracji amplituda ay stanu |y będzie nieco więk-
sza niż amplitudy ax 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:
|� = ąx + ąy|y (3.12)
x =y
Zatem w miarę wykonywania kolejnych iteracji amplituda ąy stanu kwan-
towego |y coraz bardziej różni się od amplitud ax pozostałych stanów kwan-
towych |x . Przeprowadzając odpowiednie obliczenia można wykazać, że po
wykonaniu k-tej iteracji algorytmu amplituda stanu kwantowego wynosi
ąy(k) = sin((2k + 1)j), gdzie sin2(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 kmax = 1/4Ą2n/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
26
3.2. ALGORYTMY SHORA
Rysunek 3.2: Reprezentacja gometryczna algorytmu Grovera dla zbioru 8
elementów reprezentowanych przez trzy qubity
27
ROZDZIAA
3. ALGORYTMY KWANTOWE
|0
H H
|1
H
Algorytm Deutscha
|0n
H"n H"n
|0m
Algorytm Simona
|0 . . . 0 QF T QF T
|0 . . . 0
Algorytm Shora
Rysunek 3.3: Sieci bramek kwantowych dla algorytmów ukrytej podgrupy.
28
|
x, y
|
x, f
(
x
)
�"
y
|
x, y
|
x, f
(
x
)
�"
y
x
|
x,
0
|
x, a
mod
N
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 (ZN, �) nazywamy najmniejszą liczbę całko-
witą r spełniającą warunek
ar = 1 mod N.
Liczbę r oznaczamy pisząc r = ordN(a). Stosując zapis symboliczny
r = ordN(a) = min {x " Z|mx = 1 mod N}
Jeżeli liczba a jest względnie pierwsza z N to ordN(a) istnieje. W przeciwnym
wypadku gcd(a, N) = 1 więc am - 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ę fa(x) := ax( mod N), przy założeniu gcd(a, N) = 1.
Zgodnie z definicją rzędu
fa(x + r) = ax+r( mod N) = axar( mod N) = ax( mod N) = fa(x),
co oznacza, że r = ordN(a) jest okresem funkcji fa. 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, znajdz
okres funkcji fa : Z ZN
określonej wzorem fa(x) = ax( 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 fa do
pewnego skończonego podzbioru Zq �" Z i na nim badać okresowość funkcji
fa|Z .
q
Przestrzeń Hilberta komputera kwantowego, na którym ma się odbywać
algorytm znajdowania okresu, można przedstawić w postaci H1 " H2, przy
czym pierwsza podprzestrzeń odpowiada rejestrowi, w którym przechowy-
wane są argumenty funkcji fa, a druga  rejestrowi zawierającemu wartości.
Rejestry te  a co za tym idzie wymiary q = dim H1 oraz d = dim H1 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 ZN. Mówiąc precyzyjnie, zastępujemy zagadnienie znalezienia dzielników
29
ROZDZIAA
3. ALGORYTMY KWANTOWE
liczby N, zagadnieniem następującym Mając daną liczbę N oraz liczbę a,
względnie pierwszą z N, znajdz
rząd ordN(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 ordN(a).
Okres funkcji f(x) = ax( mod N) jest rzędem elementu a.
f(x + r) = ax+r( mod N) = axar( mod N) = ax( 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ę Zq
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 Zq wykonując transformatę
Fouriera
q-1
1
|x |0 (3.15)
"
q
k=0
2. Umieść wartość funkcji f(x) = ax( mod N) w drugim rejestrze
q-1
1
|x |f(k) (3.16)
"
q
k=0
3. Wykonaj drugi raz transformatę Fouriera
q-1 q-1
1 2iĄkl
exp |l |f(k) . (3.17)
"
q q
k=0 l=0
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].
30
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 znalez
ć w pracach [23, 20].
W skończeniewymiarowej przestrzeni Hilberta H odpowiadającej ukła-
dowi wybieramy bazę ortonormalną {|g |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 |� ma rozkład w bazie {|g |g " G}
|G|
|� = ci|gi (3.18)
i=1
W zbiorze odwzorowań liniowych {f : G C} definiujemy iloczyn ska-
larny
f1|f2 := f1(g)f2(g) (3.19)
g"G
Współczynniki rozkładu 3.18 mogą być potraktowane jako wartości pew-
nej funkcji f : G C określonej wzorem
f(gi) = ci (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
|G|-1
2iĄgj gk
1
Ć |G|
f(gj) = e f(gk). (3.22)
|G|
k=0
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 |j " H w d-wymiarowej
przestrzeni wektorowej, określone jest wzorem
d-1
2iĄjk
1
d
QFT|j = " e |k (3.23)
d
k=0
31
ROZDZIAA
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ę {|0 , |1 }.
Transformata Fouriera na B jest określona jako odwzorowanie
1
Ć
"
f(x) = (-1)0�xf(0) + (-1)1�xf(1)
2
1
"
= f(0) + (-1)xf(1)
2
Odpowienio kwantowa transformata Fouriera działa na stany bazowe zgod-
nie ze wzorem
1
"
QF T2|x = (-1)0�x|0 + (-1)1�x|1
2
1
"
= |0 ) + (-1)x|1
2
i jest reprezentowana przez macierz unitarną H
1
1 1
H = " (3.25)
1 -1
2
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.
32
3.3. KWANTOWA TRANSFORMATA FOURIERA
Pierwszym krokiem jest wykonanie kilku prostych przekształceń. Niech j
będzie liczbą n-bitową, reprezentowaną przez stan bazowy |j " H. W postaci
dwójkowej liczbę tę można zapisać jako
n
j = jk2n-k, (3.26)
k=1
gdzie jn " {0, 1} oznacza n-ty bit liczby j.
Wychodząc ze wzoru 3.23 możemy zapisać
2n-1
2iĄjk
1
2n
QFT|j = " e |k
2n k=0
1 1
n
2iĄj( kl2l)
1
l=1
2n
= " . . . e |k1 . . . kn
2n k1=0 kn=0
1 1 n
2iĄjkl2l
1
2n
= " . . . e |k1 . . . kn .
2n k1=0 kn=0 l=1
Otrzymany stan nie jest stanem splątanym. Można go zapisać w postaci
iloczynu tensorowego odpowiednich superpozycji stanów bazowych.
n 1
1
l
QFT|j = " e2iĄjk 2-l|kl
2n l=1 kl=0
n
1 -l
= " |0 + e2iĄj2 |1
2n l=1
Oznaczając przez 0.jl . . . jm ułamek binarny o wartości
m
jk
(3.27)
2k-l+1
k=l
ostatecznie zapisujemy stan QF T |j jako
n n-1 1
(|0 + e2iĄ0.j |1 )(|0 + e2iĄ0.j jn|1 ) . . . (|0 + e2iĄ0.j ...jn|1 )
" (3.28)
2n
Dla przypadku trzech qubitów i j = 4j1 + 2j2 + j3 można ostatni krok po-
33
ROZDZIAA
3. ALGORYTMY KWANTOWE
wyższego wyprowadzenia rozpisać bezpośrednio
(|0 + e2iĄj/2|1 )(|0 + e2iĄj/4|1 )(|0 + e2iĄj/8|1 )
QF T |j = "
8
1 1 1
(|0 + e2iĄ(2j +j2+j3/2)|1 )(|0 + e2iĄ(j +j2/2+j3/4)|1 )(|0 + e2iĄ(j /2+j2/4+j3/8)|1 )
= "
8
3 2 1
(|0 + e2iĄ0.j |1 )(|0 + e2iĄ0.j j3|1 )(|0 + e2iĄ0.j j2j3|1 )
= "
8
gdzie wykorzystana została okresowość funkcji ex.
Na Rysunku 3.4 przedstawiony jest układ realizujący kwantową transfor-
matę Fouriera dla układu trzech qubitów.
F (4) F (8)
H
F (4)
H
H
Rysunek 3.4: Transformata Fouriera dla trzech qubitów.
Bramka F (n) jest zdefiniowana dla n " N jako operacja
1 0
F (n) = 2iĄ . (3.29)
n
0 e
W tym wypadku mamy
1 0
1 0
F (4) = , F (8) = Ąi . (3.30)
0 i 4
0 e
Ponieważ e2iĄ = -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-
n
go  jednokrotnie. Zamiana kolejności qubitów wymaga bramek SWAP.
2
34
3.4. INNE ALGORYTMY KWANTOWE
(n+1)n
A
ącznie, musimy wykonać bramek, co oznacza, iż algorytm QFT ma
2
złożoność O(n2), 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ą znalez
ć 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) = ax mod N.
" Ukryta funkcja liniowa
Dla funkcji f(x, y) = x + ay określonej na (Z � Z, +) o wartościach
w ZN i permutacji Ą : ZN ZN określmy
h = Ą ć% f
W tym wypadku ukryta podgrupa ma posać:
{(-ta, t)|t = 1, . . . , N - 1} .
" Rząd permutacji
Dla G = (Z2n � Z2n, �") i funkcji f : G Z2n określonej jako
f(x, y) = Ąx(y)
35
ROZDZIAA
3. ALGORYTMY KWANTOWE
gdzie Ą jest permutacją zbioru Z2n. Szukamy ukrytej podgrupy
{r " Z2n|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ń
(ab)(x) = a(b(x))
a,b"G x"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 StG(x). Oznaczmy przez fx odwzorowanie przeprowadza-
jące element grupy G w wartość tego elementu na x , fx(g) = g(x).
Odwzorowaniu temu odpowiada ukryta podgrupa StG(x). Stabilizator
StG(x) jest ukryta podgrupą dla odwzorowania fx : G X określonego
jako
fx(g) = g(x) g " G
W pracy [19] został podany sposób znalezienia StG(x) dla przypadku
grup albelowych. Zadanie to zawiera jako przypadki szczególne zadania
faktoryzacji i obliczania logarytmów dyskretnych.
36
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 |Ć+ . Ania
może wykonać na swoim podukładzie jedną z operacji unitarnych reprezen-
towanych przez macierze Pauliego
1 0
1. I = ,
0 1
0 1
2. �x = ,
1 0
0 -i
3. �y = ,
i 0
1 0
4. �z = .
0 -1
Odpowiada to odpowiednio przejściu w jeden ze stanów:
37
ROZDZIAA
4. KWANTOWA TEORIA INFORMACJI
1. |Ć+ = I " I|Ć+ ,
2. |�+ = �x " I|Ć+ ,
3. |�- = �y " I|Ć+ ,
4. |Ć- = �z " I|Ć+ .
Jeżeli teraz Bartek dokona pomiaru stanu całości w bazie {|Ćą , |�ą } 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 |x , o ile dysponujemy kanałem kwantowym.
Załóżmy, że Ania i Bartek mają do dyspozycji stan splątany |Ć+ . Aby
przesłać dokładną kopię stanu |x = ą|0 + �|1 Ania musi wykonać nastę-
pujące kroki:
1. Utworzyć układ w stanie |x |Ć+ .
2. Dokonać pomiaru stany podukładu dwóch pierwszych qubitów w bazie
{|Ćą , |�ą }.
3. Przesłać do Bartka kanałem klasycznym dwa bity opisujące jej pomiar
poprzez numer wektora bazowego.
Z kolei Bartek, aby odtworzyć stan |x , wykonuje następującą operację
na swoim podukładzie, w zależności od otrzymanej wiadomości klasycznej:
1. |Ć+ I,
2. |�+ �x,
3. |�- �y,
4. |Ć- �z.
38
4.3. KWANTOWA DYSTRYBUCJA KLUCZA
Przykładowo, jeżeli Ania wybierze pomiar na stan |Ć+ , musi wykonać
następujący ciąg operacji:
(|Ć+ Ć+| " I)|x |Ć+ =
1
= |00 00| " I + |00 11| " I + |11 00| " I + |11 11| " I |x |Ć+
2
1
= " |00 00| " I|x |00 + |00 11| " I|x |11
2 2
+ |11 00| " I|x |00 + |11 11| " I|x |11
W ten sposób Bartek otrzymuje stan
1
" �|001 + ą|000 + ą|000 + �|111 =
2 2
|00 |x + |11 |x
"
2 2
czyli stan zostanie przeniesiony do rejestru Bartka. Przykład obwodu kwan-
towego realizującego procedurę teleportacji można znalez
ć 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.
Wyobraz
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.
39
ROZDZIAA
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:
" {|0 , |1 }  zwaną kanoniczną (K),
|0 " |0 "
+|1 -|1
" ,  zwaną diagonalną (D), przy czym oznacza się jej wek-
2 2
tory odpowiednio przez: |+ i |- .
Dobór takich baz nie jest oczywiście przypadkowy.
Qubity nadawane przez Alicję są jednym z czterech stanów bazowych:
|0 , |1 , |+ , |- . 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
|0 K |0
|1 K |1
|+ D |+
|- D |-
|0 D 50%|+ 50%|-
|0 D 50%|+ 50%|-
|0 K 50%|0 50%|1
|0 K 50%|0 50%|1
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 znalez
ć pewne przybliżenie
nieznanego nam stanu. Dowód twierdzenia można znalez
ć 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
40
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-
|0 " |0 "
+|1 -|1
zależnie wybranym stanie: |0 , |1 , |+ = lub |- = .
2 2
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
41
ROZDZIAA
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.
42
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
43
ROZDZIAA
5. IMPLEMENTACJE OBLICZEC
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-
44
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ądz
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
45
ROZDZIAA
5. IMPLEMENTACJE OBLICZEC
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ą.
46
5.3. PUA
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.
47
ROZDZIAA
5. IMPLEMENTACJE OBLICZEC
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ądz
pola magnetyczne-
go, bądz
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.
48
5.6. PODSUMOWANIE
5.6 Podsumowanie
Wydaje się osiągalna realizacja obliczeń kwantowych przy wykorzystaniu
technik kropek kwantowych. Postępująca miniaturyzacja jest bodz
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.
49
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.
50
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.
51
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.
52