Algorytmy kwantowe [PDF]

Zitiervorschau

•

Mika Hirvensalo

Algorytmy kwantowe

•

Spis

treści

Przedmowa do wydania polskiego

6

Przedmowa do drugiego wydania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

Z przedmowy do pierwszego wydania . . . • . . . • • • . . . . . • . . . . . . . . . . .

1O

1.

Wstę p

.................. ................ ...... ...... . •

1.1. Krótka histori a obliczeń kwantowych . . • • • • • • 1.2. Fizyka klasyczna . . . . . . . . . . . . . . . . . . . • • • • • 1.3. Układy probabilistyczne . . . . . . • • • • . . • • • • . . 1.4. Mechanika kwantowa . . . . . . . . • • • . . • • • . . .

.••••••. . .•••. •••• .•. . . •••. .••••....

..• .•• .•• .•.

. . . .

13 13 14 16 18

2. Infor macja kwa ntowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.1. 2.2. 2.3. 2.4. 2.5. 2.6. 2.7.

Bity kwantowe . . . . . . . . . . . Rejestry kwantowe . . . . . . . . Twierdzenie o nieklonowaniu Obserwacja . . . . . . . . . . . . . Teleportacja kwant owa . . . . . Kodowanie su pergęste . . . . . Za dania . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

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

. . . . . . .

. . . . . . .

... . •. ... ... .. . ... ...

.... ... ....... ..... .. ...... . .•..... .. .. ... .......

....... ... .... ....•.. ....... ...••.. ..... .. .. . •. . .

. . . . . . .

24 28 32 34 36 40 41

„

3. Maszyny obliczeniowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.1. Obliczenia jednostajne . . . . . . . . . . . . . . . . . . . . . . . . . . . • • . 3.1.1. Maszyny Turinga . . . . . . . . . . . . . . . . . . . . . . . . . . • • . 3.1.2. Probabilistyczne maszyny Turinga . . . . . . . . . . . . . . . . . 3.1.3. Wielotaśmowe maszyny Turinga . . . . . . . . . . . . . . . . . 3.1.4. Kwantowe maszyny Turinga ............... ~ . . . . . 3.2. Obwody . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 . Obwody logiczne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2. Obwody odwracalne . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3. Obwody kwantowe . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

42 42 45 50 51 55 55 57 60

4. Szybka fa ktoryzacj a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.1 . Kwantowa t ransformata Fouri era . . . . . . . . . 4.1.1 . Podstawy . . . . . . . . . . . . . . . . . . . . . . 4.1.2. Transformat a Hadamarda-Walsha . . . . 4.1.3. Kwantowa transformata Fouriera w Zn 4.1.4. Uwagi o złożoności . . . . . . . . . . . . . . 4.2. Algorytm faktoryzacji Shora . . . . . . . . . . . . . 4.2.1. Od okresowości do faktoryzacji . . . . . 4.2.2. Rzędy elementów w Zn . . . . . . . . . . . 4.2.3. Znajdowanie okresu . . . . . . . . . . . . . .

....... ...... .. ............... . . .. . . . . . . . •. . .

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

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

63 63 65 67 71 73 73 75 78

3

4.3.

Prawdopodobieństwo poprawności

. ... . .. .. . . 4.3.1. Przypadek łatwy . . . . . .... . .... . . . .... 4.3.2. Przypadek ogólny . . . . . . . . . . . . . . . . . . . . 4.3.3. Złożoność algorytmu faktoryzacji Shora . . . 4.4. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .

. '. . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

81 81 82 87 88

5. Znajdowanie ukrytej podgru py . . . . . . . . . . . . . . . . . . . . . . . 89 5.1. Uogólniony algorytm Simona . . . . 5.1.1. Wiadomości wstępne . . . . . 5.1.2. Algorytmy . . . . . . . . . . . . . 5.2. Przykłady . . . . . . . . . . . . . . . . . . . 5.2 .1. Znaj dowanie rzędu . . . . . . . 5.2.2. Logarytm dyskretny . . . . . . 5.2.3. Oryginalny problem Simona 5.3. Zadania . . . . . . . . . . . . . . . . . . . .

. . . . . . . .

6. Algoryt m wyszukiwa nia Grovera

. . . . . . . .

. . . . . . . .

. . . . . . . .

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

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

•. .. .. .. •. .. .. ..

. . . . . . . .

. . . . . . . .

... ... ... ... .•. .•. ... .•.

. . . . . . . .

. . . . . . . .

.. . ... ... ... .•. ... .•. ...

. . . . . . . .

90 90 91 96 96 96 97 98

. . . . . . . . . . . . . . . . . . . . 99

6.1. Problemy wyszukiwania . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.1.1. Problem spełnia l ności . . . . . . . . . . . . . . . . . . . . • . . . . 6.1.2. Wyszukiwanie probabilistyczne . . . . . . . . . . . . . . . . . . 6.1.3. Wyszukiwanie kwantowe z jednym sprawdzeniem . . . 6.2. Metoda wzmacniania Grovera . . . . . . . . . . . . . . . . . . . . . . . 6.2.1. Operatory kwantowe dla algorytmu wyszukiwania Grovera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2.2. Wzmacnianie amplitudy . . . . . . . . . . . . . . . . . . . . . . . 6.2.3. Analiza met ody wzmacniania . . . . . . . . . . • . . . . . . . . 6.3. Zastosowania metody wyszukiwania Grovera . . . . . . . . . . . . 6.3.1. Wyszukiwanie w przypadku nieznanej liczby rozwiązań

. . . . .

. . . . .

. 99 . 99 . 1OO . 102 . 106

. . . .

. . . .

. . . .

106 107 111 116 116

7. Dolne ogran iczenia na złożoność dla obwodów kwantowych . . .... . . . . .. . . . .. . . . .. . . . . 120 7 .1. Zarys metody . . . . . . . . . . . . . . . . . . . . . . • . . 7. 2. Reprezentacje wielomianowe . . . . . . . . . . . . . 7.2.1. Wiadomości wstępne . . . . . . . . . . . . . . 7.2.2. Ograniczenia na stopień reprezentacji . . 7 .3. Dolne ograniczenie dla obwodów kwantowych 7.3 .1. Ogólne dolne ograniczenie . . . . . . . . . . 7.3.2. Przykłady .. . . . .. . . . . . .. . . . . . .. . .

..•.. ..... ..... ..... ..... ..... . ....

. . . . . . .

.... .... .... .... .•.. .. . . . . ..

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

120 121 121 125 128 128 131

8. Dodat ek A. Fizyka kwantowa . . . . . . .. . . . .. . . . . . .. . . .. 133 8.1. Krótka historia teorii kwantów . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2. Matematyczna struktura teorii kwantowej . . . . . . . . . . . . . . . . . 8.2.1. Przestrzenie Hilberta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.2.2. Operatory . . .... . . . .... . . . ... . . .......... . . ... 8.2.3. Reprezentacja spektralna operatorów samosprzężonych . . 8.2.4. Reprezentacja spektralna operatorów unitarnych . . . . . . .

4

133 135 137 138 143 146

8.3. Stany kwantowe jako wektory z przestrzeni Hilberta . . . . . . . . . . 8.3.1. Kwantowa ewolucja czasowa . . . . . . . . . . . . . . . .. . . . . . . 8.3.2. Obserwable . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.3.3. Zasada nieoznaczoności . . . • • • • • • . . . . . • • . . . . . . . . . . 8.4. Stany kwantowe jako operatory . . . • • • • . . . . . . . . . . . . . . . . . . 8.4.1. Macierze gęstości ... ........ ••• .... .. .. : ... .. . . : 8.4.2. Obserwable i stany mieszane . . • • . . . . . . . . . . . . . . . . . . 8.4.3. Stany podukładów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8.4.4. Wi ęcej o ewolucji czasowej . . . . . . . . . . . . . . . . . . . . . . . . 8.4.5. Twierdzenia o reprezentacji . . . . . . . . . . . . . . . . . . . . . . . 8.4.6. Twierdzenie Jozsy o klonowaniu i usuwaniu . . . . . . . . . . . 8.5 Zadania ....... . .. .............................. „ . .

150 151 153 156 161 162 164 169 178 179 188 190

9. Dodatek B. Podstawy matematyczne .......... . ...... 192 9.1 . Teoria grup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.1 . Wiadomości wstępne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.2. Podgrupy, wa rstwy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.3. Grup ilorazowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.4. Grupa Z~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.5. Homomorfizmy grup . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.1.6. Iloczyn prosty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2. Transformaty Fouriera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.2.1. Charaktery grup abelowych . . . . . . . . . . . . . . . . . . . . . . . 9.2.2. Ortogonalność charakterów . . . . . . . . . . . . . . . . . . . . . . . 9.2.3. Dyskretna transformata Fouriera . . . . . . . . . . . . . . . . . . . . 9.2.4. Odwrotna transformata Fouriera . . . . . . . . . . . . . . . . . . . 9.2.5. Transformata Fouriera i periodyczność . . . . . . . . . . . . . . . 9.3. Algebra liniowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3.1. Wiadomości wstępne . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.3.2. Iloczyn wewnętrzny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.4. Teoria liczb . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.4.1. Algorytm Euklidesa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.4.2. Ułamki łańcuchowe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.5. Entropia Shannona i informacja . . . . . . . . . . . . . . . . . . . . . . . . . 9.5.1. Entropia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.5.2. Informacja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.5.3. Ograniczenie Holevo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.6. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

192 192 193 194 196 199 200 201 201 204 206 208 209 209 209 212 215 215 217 225 225 229 231 232

Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 Indeks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

Przedmowa do wydania polskiego

Od l?edakcji Seria ldee, nietody i na1zędzia infonnatyki przynosi pozycje, dotyczące aktualnych i \vażnych problen1ów informatyki z różnych jej dziedzin. Naszyn1 zamierzenien1 jest, by pozycje te - będąc na \vysokim poziomie nauko\vym - były jednocześnie przystępne dla szerokiego kręgu odbiorców: praco\vnik.ów naukO\yYCh, informatyków, studentów, ale również dla zainteresowanych informatyką specjalistów innych dziedzin i uczn iów starszych klas liceów. W tym względzie seria nin iejsza kontynuuje rnisj9 WSiP jako domu \vydawniczego, który pomaga uczyć się \V czasach, gdy ciągłe zdobywanie \Viedzy staje się koniecznością i 'vyzwaniem. W serii \vydawane będą pozycje zaró\vno autorów polskich, jak i pozycje tłu­ maczone na język polski. Op iekę nad serią w zakresie budowania oferty oraz nadzoru naukowego sprawuje Rada Naukowa, \V skład której wchodzą znani i cenieni profesorowie \vyższych uczelni: • Prof. dr hab. Lech Polkowski, Polsko-Japońska Wyższa Szkoła Technik Kon1putero\vych, Uni\versytet Warmińsko-Mazurski - przc\vodniczący ([email protected]);

• Prof. dr hab.

inż.

Tadeusz Kaczorek, Politechnika Warszawska

([email protected]);

• Prof. dr hab.

inż.

Robert Schaefer, Uni\versytet

Jagielloński

( schaefer@sof tla b. ii. uj .edu. pl);

• Prof. dr hab.

inż.

Andrzej Skowron, Uniwersytet Warszawski

([email protected]);

• Prof. dr hab.

inż.

Ron1an Słowiński, Politech nika

Poznańska

( slowinsk@sol. put. pozna n. pl). W ramach serii ukazały się już:

• /11111ownie danych. Podstawy organizacji i f1111kcjonowa11ia, Matthias Jarke, Maurizio Lcnzerini, Yannis Vassiliou, Panos Vassiliac.lis; • Wprowadzenie do języka XHTML. 1ivorzenie dy11a111icznych stron WWW z wykorzysta11ien1 XHTML i Ja1raScrip1, John Co,vełl; • Algory1111y J..,vantowe, Mika Hirvcnsalo; • WyZJvania progran1istyczne, Steven S. Skiena, Miguel /\. Revilla. W nadziei, że seria spotka sir; z przychylny1n przyj9cicn1 ze strony Czytelników, n1y miłej lektury.

6

życzy­

Od Tl111nnczn

Obficzenia k\vanto\ve cieszą się \V ostatnich latach ogromnym zaintereSO\Vaniem. Przyczyną tego jest fakt, że zastoSO\vanie komputcrÓ\V k\vanto,vych St\varza nadzieję na znaczną redukcję czasu \yYkOnY\vania obliczeń dla \vielu praktycznych problemów, np. dla przeszukhvania baz danych. W przypadku algorytn1u faktoryzacji, mającego zastoSO\vanic \V kryptografii, istnieje na,vct niożlhvość pokonania bariery \vykładniczej złożoności obliczenio\vej. Przewaga komputerów kwantowych nad klasycznymi ma swoje źródło w kwanto\vej równoległości obl i czeń: informacja \V n1aszynie k\vantowej jest repreze1ltO\Vana przez stany kwantowe - wektory z przestrzen i Hilberta, a obliczenia dokonY\vane S O))+ P2((x,,;,, r )). W przypadku, gdy uklad pomocniczy nie zakłóca uktadu pier1votnego, n1oże­ n1y go pomin 1 kwantowa

Do,vód. Załóżmy, że taka maszyna istnieje. Ponieważ /1 > I, istnieją d\va stany ortogonalne la1 ) i la2) . Wtedy ma1ny U(la1 )la1 )) =la1)la1) oraz U(la2) la1 )) = la2)la2), a także

u( )z Kwa ntowym odpowiednikiem klasy BPP jest rodzina języków akceptowanych przez kwantową maszyn~o

Teraz jednak, w odróżnieniu od IF';', nie ma prostego sposobu na znalezienie takiej reprezentacji k\vanto\vej elen1entów Ł„, aby bazę

IO), Il ), 12) ... 111 - J) można było zapisać

\V postaci iloczynu tensorowego dwóch 1nnicjszych baz reprezentujących podukłady Z„. Jeżeli jednak znamy jakiś rozkł.ad na czynniki 11=11 1112, taki że nwd(n 1, n 2) = 1, to szukany rozkład możemy znaleźć za pomocą chińskiego twierdzenia o resztach (twierdze nie 9.1.2). Na n1ocy tego t\vierdzenia istnieje bowiem bijekcja

określona

przez F((k1, ki )) = a 1n2k 1 + a2n 1ki, gdzie a 1 (odp. a2) jest 111ultiplikatywną odwrotności ą 112 (odp. n 1) n1oduło 111 (odp. n2). W zadaniu 2. polecamy sprawdzić, że F rzeczy\viście jest izomorfizmem. Zauważ1ny również, że odwzorowanie k1 ,_. a 1k1 (odp. k2 ,__, a2k2) jest permutacją Z„, (odp. Z„2 ), gdyż a 1 (odp. a2) posiada odwrotność n1ultiplikatywną. Teraz możc1ny przystąpić do rozkład u QFT (4.1 1). Załóżn1y, że

dla

z„,

i Z„2 istnieją kwantO\Ve transformaty Fouriera, tzn. 1na-

1ny k\vantowe reprezentacje Z„, i Z„,

{IO). II ), 12) ... 1111 - 1) } oraz dysponujemy programami

I

{ IO), Il), 12) ... 1112 - I}}

realizującym i

odwzorowania

4. Szybka faktoryzacja

Ola elementÓ\V z„ wykorzystamy reprezentację k\vantową Jk) = Jk1)Jk2), daną przez chińskie twierdzenie o resztach z k = a1112k1 + a211 1k2. Budując ob\vód kwanto\vy \vykonujący mnożenia (k1, ki) ,_. (a 1k1, a2k2), a następnie łącząc go z obwodami QFT dla obu sklado,vych, otrzymujemy Jk1 }Jk2} ,_. Ja1k1 )Ja2k2}

'f e- " ~ „ ..fili

,_. (__!___'f e_,."!:'' 111)) ( Jlr, '• =()

Rozkład

ten

2 1

1-

1

Ji2})

11=0

możemy zastoSO\vać

rekurencyjnie do 11 1 i 11 2. Zauważmy, że otrzymany rozkład \vymaga \VStępncj znajomości faktoryzacj i 11=11 1112, takiej że nwd(n1,n2) = I, lecz w ogólności proble1n polega ni1 znalezieniu nietrywialnej faktoryzacj i 11. Algorytrn Shora korzysta z odwrotnej k\vantowej transformaty Fouriera na Z 2m . Ponieważ jednak nie istnieje rozkład 2m na liczby \vzględnie pierwsze, musimy poszukać innego roZ\viązania. Szczęśliwic o k'\vanto,vych transformatach Fouriera na grupach ~ możemy dowiedzieć się czegoś \Vięcej.

Pon ie\vaż

odwrotna transforn1ata Fouriera w 2'"'L~r

:Ł„

jest symetryczna

\VZględem

l :ti'"

(4.11) (czynnik e- • zastępujcrny przez e7), IO \vybór, którą Z nich badać,

jest k\vestią osobistych preferencji. My pokażemy poniżej, \V jaki sposób zrcalizo,vać odwrotną transformatę Fouriera na ~ · Grupa Zi- posiada bardzo naturalną reprezentację 'vykorzystuj ącą 111 kubitów: element x = x„_ 12'"- 1+ + x111 _ 22111 - 2 + ... + x12 + xo, gdzie każdy X; E {O, I}, jest reprezentowany przez

68

4.1. Kwantowa transformata Fouriera

W jaki sposób zrealizować odwrotną QFT 2m -J

I lx) ,__, ,/F

L

''"" e 7" iy)

(4.12)

>~

przy użyciu obwodu kwantowego? Na początek zwróćmy uwagę na fakt, który w tym momencie nie powinien j u ż zaskakiwać: superpozycja po prawej stronie (4.12) jest stanern rozkłada lnym. Lemat 4.1. 3. 2"'- 1

°2Xłl)'

iri..f

'Ki.x

:::ie

Le ''" ly) =CIO) +ell' p ))CIO) +e2il l )) . . . (IO) +e;m=rp))

(4.13)

y=O

Dowód. Stosując przedstawie nie IY) = ly'b) = IY)lb), gdzie y' oznaczam - l najbardziej znaczących bitó\v y, ab jest najmniej znaczącym bitem y, możemy podzielić surnę "'' ( 4.13) na dwie części: 2•n - l

2m- l _ l

2::-l"'

2l11-l _ J

lrrirl>'

Le-;;;;- IY) =

L

>~

.)'=O

f =O

2m- l _ l

2m- l _ I

=

L

ly'O) +

e'~~IY) IO) +

2m- l _ I

-L

'm

e

L

2::it12\1 +I)

2::1X)·

e?

L

e

2 "'

IY' l)

e'';," e';:~IY)l l)

r:i'Jc

ly)(IO) +ei="I!)).

>~

o

Tezy do\vodzin1y indukcyjnie. Rozkład

(4.13) daje także wskazówkę, w jaki sposób przy użyciu obwodu kwantowego obliczyć transformatę (4.12). W wyrażeniu (4.13) I-ta faza stanu Il ) zależy tylko od bitów x0 ,x1 , • . „x1_ 1 i może być zapisana jako

= exp

7rix1_1) exp (7rix,1_2) ( 20 2

-( - - l )x1_1exp

(7riX1 , -2) 2

... exp

... exp

(r.ix,) ( 7riX_0) _, exp 21 21 1

0) • ( rrix,) ( 7riX exp _ _ 1 2 21 21 69

4. Szybka faktoryzacja Może1ny teraz przystąpić do opisu obwodu cję (4.12). Mając reprezentację k'vantową

k\vantowego wykonującego opera(4.14)

odwracamy porządek kubitów i otrzymujemy odnTotną reprezentację binarni1 (4.15) W praktyce po,vyższa operacja od\vracania porlądku kubitÓ\V nic jest konieczna, gdyż równic dobrze rnoglibyśn1y operować na reprezentacji (4.14); wpro\vadzarny j ą tu jedynie dla pclności 'vY'vodu. Na stanic (4.15) 'vykonujen1y od strony prawej do lewej następujące operacje: transformata Hadamarda na 111-tyn1 kubicie (pierwszym od pra,vcj) daje I

ft lxo)lx1 ) .. -IXm-2)(10) + ( Następnie uzupełniamy fazę

I)'•

(

1

1)'•

(- I

'11)).

t· ' do \vyrażcnia

(;rix

(;rix

, ) ... exp • ,1 ) exp __0, ) , exp (rrix~-z 2 2 2

stosując 'varunkowo operację

zmiany fazy

Tri) , ... , exp ( Tli • ,) . exp ( 2' „_, ) , exp ( 2Tri 2

Oznacza to, że dla

każdego

I E {I, 2, ... , 111 - l }, do in-tego kub itu 'vprowa-

dzamy czynnik fazo"'Y exp (

2:~,) wtedy i tylko \vtedy, gdy ku bity 111-ty oraz

1-ry mają \vartość l. Procedura ta daje stan I

!·u-

ft lxo) lx1 ) ... lx,,,_2)(10) +ci=" li )). W ten sam sposób postępujemy z kubitami znajdującymi się na pozycjach kolejno 111 - I, ... , 2, I: dla /-tego ku bitu najpienv '''Ykonujemy transformację Haclamarcla, co przepro,vadza ten kubit \V stan

~(IO) +( - J)x,_,IJ)), a następnie dla każdego k z zakresu I - I, I - 2, ... , 1 wprowadza1ny \Varunkowo czynnik fazo,vy , ,_, ) cxp ( Tri 2 \Vtedy i tylko wtedy, gdy kubity /-ty oraz k-ty rcalizujen1y, 'vykorzystując od\vzorowanic

70

mają \Vartość

1.

Operację tę

4.1. Kwantowa t ransformata Fouriera

IO) IO) ,_. IO) IO) IO)IJ ) ,_. IO}l l } ll}IO) >-> IJ)IO) ::i

11)11) ...... e 'l l )ll) 1'

działające

na kubity /-ty i k-ty. Macierz tego odwzorowania

możemy zapisać

jako

oo o o l o o oo I o o o o e ll"F I

k.1

=

(4.16)

:r;

Jeśli

nie brać pod U\vagę zn1iany ustawienia kubitów (x,,,_1,Xm-2 • ... ,xo) ,...... (x0 ,x1, ... ,x,,,_i), to opisana procedura n1oże być zrealizowana przy użyciu sieci o ~111(111 + l) bramkach, przedstawionej na rysunku 4.1. „\'.111- l

X1t1 - 2

YI

H

X111 - 3

xo

YO

ef> -+ a

4

(rnod

11),

otrzymując

(4.29) Ponie\vaż funkcja k >-+ a" (1nod 11) posiada okres r, 'vyrażenie (4.29) 1nożna przepisać

\V postaci 79

4. Szybka faktoryzacja r- 1

s1

.),,; L L lqr+ l}la

1 ),

(4.30)

/:() q=O

gdzie s1 jest naj,viększą liczbą całkowitą, dla której s1r +I < 111. 0C-L.)"viście s1 . rnoze . srę . za bardzo zm1en1a . . ć : zawsze mamy -Ili - I - -I -=:::: / nie s1 r 1·

I < -Ilir - -. 1·

3. Obliczamy odwrotną QFT na Z 111 i jako wynik otrzymujemy r·- 1

l -.;m

J

L L -.;ml "L..,e " S1

,.., q=O

111-

2

I

4 log log r

I > 4~--:-log log n ·

Połącze nie następujących

o

faktó\v pozwoli nam na sformułowan ie lematu 4.3.3:

• Prawdopodobieństwo, że d la losowo wybranego (z jecłnostaj nyn1 rozkła­ dern prawdopodobieństwa) a E Z„ rząd r = rz„(a) jest liczbą parzystą i a~

1

~-

I (mod n), równe jest co najn1niej

Stala Eu lera jest zdefiniowana przez / = lim 11 - ·x:

~

(lemat 4.2.4).

(I+~+~+ . .. +~ - log n). W pra-

cy (76) pokaza no, że w

powyższym twierdzeniu stałą 2,50637 można nawet zamien ić n a2,5d lawszyst kichłiczb r zwyj ątkiern r =2·3·5 · 7 · łł · 13· 17 · l9·23.

85

4. Szybka faktoryzacja

•

Pra\vdopodobieństwo, że In Il'

•

w "'Yniku obsef\vacji (4.31) otrzyrnan1y p, takie że d r111 I < ) , rO\Vlle ' jeSl · CO naJDlfllCJ · · · S2 (J Crllal 4.3.1). 2

Pra\vdopodobicńs!\vo, że n\vd(d, r) = I, równe 1·est co· na1·mnic1· 41 og\ og11 (le111at 4.3.2).

Le mat 4.3.3. Prawdopoclobicńs!\Vo, że algorytm kwa ntO\vy znajdzie rzi1cl clcn1entu grupy Z,„ równe jest co najmniej I

20 log log /1 • Uwaga 4.3.1. W podrozdziale 4.1.4 \VSpon1 n ieliśn1y, że podsla\vą wiciu interesuj11cych algorytn1ów kwan towych jest zakodowa nie i n teresuj ącej nas inforrn acj i \ve wspólczyn nikach k\van tov;ej superpozycji, a następnie wykonanie szybkiej QFT. Metoda ta jest 'vykorzysty\vana również do znajdo,vania okresu \V algorytn1ie faktoryzacji Shora: aby "'Ykorzystać k\vanto\vą \vspólbieżność, należy przygoto\vać superpozycję 1n- I

--k '°' ). L.., lk)IO ylll

k=O

nas infonnacja, czyli okres, zostaje wpisana do wspólczynnikó\v przez 'vykonanie operacji k ...... ak (mod n). W \vyniku otrzyrnujerny Interesująca

111-I

r-1

s1

1 ~ L lk)lił} = ~ '°'L lqr+l)la ) . ylll y/11 L.., k=O

/: O q:O

W powyższej superpozycji le"'Ym mnożnik i ern każdego ze stanów

la1) jest

„, L lqr +I).

( 4.4 J)

q:O

Jednak informacja o okresie jest już za\varta \VC \vspólczynnikach superpozycji \vektoró\v bazo,vych lx), x E Zm: współczynnik przy lx) jest różny od O\Vtedy i tylko \Vtedy, gdy x = qr +I, tak \vięc ci, l - (;

x)

2 .

5 Znajdowanie ukrytej podgrupy W tyn1 krótk im rozdziale on1ó\vin1y algorytn1 k\vantowy, który można uważać za uogólnienie algorytn1u Shora. Zrozumierny lepiej, dlaczego kon1putery kwantowe 1nogą być szybsze w roz\vii)zY'va niu pewnych problen1ó\v obliczeniowych. Tak zwany problen1 ukrytej podgrupy Simona można sformuło,vać \V postaci ogólnej w następujący sposóh [ 18]: Dane wejściowe: Skończona grupa abelowa G oraz funkcja p: G --+ R, gdzie R jest zhiore1n skończonym. Założeni e:

Istnieje nietry\vialna podgrupa H ~ G. taka że funkcja p jest stała i różnowartościowa na każdej \varsrwie podgrupy H. Wynik: Zbiór generujący podgrupę fi. Mówin1y, że fu nkcja p spełnia znl oźcnic Simona względem podgrupy H. Jeże­ li h E H, to ele1nenty g oraz g + h należą do tej samej \varstwy H (szczegóły rnożna znale:lć w podrozdziale 9.'I ), a pon ieważ p jest stała na warstwach H , rna rny p(g + '1) = p(J;). Mó,vimy również, że fu nkcja p jest H-okresowa. W podrozdziale 5.2 zobaczymy, że pewne interesujące problemy obliczenio\ve rnożna spro\vadzić do roZ\viązania problemu ukrytej podgrupy. W typo,vych zagadnieniach tego typu IGI jest zwykle tak duże, że wykonanie pełnego przeszukhvania '" celu znalezienia generatoró\v podgrupy H byłoby zadanien1 praktycznie niewykonalnym. Jednak rozmiar reprezentacji1 pojedynczego elernentu g E G ró,vny jest jedynie $(log IGI). Ponadto G na ogól posiada niahi liczbę generatoró\v. Będzien1y także brali pod uwagę rozmiar danych 'vy111aganych do opisu C; jest on z,vykle rzędu (log IGl)k, gdzie k jest ustalone i równe rozmiarowi danych \vejści R można obliczyć'" czasie wielo111ianowym względem log IGI. Aby lepiej zi lustrować istotę zadania, rozwiązanie problemu ukrytej podgrupy przedstawin1y, wykorzyst ując uogól n ioną postać kwantowego algoryln1u Sin1ona na IF'~'. Zauważ1ny również, że'" grupie IF'~' każda podgrupa jest równocześnie podprzestrzenią, tak więc zarniast pytać o zbiór generujący, moglibyśn1y zapytać o bazę. Znając zbiór generujący, bazę można znaleźć \Y 'vydajny sposób, stosując n1etodę eliminacji Gaussa (patrz zadanie 4.).

1 Przykładowo

elen1enty G mogą być reprezentowane w postaci łańcuchów binarnych.

89

5. Znajdowanie ukrytej podgrupy

5.1. I Uogólniony algorytm Simona W podrozdziale tym pokaże1ny, \V jaki sposób rozwiązać problem podgrupy Si1nona dla c = w~·. l:ln. addytyv,1ncj grupy 111-wyn1iarowej przestrze ni \Vektorowcj nad ciale1n liczb dwójko\vych Jł H.l.

11 11

111

musi być spełn i o n a równość l1F111 I = IH I · IF-l.l.I· ·

\vynika,

iż

.

5.1.2. J Algorytmy Do reprezentacji elementó\v !ii"~' będziemy musieli uŻY\vać n1iast do reprezentacji \vartości funkcji p: W';'

-+

R -

111

kubitó\v, nato-

\V

przybliżeniu

log2 [lF'~': H] = log2 l~I = 111 - log2 IH I kubi tów. Rozmiar danych potrzebnych do opisu G = IF';' równy jest tu jedynie 111. Zakladan1y, że względen1 roz1niaru danych \vejścio\vych, p można obl iczyć w czasie \vielomiano\vym. Zbiór generatorÓ\v ff można znaleźć, korzystając jedynie z funkcji p. Można pokazać (18), że jeżeli nic posiadamy źadnej dodatko\vej wiedzy op, tzn. p jest funkcją czarnej skrzynki (blackbox fu11c1io11; patrz podrozdział 6.1.2), to roz\viązanie tego problemu za pon1ocą jakiegokolwiek algorytn1u klasycznego \vyn1aga czasu 1vykladniczego, na\vet gdy dopuścimy ograniczone pnt\vdopoclobicństwo błędu. Z drugiej strony, jak pokaże1ny poniżej, stosuji1c obwód kwantO\yY, zadanie to n1ożna rozwiązać w czasie \vielo1niano\vym. Algorytm znajdo\vania bazy H polega na znalezieniu bazy H.l., którą oznaczymy przez Y, a następnie obliczeniu bazy H. Jak \VSpomnieliśmy \vcześniej, drugi krok można \vykonać \V sposób efekly\vny na komputerze klasycznyn1. Jak zobaczymy, zadanie znalezienia bazy H.l. byłoby prostsze, gdybyśmy wcześniej znali wymiar H.l.. W takin1 przypadku algorytm ma następującą postać: Algorytm A: Znajdowanie bazy (przy znanym wymi arze) I. Jeżeli d = di1n H.l. =O, zwróć 0 i zakoilcz pracę.

2. Za pomocą algorytmu B (poniżej) \vybierz z jednostajnym rozkJadem pra\vdopodobicńsr.va zbiór Y, składający się z d clcmentó\v należących do H• .

91

5. Znajdowanie ukrytej podgrupy

3.

Stosuj ąc metodę

eliminacji Gaussa (zadanie 4.), sprawdź, czy Y jest zbiorem clcmcntów liniowo n iezależnych. Jeśli tak, zwróć Y i zakończ pracę; w przeciwnym przypadku zgłoś niepowodzenie i zakończ pracę.

Poniżej pokażemy, że

drugi krok powyższego algorytmu poZ\vala na znalezie-

nie bazy Hl. z prawdopodobieńst\vcm nie n1niejszym niż ~ (lemat 5.1.2). Wcześniej

opiszemy jednak, \V jaki sposób można ten krok \vykonać szybko za pomocą ob,vodu kwantowego. Warto także wspo1nnieć, że \V powyższyn1 algorytmie komputer k\vantowy potrzebny jest jedynie do wygenerowania zbioru elen1entó\v z HJ. .

,.

Algorytm B: Wybór elementów z jednostajnym

rozkładem prawdopodobieństwa

l. Za pomocą transformaty Hadamarda-Walsha na IF';' przygotuj stan

(5.2) 2. Oblicz p, aby

uzyskać

~ L lx}lp(x)} =

)F L L lt + x}lp(t)} .

xE~

(5.3)

tET XEH

3. Za pomocą transforn1aty Hadarnarda-Walsha na IF'~' otrzymaj

=

2~ I: I: - log€ jest niniejsze niż dowolne € > O. p

Powtarzając wyszukiwanie określoną liczbę razy, możen1y zredukować dopodobieństwo błędu do dowolnej dodatniej stałej € .

praw-

Łat\vo się przekonać, że dowolny

klasyczny, deterministyczny algorytm wyszukiwania, któ1y zawsze z\vraca takie x, żefi.x) = 1 (jeżeli taki x istnieje), \vymaga N= 211 sprawdzeń f jeśl i jak iś ałgorytn1 wykonuje xnniej niż N spra,vdzcń, to możemy zmienić f w taki sposób, aby odpowiedź nie była już popra\vna. Uwaga 6.1.3. Oczywiście w powyższej argun1entacji istotny jest fakt, że bierzen1y pod uwagę jedynie funkcje czarnej skrzynki. Gdybyśmy zamiast tego dysponowali ałgo1yt1nen1 obliczającym f, bardzo trudno byłoby stwierdzić, jak szybko zwracałby on informację o szukanym x. W istocie kwestia złożoności czasowej procesu odzyskiwania x z algorytmu obliczającego .f wiąże się bezpośrednio z trudny1n i dotychczas nieroZ\viązanym problemem P -f NP. Dopuszczając łoso,vość,

nie możen1y znacząco poprawić efektywności wyszukiwania deterministycznego. Ustalmy y E ~ i rozważmy funkcję czarnej skrzynkiJ;. zdefiniowaną przez ) { l jeżeli x = y, f.,.(x = O w przeciwnym przypadku.

(6.1)

Jeżeli będzierny wybierać różne kładem pra,vdopodobieńst\va,

elementy x1, ... , xk E IF'~ z jednostajnyrn rozto prawdopodobieństwo znalezienia y wynosi

~ . Aby znaleźć y z prav1dopodobieństwcm ró\vnym co najmniej p, konieczne byłoby

'vykonanie pN sprawdzeń. Sytuacji nie poprawi niejednostajnego.

także użycie rozkładu

Le mat 6.1 .1 . Niech N= 211 i niech f będzie funkcją czarnej skrzynki. Zakła­ damy, że AJ jest algorytmem probabilistycznym wykonujący1n sprawdzenia f i zwracającym ełe1nent x E lF'~. Jeżeli, dla do\volnej różnej od stałej funkcji f, prawdopodobicr1sl\vo, że f(x) = I wynosi co najmniej p > O, to istnieje funkcjaf, taka że A1'vykonuje co najn1niej pN - l sprawdzeń.

101

6. Algorytm wyszukiwania Grovera

Dowód. Niech.f;. będzie zdefiniO\vane jak w (6.1), a Py(k) będzie prawdopodobier1stwem, że algorytm At, zwraca y, \vykonując k sprawdzeń. Z założenia Py(k)

~ p. Dowiedziemy istnienia y E IF'~, takiego że Py(k) ~ k ~ 1 .

Po pienvsze,

pokażen1y, korzystając

z indukcji,

że

vEF''l

.

Jeżeli k =

O, to Ah· zwraca x E

lF~ z prawdopodobieństwem p,, skąd

L Py(O) = L Py = l . .YEff"l

Za łóżmy

teraz,

że

LPy(k - I ) ~ k . yEF;

W k-tyn1 sprawdzeniu algorytrn At,. bada .f(y) z pewnym stwem

ąy, więc

Py(k)

~

Py(k - l ) + ąy.

L Py(k) ~ L Py(k - I)+ L ,,., E J·e""' „ 2 y '"2 Ponieważ

y n1oże1ny tak i, dla którego

Py(k)

\vybrać

prawdopodobień­

Stąd

ąy ~ k + l.

na N= 2"

różnych

sposobó\v, \vic;c niusi

istn ieć

~ k ~I.

Wynika z tego,

że k ~ 1 ~ Py(k) ~ p, a zaten1 k ~ pN -

o

I.

6.1.3. I Wyszukiwanie kwantowe z jednym sprawdzeniem Kontynuując badanie funkcji czarnej skrzynki/: IF'~ -+

!F2,

nlożcmy zadać py-

tanie, czy istnieje możlhvość skonstru- 21y>) xE~

i \vykonujemy

transforr11ację

1-Iadamarda H,„ otrzymuj . xeiF'~

Stąd, wykorzystując

oznaczenia \Vprowadzone \V rozdziale 8., możemy napisać, że P = l'lfi}('!/11. Notacja ta nie ma tu jednak dużego znaczenia. Bardziej istotne jest to, że reprezentacja (6.18) umożliwia łal\ve obliczanie \vyniku działania - H 11 R11 H11 na ogólną superpozycję (6.19) Oznaczając

A= FL ex XE~ (średnia

L

z amplitud), widzin1y, że

c,lx)

=AL

lx} +

..,.

XE"l

L (ex - A)lx)

(6.20)

xe~

jest rozkladem (6.19) na d\va wektory ortogonalne: pierwszy z nich należy do podprzestrzeni rozpiętej przez l/J, a drugi do dopełnienia ortogonalnego tei podprzestrzeni. Fakt, że pierwszy składnik prawej strony (6.20) należy do podprzestrzeni generowanej przez 1/J jest oclY'visty, a ortogonalność składnikó'v sumy lat\VO jest sprawdzi ć:

{A L X

lx}I l:: ~ · 2", to możemy znaleźć rozwiązanie x z prawdopodobieństwem co najmniej

~, po prostu zgadując. Z drugiej strony, jeżeli k =O, to G„ wcale nie zmienia

wyjściowej

114

l7'i J.

superpozycji.

6.2. Metoda wzmacniania Grovera

Oczywiste jest, że

l "J 480

rr = - 2I + 40 0

+ u>

dla pewnego c5, takiego że lc51

l4~0 J + l) Oo = ~ + 2c50 więc 2 l4~0 J + Oo odległe ~ l2c50o I ~ ~, uo :::' ·n2(" ")I = 4. ·2(2l" J+ 1)"'

(2 Tak

~ ~, ski1d 0.

(

Sill

l)

jest

od

SI

480

2

-

Metodę Grovera dla \vyszuk iwa nia stępuj ącego algorytn1u:

o

z czego wynika,

3

że o

można zapisać ·w forn1ie

na-

Dane ,vej ściowe: Funkcjaczarnejskrzyn kif: lF'; -+ IF2 i k = l{x E ~ :.f(x) =

l}I.

k\van towego

Algorytm wyszukiw ania Grovera

Wynik: E lemen t y E n1ent istnieje. 1.

Jeżeli k > ~ · 2",

IF';, dla którego j(y) = l

to z jednostajnyn1

bierz y E lF'; i zakończ pracę.

2. W przeciwnyrn przypadku oblicz r =

(roZ\viązanie ), jeżeli taki ele-

rozkładem pra,vdopodobieńst,va

l;;.J,

"'Y-

gdzie 00 E [0,?r/ 3] jest okre-

. 2 8o = 2". k s' Ione przez sin

3.

Posługując się transforrnacją

Hadamarda H„, przygotuj \vyjściową superpo-

zycję

~L lx} . x --7"z

. it:-

4. Zastosuj r-krotnie operator C„. 5. Aby uzyskać y E IF';, \Vykonaj obsenvację.

Jeżeli k ;;,: ~ · 2

11 ,

to \V pienvszy1n kroku uzyskuje111y prawidłowy \\')1nik z prawdo-

podobieńsl\ven1 co najmn iej ~. W przeciwnyn1 razie, na 1nocy ł\vierdzenia 6.2.l, algo1ytn1 zwraca

roz,viązanie z prawdopodobicńsl\ven1 nie 111niejszyn1 niż ~.

I115

6. Algorytm wyszukiwania Grovera

W obu przypadkach od zera.

prawdopodobieńshvo

znalezienia

rozwiązania

jest

różne

l

Jeśli k = 1 i n jest duże, to 400j ~ ~fi. Możemy więc znaleźć rozwiąza­

fi)

nie z niezerowym prawdopodobieńst\vem, wykonując o( spra\vdzeń, co jest znacząco lepszym rezultatem niż wynik, który można osiągnąć za pon1ocą jakiegokolwiek klasycznego algorytmu losowego. Bardzo ciekawy jest też przypadek k = ~ · 2". Wtedy sin 2 Bo

= ~, skąd Bo = ~ .

Zgodnie z (6.28) pra\vdopodobieńst\vO znalezienia rozwiązania po jednej iteracji G„ równe jest sin 2(3B0 ) = sin2 ~ = 1. Oznacza to, że dla k = ~ · 211 po jednokrotnym wykonaniu operacji G„ 1nan1y całkowitą pewność znalezienia rozwiązania.

Dla dowolnego klasycznego algorytmu wyszu kiwania jest to w oczywisty sposób niemożli\ve. Niestety zwykle nie znamy wartości k z góry. W nast9pnyn1 podrozdziale zaprezentujemy uproszczoną wersję metody zaproponowanej przez M. Boyera, G. Brassarda, P. Hs.'lyera i A. Tappa [17), która umożliwia wyszukiwanie pożą­ danego elementu nawet wtedy, gdy k nie jest znane.

6.3. I Zastosowania metody wyszukiwania Grovera

6.3.1. I Wyszukiwanie w przypadku nieznanej liczby rozwiązań Rozpocznien1y od przytoczenia elementarnego wyniku, którego dO\VÓd pozostawiarny jako ćwiczenie. Lemat 6.3 .1. Dla dowolnego rzeclY\vistego a oraz dodatniego całkowitego 111 111 -

I

. I) (( 2 I + L COS

) = sin(2met) . .

Cl'.

1-=0

Następny ważny

2 sin et

lemat pochodzi z pracy (17].

Lemat 6.3.2. Niech /: JF~-> iF2

będzie funkcją czarnej skrzynki z k ( ~

· 211

rOZ\viązaniami, niech Bo E [O, n / 3] będzie zdefiniowane równaniem sin2 Bo =

116

~. i niech

111

będzie dowolną dodatnią liczbą całkowitą. Wybieramy

6.3. Zastosowania metody wyszukiwania Grovera

r E [O, 111 - I] z jednostajnym ścio\vej superpozycji

rozkładem prawdopodobieństwa . Jeżeli

do wyj-

-dz. L: lx) xef':•

r-krotnie zastosujemy G,„ to ró\vne jest p _ ~ _ sin(411100 ) "- 2 4111 sin(200 )

prawdopodobieństwo

otrzymania

roZ\vi ązania

·

Dowód. W poprzednim podrozdziale przekonaliśmy się, że po r iteracjach G11 prawdopodobieństwo uzyskania rozwiązania wynosi sin2 ((2r + I)80). Stąd, jeżeli r E [O, 1n - l) jest wybrane z rozkładen1 jednostajnyn1, to wobec lematu 6.3. l szukane pra\vdopodobieństwo jest równe 1n-

I

111 -

1 2 P111 = 111 .!... "'""sin ((2r+ l)Bo) = L 2111 L

I

"'"'ci 1-=-0

r=O

I = 2-

sin(411100 ) 4111 sin(200 )

U\vaga 6.3.1. Jeżeli ni sin(411180 ) skąd

~ 1=

sin~~

. (20 )

cos((2r+ 1)200))

o

·

~ sm . (~Oo)' to

. (;O) sin(2Bo) sm 0 I

~

~ 111 sin(280 ), .

.

.

4 . Wtedy z powyzszego lematu \vyn1ka, ze P„

~

I

-4 . Ozna-

4m.Siil o cza to, że jeżeli 1n jest wystarczająco duże, to r-krotne zastosowanie G„, gdzie r E [0, 111 - l) jest wybrane z rozkładem jednostajnym, pozwoli na otrzymanie

rozwiązania z pra\vdopodobieństwen1 nie mniejszym od ~.

Załóżmy teraz, że nieznana liczba k spełnia O < k ~ I

sin(200 )

=

l

2 sin 00 cos 00

=

2•

& !f.. &,/F

2J.!((2• - k) "'

Vk

"'

więc wybierając 111 ~ ,/F, mamy pewność, że 11i ~ przedsta\vionego

niżej

i ·2". Wtedy

. Sill

'

(~Bo) . Prowadzi to do

algorytmu.

117

6. Algorytm wyszukiwania Grovera

Kwantowy algorytm wyszukiwania

Dane \Vej ścio,ve: Funkcja czarnej skrzyn ki j: IF'~

-+

lF2.

Wynik: Elen1ent y E IF'~, dla którego j(y) = I ( rozwiąza n ie), jeżeli taki clcn1ent istn ieje. l. Wybierz z jednostajny1n rozkładen1 p ra\vdopodobieńst\va elen1ent x E Jeżel i j(x) = I, zwróć x i zakończ pracę.

lF~ .

l J2'i

= J + I, \vybicrz liczbę ca ł kowitą r E [0, 1n - Il z rozkładem jednostajnym. 3. Posługując się transfonnacją I lada1narda H„, przygot uj wyjściową superpo-

" 2. W przeciwnym przypadku

111

zyCję

)F I: ix) xer,

i zastosuj r-krotnie operator G„. 4. Aby uzyskać y E F'~, wykonaj obserwację. Korzystaj ąc

z pop rzednich lematów, możen1y \V prosty sposób ocenić prawdopodob ier'l stwo podania przez ten algorytn1 poprawnego \vyniku. Niech k

będzie liczbą roz\viązaf1 f Jeżeli k >

! ·2

11 ,

to z

prawdopodobieńsl\vem nie .

mniejszy111 od

! ,algorytn1 poda roz\viązanie po pier~1szyn1 kroku. Z drugiej

strony dla k ::;;

3 11 · 2 mamy 4

111

fi-

;;::

Vk

;;::

I si n(200 )'

a zaten1, zgodnie z uwagą 6.3.l, prawdopodobień sl\vo, że uzyskamy rOz\viąza.

.

.

. . I

nie, \vynos1 co naJrn111CJ

4.

Uwaga 6.3.2. Pon ieważ n1amy pewność, że powyższy algorytm poda rozwi;izanic z prawdopodobieństwem nie mn iejszym niż ~ , więc 111ożen1y powiedzieć, iż rozwiązan ie może być

znalezione śred nio w czterech próbach. W próbie liczba \vykonY\vanych sprawdzeńjwynosi co n aj\vyżej j2'i.

każdej

Wykorzystuj ąc rnetody zaproponowane w pracy [17], 1n ożna uzyskać lin iową pop ra\vę efektywn ości powyższego algorytmu. W obu przypadkach spełnione jest poniższe twierdzenie.

118

6.3. Zastosowania metody wyszukiwania Grovera

Twierdzenie 6.3.1. Posługując się ob,voden1 kwantO\\'Yrn \rykonujący111

O(~) sprawdzeń fun kcji czarnej skJzynkif, n1ożna z niezero,rym prawdopodobieóst\vern rozstrzygnąć, czy istnieje element X E Il"~, taki że /(x) = l. W następnym rozdziale przedstawin1y po111yslO\V~! technikę opracowaną przez R. Bealsa, H. Buhrmana, R. Cleve'a, M. Mosca i R. de Wolfa (6] i pokażemy za jej pon1ocą, że powyższy algorytn1 jest optymalny z dokladnością do stałe­ go czynni ka. Do,volny algorytm k\van towy, który z niezerowym prawdopodobieństwem rozstrzyga, czy istnieje rozwiązan ie f, wykonuje D( ~) sprawdzeń funkcji f Wynik ten zaklada korzystanie z funkcji czarnej skrzynki, a zatem nie daje dolnego ograniczenia na złożoność dla funkcji obliczalnych (patrz uwaga 6.1.3). Z drugiej strony, zastępując funkcję czarnej skrzynki fun kcją obl iczalną, otrzy1nuje1ny n astępujące twierdzenie: obwode111 kwanto\ryrn, n1ożn a z niezero,rym prawdopodobieństwen1 uzyskać roz,viązan i e dowolnego probłe1nu \V klasie NP w czasie o( ~p(11)), gdzie p jest \Viełomianem zależnym od konkretnego proble1nu.

Twierdzenie 6.3.2.

Posługuj C, (x, y) ,__. (xly}. Wszystkie n-wymiarowe przestrzenie Hilberta są izornorficzne, może1ny wic;c każdą taką przestrzeń oznaczać przez H11 • Dla każdego x, y, z E H oraz c 1, c2 E C iloczyn \Vewnętrzny musi spełniać następujące aksjo maty: l. (xly} = (ylx}*. 2. (xlx} ;;::, Ooraz (xlx} =O \Vtw x =O. 3. (xlcr y + c2z} = c1 (xjy} + c2(xlz}. Jeżeli E = { e 1, • •• , e11 } jest ortonormaln ą bazą przestrzeni H, to każdy wektor x E H można przedsta,vić \V postaci x = x 1e 1 + . . . + x11 e11 • Maj ąc ustaloną bazę E, rn ożna •..vcktor x wyrazić za pon1 ocą \vs półrzędnych względe m tej bazy x = (x 1 , • • . , x„ ). Stosując tę reprezentację, mozna łatwo pokazać, że baza ortonormalna indu kuje iloczyn \Vę\vnętrzny (xly} = X~YI + .. . + x;,y„.

(8.6)

Z drugiej strony każdy iloczyn wewnętrzny jest induko\vany przez jakąś bazę o rtonorm alną. Dlatego też, oznaczając dowolny iloczyn \vewnętrzny przez (-I-), za pomocą procedury o rtogonałizacji Gran1a- Schmidta możemy znaleźć bazę {b 1, .. . , b11 } orto n ormalną wzgl ęde m (-1-}. Wtedy mamy (xly} = (x1 b 1 + .. . +x„ b11 l.Y1b 1 + . . . + Y11bn} =xjy1 + . . . +x;.y„ . Iloczyn wewnętrzny pozwala w naturalny sposób zdefin iować normę wektora: llxll = ~. Mó\viąc niezbyt precyzyjnie, zupełność przestrzeni \vektoro,vej H polega na tyn1, że za,viera ona wystarczająco d użo wektoró\v, tzn. przynajn1niej jeden dla każdego przejścia granicznego. Definicja 8.2.1. Przestrzeli wektoro,va f i jest zupełna, jeżeli dla każdego cii1- ·' gu wektorÓ\Vx;, takiego że litn 1lx111

-

x11 1l =O,

111.11 - 0 0

istnieje wektor x E H, taki że ł in1 llx111

-

xll =O.

11- 0 0

137

8. Dodatek A. Fizyka kwantowa

przestrzeni Hilberta jest fakt, że każda podprzestrzeń WE H, która także jest przestrzenią Hiłherta7, posiada dopełnie­ nie ortogonalne. Dowody poniższych lemató\v pozosta\viamy czytelnikowi jako ćwiczenie. Ważną geometryczną \Vłasnością

Lemat 8.2.1. Niech W

będzie podprzestrzenią

przestrzeni H . Wtedy zbiór

\VCktorÓ\V W =

{y EH: (ylx) =O dla każdego x E H}

jest także podprzestrzenią przestrzeni H. Zbiór ten nazY'vany jest niem ortogonalnym przestrzeni W.

dopełnie­

W jest podprzestrzenią skończenie 'vymiaro,vej przestrzeni Hilberta H, to H = W © W.L.

Lemat 8 .2.2.

Jeżeli

8.2.2. I Operatory No,voczesne ujęcie mechaniki k\vanto\vej oparte jest \V dużej mierle na odw·zoro,vaniach linio,vych. W kolejnych podrozdziałach omó,vimy te \vłasności od\vzoro,vań linio,vych, które rnają naj,vi9ksze znaczenie dla mechaniki k\vanto\Vej. Nadal będzierny konccntrO\vać się na układach k\vanto,vych o skończonej liczbie poziomó\v, dlatego zakładamy, że rozpatrywa ne w nast9pnych podrozdzia łach przestrzenie wektoro,ve są skończenie,vymiaro,ve, chyba że zostanie wyraźnie zaznaczone, iż jest inaczej. Na pocz'!tku musimy \Vpro\vadzić kilka no,vych terminów. Od,vzorowanie liniowe H-> H naZ)'\vamy operatorem, a zbiór operatoró\v określonych na przestrzeni H oznaczamy przez L(H). Dla operatora T definiujemy normę operatora jako

li Tll = sup li Txll. 11•11=1

Niezero'vy wektor x E /{ nazy,vamy \vektorcrn \vłasnym operatora T, odpowiadającym 'vartości 'vłas nej .A. E C, j eżeli 'l'x = >.x. Jeśli

doda,vanie i mnożenie przez liczbę zdefiniuje się \V naturalny sposób (prledsta,viony poniżej), zbiór operatoró\v także t\vorzy przestrzeń \vektoro\vą. Niech S, TE L(H) oraz a E C. Wtedy S + Ti aS są operatorami \V L(H) zdefinio,vanymi jako (S + D x = Sx + Tx oraz (aS)x = a(Sx ) dla 7

138

każdego

x E H.

Dla skończenie wymiarowych przestrzeni Hilberta wszy.;tkie podprzestrzenie są przcstrzenian1i Hilberta.

także

8.2. Matematyczna strukt ura teorii kwantowej

Definicja 8.2.2. Dla ró\vnanie

każdego

(x!Ty) = (T"xly} dla

operatora T: H --. H, operator T * spełniający

każdego

x, y E H

naZ)'\vamy operatorem sprzężonyn1 do T. U\vaga 8.2.l. Przy ustalonej bazie {e 1, .. . , e11 } \V przestrzeni H11 każdy operator T jest rcpreze11to,vany przez 1nacierz zespolo n ą n. x 11. Macierz operatora sprzężonego jest macierzą powstałą z transpozycji sprzężenia zespolonego n1acierzy operatora T. Niech {x 1, . .. , x11 } i {y 1, . . . , y11 } będą ortonormalnyrni baza ni i przestrzeni H11 •

Można pokazać, że li

li

(8.7) i= I

i= I

(patrz zadanie -i .). Definicja 8.2.3 . Niech {x1, • •• , x11 } będzie bazą o rtonormalną. Wielkość li

T r(T) =

L (x;!Tx;} i=I

naZ)'\Va

się śl ad em

operatora T.

Z (8.7) \vyni ka, że pojęci e śladu jest dobrze określone. Ponad to oczywiste jest, że ślad jest liniowy. Za u\vażn1y także, że \Vrep rezentacji macierzowej ślad jest sumą ele1nentó\v diagonalnych macierzy. Definicja 8.2.4. Operator T jest jest unitarny, jeżel i T• = r - 1. W dalszyn1

ciągu

przydatne

sa n1osprzężony, jeżeli

będą następuj ące

T' = T. Operator T

len1aty:

Lemat 8.2.3. Operator samosprzężony ma rzeczywiste \vartości \vłasne. Do\vód. Jeżel i Ax = .Ax, to

.A*(x!x} = (.Axlx) = (Ax!x) = (x!Ax} =.A(xlx}. Ponie\vaż

z definicji wektor własny x ~ O, to .A• = .A.

własne różnym wa rtościon1 włas;iyn1 są

Lemat 8 .2.4. Wektoty

operatora sarn osprzężo ncgo ortogo nalne.

o odpO\vi adającc

139

8. Dodatek A. Fizyka kwantowa

Do\vód. Załóżmy, że >- ~ .>-', Ax = .Ax oraz Ax' = .A'x'. Ponieważ na mocy poprzedniego lematu .A i >-' są rzeczylviste oraz

.A' (x'lx) = (Ax'lx) = (x'IAx) = .A (x'lx), \Vięc

o

(x'lx) =O.

Definicja 8.2.5. Mó\vimy, że samosprzężony operator T jest dodatni, jeżel i (x!Tx) ~ Odla każdego x E H. U\vaga 8.2.2. W zbiorze operatorÓ\V nlożemy \vpro\vadzić częściowe uporząd­ ko\vanie poprzez następującą definicję: T ~ S wtedy i tylko wtedy, gdy operato r T - Sjest dodatni. Jeżeli W jest podprzestrzenią przestrzeni H oraz H = W EB W.L, to każdy wek-

tor x E H można jednoznacznie przedsta\vić w postaci xw + xwi , gdzie Xw E W, a X w~ E w .L. Łatwo spra\vdzi ć, że Od\VZOrO\vanie Pw, zdefiniowane jako Pw(Xw + xw~ ) = xw, jest san1osprzężonym od\vzoro\vaniern linio\vym. Nosi ono naz\vę operatora rzuto\vego (lub rzutu ortogonalnego) na podprzestrzeń W. Oczylviście P~v = Pw. Z drugiej strony niożna pokazać, że każdy samosprzężony operator P, taki że P2 = P, jest rzutcn1 na pe\vną podprzestrzeń przestrzeni H (zadanie 2.). Zbiór operatorów rzuto\vych w L(H) oznaczamy przez P(H). Z\vróćn1y uwagę, że operacja rzuto\vania nie Z\viększa normy wektora:

Przedostatnia ró\vność, nazY'vana twierdzeniem Pitagorasa, wynika z faktu, że xw i Xwr są ortogonalne. Operatory rzulO\VC odgry\vają \vażną rolę w teorii operatoró\V sarnosprzężonych i dlatego \V następnyn1 podrozdziale zajmiemy się ni111i dokładniej. Ponie,vaż \V teorii k\vanto,vej bardzo istotne jest także pojęcie operatorów unitarnych, 01nówimy teraz ich 'vybrane własności. Lemat 8.2.5. Operator unitarny U: H -+ H 7.achowuje iloczyn \vewnętrzny, tzn. {Ux!Uy) = (xly). Do,vód. Własność ta 'vynika bezpośrednio z definicji operatora sprzężonego oraz z definicji unitarności:

o

{Ux!Ux) = {U ' Uxly) = ( U 1 Uxly) = (xly) . Stwierdzenie 8.2.1. Operator; unitarne zacho\vują nonnę, tzn. Stwierdzenie Od\vrotne do poprzedniego len1atu

140

także jest

li Vxll = llxll.

prawdzi,ve.

8.2. Matematyczna struktura teorii kwantowej

Lemat 8.2.6. Operatory U: H ___. H zachowujące iloczyn wewnętrzny są unitarne. Dowód. Załóżmy, że ( UxlUy) = (xly) dla każdych x, y E H. Wtedy w szczegól ności li Uxll = llxll dla każdego x E H, z czego wynika, że U jest injektywne. Po nieważ zakładaliśmy, że wymiar przestrzeni H jest skończony, w i ęc U jest także surjektywne. A zate1n istnieje u- 1 i

co oznacza, że U* =

u- 1, czyli U jest operatorem unitarny1n.

Lemat 8.2. 7. Operatory U: H -> H zacho\vujące Dowód. Prawdzhvość tożsamości polaryzacyjnej

norn1ę są

D

unitarne.

3

(xly) =

kL

/ (y + /xiy + ikx)

(8.8)

k~O

rachunkie1n (patrz zadanie 4.). Z (8.8) \V)'nika wprost, że operatory zachowujące nonnę zachO\vują także iloczyn we'ń1 nętrz­ ny. Tezę otrzy1nujemy, stosując len1at 8.2.6. D 1nożna \vykazać bezpośredn im

Len1at 8.2.6 można jeszcze trochę ,vzmocnić:

Lemat 8.2.8. Niech {x 1, .. . ,xk} oraz {Y1, . . . ,yk} będą zbiorami \Vektorów z przestrzeni H. Jeżeli (x;lxj) = (ydyj) dla każdego i,j, to istnieje od\vzoro\vanie unitarne U: H -+ H, takie że y; = Ux;. Dowód. Niech vV będzi e podprzestrzen ią przestrzeni H generO\Vanej przez wektory x 1 , ... , Xk · Istnieje wtedy podzbiór X1, .. . , Xk będący bazą W. Bez utraty ogó lności możemy założyć, że podzbiorem tyn1 jest x 1, ••• , x,. dla pewnego I! ~ k. Definiujemy teraz Od\vzorowanie U: W ___. H jako Ux; = y; dla każdego i E {I, . . . , k'} i rozszerzan1y je do odwzorowania liniowego w jedyny możliwy sposób. Pokaże1ny najpienv, że {Y 1, . .. , Yk'} jest bazą !Jn(U). OcZ)'\viśeie wektory te generuj In1( U) na ca łą przestrzeń H w sposób przedstawiony pon iżej. Niech {z 1, .. . , Zr} będzie orto normalną bazą przestrzeni w.L, a {z;, ... , z~} ortono rn1alną bazą Im(W).L. Jeżeli rozszerzenie U zdefiniujemy jako U(z;) =z; dla każdego i E { 1, . . . , r}, 10 otrzymane \V ten sposób odwzoro\vanie U:/-/--> I-I jest oczywiście bijekty\vne. Aby do\vieść, że U jest unitarne, na mocy lematu 8.2.7 pozostaje pokazać, że U zachowuje iloczyn \vewn ętrzny. W tyn1 celu wystarczy (dzię ki l ini owości) dYit )) =O dla każdego Yi- Tak jak poprzednio n1ożemy \vięc \vyciągnąć \vniosek, że \vektor y1 - (c\11 y 1 + ... + c~>YL') jest ortogonalny do podprzestrzeni genero\vanej przez \Vektoiy y 1, •••• Yk· Ponie\vaż jednak \vektor ten należy do tej przestrzeni, musi \vięe być \vektorem zerowyn1. A zaten1 y;

= c(i)1 Y1 + . . . +cit(i)Yit = c(i)1 Ux1 + . .. + ck'(i) Uxit = Ux;.

D

lJ Reprezentacja spektra lna operatorów

samosprzężonych

Dla dowolnych \Vektoró\v x. y E H„ definiujemy linio\ve od\vzoro\vanie lx)(yl : H„ -+ H„ jako

lx)(ylz = (ylz)x. Łatwo zau\vażyć, że jeżeli

podprzestrze(1

llxll = I, to lx)(xl jest rzutem na jedno\vyn1iarow11

genero\vaną

przez x.

U\vaga 8.2.3. Jeżeli A. B E L(H„), to

IAx)(Bylz = (Bylz)Ax =A(ylB. z)x =Alx)(ylB' z. Równość zachodzi dla każdego

z E H„, man1y zatem IAx)(Byl = Alx)(ylB*.

Uwaga 8.2.4. Operator sprzężony do lx)(yl ma prostą postać: (lx)(yi)• = IY)(xj. U\vaga 8.2.5. Niech {x 1•••• , x„} będzie ortonormalną bazą przestrzeni H„. Wtedy reprezentacją macierzo\vą Od\vzorowania x1)(xil jest po prostu ma· cierz, której elementami są same zera z \yYjątkiem n1iejsca przecięcia i-tego rzędu oraz j-tej kolun1ny, \V którym znajduje się 1. Wynika z tego \vprost, że od\vzoro\vania lx1)(xA generują całą przestrze11 L(H„). Rzeczywiście, jeżeli T E L(H„), to reprezen ta~ją macierzową operatora Tw bazie {x 1 , ••• , x„} jest łl

T=

Ił

LL

(8.15)

(x, ITx.)lx,)(x,I .

r=I .r-1

Łal\vo zau\vażyć, że

od\vzoro\vania lx1)(xil s11 liniO\VO przestrzeń L(H„) rna \vyn1iar 11 2 .

niezależne,

a zatem

143

8. Dodatek A. Fizyka kwantowa

Aby wprowadzić pojęcie rozkładu spektralnego san1osprzężon cgo operatora T, musimy najpierw przedsta\vić pewien dobrze znany fakt: H„ będzie operatorem san1osprzężo­ nyn1. Istnieje ortonormalna baza przestrzeni H„ złożona z \vektoró\v \vlasnych operatora T. Do,vód. Do\VÓd jest indukcyjny wzgl ędem n = clin1 H 11 • Jedno\vymiaro\va przestrzeń H 1 jest genero\vana przez pewien \Vektor jednostko\vy e 1. Oczywiście Te 1 = ,\e1 dla,.\ E 1, niech,.\ będzie \vartością \vłasną operatora T, a W podprzestrzeni

=,.\ •(xly) =O,

co oznacza, że równ ież Ty E W.i . Z tego \\1Zględu może1ny zająć sic; od\vzorowaniem T ograniczonym do podprzestrzeni lł' i W.i, tz n. T: vV --> W oraz T: W.i ---+ Ht.l i stosuj ąc za łożenie indukcyj ne, znaleźć ortonorrnalne bazy tych podprzestrzeni składające się z \Vektoró\v \Vlasnych operatora T. Ponieważ H11 = vV © W.i, to suma n1nogościo\va haz podprzestrzeni Ił' i w.1. jest szukaną bazą przestrzeni H11 • O teraz \vprO\vadzić pojc;cie reprezentacji spektralnej, bc;dące bardzo przydat nym narzędzier11 do badania od\vzoro\vań san1osp rzężonych . Niech x 1, ... , x11 będą ortononnalnyn1i wektorami \vlasnym i samosprzężonego operatora T : H11 --+ H,„ a ,.\ 1, ... , ,.\11 od powiad ającyn1i in1 \Vartościa n1i \Vłasnymi. Na nlocy t\vierdzenia 8.2. l liczby ,.\; są rzeCz)l\viste, jednak nie 1nuszą być róż­ ne. Zbiór wartości własnych naz)'\vany jest \Vidmetn. Łat\vo można sprav;idzić (zadanie 3.), że Możen1y

(8.16) (8.16) nazywany jest reprezentacją spektralną operatora T. Jeżeli T posiada wielokrotne \Vartości \Vlasne, to mówimy, że operator Tjest zdegenero,vany; w przeeiwnyn1 przypadku 1nówimy, że T jest niezdegenero,vany. Jak łat\vo spnl\vdzić, reprezentacja spektralna (8.'16) operatora niezdegenero\\1anego jest jednoznaczna. Wartu zauważyć, iż nie t\vierdzin1y, że \vektory X; są jednoznaczne: jedynie operatory rzulowe lx;) (x;I są jednoznaczne. Jeżeli operator T jest zdegenerO\vany, to 111ożemy pogrupo\vać wielokrotne \vartości \vłasne \vystępuj ące w (8.16) i otrzyn1ać reprezentację Rozkład

(8. 17) 144

8.2. Matematyczna struktura teorii kwantowej

gdzie P1, ... , P,t

są

operatorami rzuto\vymi na podprzestrzenie \vlasne odpo\viadające \vartościom \Vłasny1n .>.;, ... , .>.:,•. Łal\vo się przekonać, że reprezentacja spektralna (8.17) jest jednoznaczna.s Przypomnijmy, że wszystkie wektory własne na l eżące cło różnych 'vartości \vłasnych są ortogonalne, a co za tym idzie, 'ń1szys tkic operatory rzuto\ve \V reprezentacji (8.17) są rzuta1ni na \VZajc1nnic ortogonalne podprzestrzenie. Dlatego dla do\volnych i, j, takich że i-/= j, zachodzi P;Pj = O. Wynika z tego, że jeżeli p jest \viełomianem, to

pCD =p(>..;)P1 +. + p(>..:,.)P,t .

(8.18)

„

Równanie (8.18) można uogólnić: jeżeli f: JR • C jest dowolną i (8.17) jest spektra l ną reprczcntacji1 operatora T, to definiujemy

J(n =ft>..~ )P, +

„

.

+ft..>.:,,)P„,.

funkcją

(8.19)

8.2.2. Operator identycznościon'.Y I E L(H„) jest zdefinio\vany przez \Varunck lx = x dla każdego x E H„. Operator I jest \V tl)l\Vialny sposób samosprzężony, a jedyną jego \vartością \Vłasną jest J. Ponadto przestrzenią \vłas­ ną I jest ocz)"viście cała przestrze11 H„. Dlatego też, aby znaleźć reprezentację spektra ln ą I , \V)'Starczy u stalić dowolną bazę ortono rn1alną {x 1, ••• , x„ }. Wtedy mamy Przykł ad

l = lx1)(x1 I + ... + jx„)(x„j,

co nietrudno Pr.tykł ad

(8.20)

pokazać.

8.2.3. Łal\vo

spra\vdzić, że

macierz

definiuje w przestrzeni H i od\vzoro\vanie samosprzężone. Macierz M~ jest niezdegenero\vana, a jej 'vartościami własnyn1i są I i - 1. Jako odpo,viadają­ ce tym \Vartościom ortonormalnc 'vcktory \Vłasne n1oże1ny \vybrać na przykład x 1 = ~(I, l)T oraz x_ 1 = ~(I, - I )T_W prosty sposób można pokazać, że reprezentacje macierzo,ve obu operatoró'v rzuto,vych jx.,.1)(x±1I n1ają postać odpowiednio I

I

2 2 I

„

I

oraz

2 2 8 Niek16n~y

aulorzy rcprczcnlacją spektra lną (8. I 7). a nic rcprczcnlację (8.16).

nazywają jednoznaczną reprezentację

145

8. Dodatek A. Fizyka kwantowa

Reprezentacja spektralna M~ ina zate1n

I) = I . I O (O Dzięki

„

\yY

I

I

2 2 I 2

I

I 2 I

- I .

- -2I I 2

2

2

tej reprezentacji,

postać

możen1y obliczyć

na

przykład

picnviastek kwadrato-

zM ,; I

I

1

2 2

Podsta\viając teraz

y1l = I oraz

1

- -2I

I

2 -2

2 2 I

I

2

Ff =i, otrzymujemy macierz z przykladu

2.2.1. U,vzględniając \Vszystkie możłi,vc picnviastki, dostajen1y cztery różne n1aeierze X, spełniające \Varunek X2 = M~ .

8.2.4. I Reprezentacja spektralna operatorów unitarnych Zajmiemy się teraz funkcją e;r, zdefiniowa ną na operatorze samosprzężo11yn1 posiadaj.J!x1)(xil + . .. + >.„!x„)(x„I.

Z definicji e;r = eiA, lx1){x1I+ ... + eiA·lx„)(x„I. (c;r) = c- a, lx1){x1I+ . . . + e i,\,lx„)(x„I = (en)- 1, co oznacza, że operator c;r jest unitarny. Pokażemy teraz, że każde odwzoro\vanie unitarne inożna przedstawić \V postaci c;r, gdzie T jest operatorem san1osprzc;żonyrn. W tym celu udo,vodniiny pornocnicze twierdzenie, które sa1no \V sobie także jest interesuj-1 la1){a1I + ... + >-11lan){a11I

oraz

B = µJ!a1){ar I+ ... + µ11 la11)(a„I. 146

możemy przedsta,vić \Vpostaci

8.2. Matematyczna struktura teorii kwantowej Stąd

AB= -A11tda1 }(ad + ... + .A„µ„ la„)(a„I =BA. = BA. Niech .A 1 , ••• , -A1r bt;:dą różnymi \vartościami \vła­ snymi operatora A oraz niech {a~k) , ... , a!!~ } będą ortonorn1alnyoli \vektorami Załóżmy zatem, że AB

\vłasnyn1i odpo,viadającym i \Vartości własnej Ak. Dla dowolnego a~k) mamy

ABa\kl I

=BAa=B.Ą•.a =.Ą •.sa~kl I

"1

l'

11;

tzn. Ba~kl jest także wektoren1 włas nym operatora A nałcżącyn1 do wartości \vłasnej Ak. Dlatego podprzestrzeń \vłasna Z\viązana z Ak jest zamknii;:ta ze ,vzgłędu na 8. Podprzestrzeń tę oznaczymy przez ~Vt. Operator B: Wk -+ Wk. będąc ograniczeniem operatora san1osprzężonego, także jest samosprzężony. Dlatego B posiada 111k 'vektorów \vłasnych {b~4 > , ... , t\vorzących ortonormałną bazę podprzestrzeni Wk. Znajdując taką bazę dla każdej podprzestrzeni Wk, otrzymujemy ortonorn1ałny układ \vektorów \Vlasnych o następu­

h!!:},

jących \vłasnościach:

• Każdy wektor b~kl jest \vektorcm \vlasnym operatorów A i B (\v przypadku operatora A, b~k> jest wektorem własnyn1 odpowiadającym wartości własnej .Ak)· • Jeżeli i 'f j, to wektory b~kl i b)kl są ortogonalne, gdyż n a leżą do bazy ortonormalnej rozpinaj..k oraz AJt. Tak 'vięc otrzymany układ 'vektoró'v jest ortononnalną bazą przestrzeni H„ i jednocześnie zbiorem \vektoró\v \Vłasnych obu operatoró'v A i B. O Niech U będzie operatorem unitarnym. Zau\vaż111y najpief\v, że \vartości bez\VZgl ędne 'vartości \vłasnych operatora U ró,vne są 1. Aby się o tym przekonać, załóżmy, że x jest \vektorern własnym odpowiadającym \vartości \vła­ snej >.., tzn. Ux = .Ax. Wtedy

(xlx) =(xlU*Ux) =(UxlUx} =(>..x!>..x) =IA.l2 (xlx), z czego wynika, że I-Al = !. Rozłożyn1y

teraz operator U na

„część

rzcczywist O. Aby oszacować (8.26), skorzystan1y z t\vierdzcnia M. Ricsza [73] przytoczonego poniżej. 16 Jeżeli T: H„ -> H„ jest 1nacierzą unitarną, y = Tx oraz l ~a~ 2, to Nasz plan polega na

(

a)":'

~ L..,, IY;la=-r

zastąp i eniu

~

)~ c"l -a (~ L..,, lxd" ,

1= 1

1=1

gdzie c = n1ax ITii I· Wybierając x;

= (adx) oraz Tu = (bdaj), otrzy1nuje1ny Y; = (b;lx). OclY'viście

operator T jest unitarny. łl

a

l

Możerny Ił

teraz t\vicrdzenie Riesza zapisać w postaci I

(f,; l(b;lx) ln21 ) " ( f,; !(a;!x)!") -" ~ c ~· . 2

(8.29)

PO\vyższa nierówność

bctdzic także spelniona, gdy jej obie strony podniesien1y do potęgi k > O. Postaramy się usta lić wartości paran1etrów \V taki sposób, aby lewa strona nierówności (8.29) przypon1 i nała pra\vą stronę równania (8.26). Riesza jest szczególnym przypadkien1 fonuuły interpolacyjnej Steina. Elementarny dowód podany przez Riesza (73] oparty jest na ni~równości Holdera.

16 Twierdzenie

159

8. Dodatek A. Fizyka kwantowa

Tak

\Vięc

szukamy takich liczb r, s i k, k

a= 2(r + 1), - -a

= -Ir

2- a

oraz k a

=2.

że

a (I -

Aby 1

~

I a

=2(s + 1), ~

a-I

k a

wybrać

2, musimy

2

= s'I

r E [- ~,O]. Prosty rachunek pokazuje, że wystarczy przyjąć s = - „ ~ 1 oraz 2 +2 A . ' ' ' (8.29) mozemy . . ' \V postaci. „ . zaten1 n1ero\vnosc przcp1sac k=-

„

(

1

~ s+I) }(~ r+I) : :::::,., c2, L., Cf; L., P; i= 1

co przy r

i= 1

-+

Odaje szukane oszacowanie.

o

Uwaga 8.3.3. Dolne ograniczenie w l'.vierdzeniu 8.3.3 nie zal eży od stanu ukła­ du x, może jednak za leżeć od reprezentacji obserwabli A= >.J!a1 )(a il + . . . + >.„la„)(a„j

oraz B = µ J! b1)(b il + .. . + µ„l b„)(b„ j. Niezależność

od reprezentacji otrzy111uje111y, jeżeli obie obser\\'able są niezdegenerowane. Wtedy 1vszystkie 1vektory a; oraz b; są wyznaczone jednoznacznie, z dokładnością do stałej multiplikatywnej o \Vartości bezwzględ nej ró1vnej 1. Stąd także c = 111ax l(b;jaj)I jest \vyznaczone jednoznacznie. Zatl\vażmy, że \V przypadku degeneracji obsenvabli liczba \vartości, które da się zaobserwować, jest mniejsza od n, co w naturalny sposób powoduje 1vzrost entropii. 8.3.3. RoZ\vażmy układ złożony z 1n kubitó\v. Pierwszą bazą ortonorn1alną będzie znana nam baza obliczeniowa B1 = { lx1 . . . Xm } : X; E {O, I}}. Drugą bazę 82 = { Hlx) : lx) E 8 1} otrzymuje1ny, poddając bazę 8 1 transformacji Hadan1arda-Walsha (patrz podrozdziały 4.1.2 i 9.2.3): Przykład

Będzie1ny

badali obsenvable A1 i A2, \vyznaczone przez bazy 8 1 i 8 2:

A;= l: c~)lx}(xl . xEB;

Wartości c~) nie są dla nas \Vażne i m ogą być ustalone \ V dowolny sposób, tak

aby oba ciągi c~' złożone były z 2"' różnych liczb rzeczywistych. Istotne jest

8.4. Stany kwantowe jako operatory

przede \vszystkim to, aby obserwablę traktować jako rozkład przestrzeni H 2., na 2111 wzajen1nie ortogonalnych podprzestrzeni jednO\vymiarowych. Łatwo spra,vdzić, że dla do,volnych lx) E B1 i lx') E B2 zachodzi j(x jx')I = Stąd

~·

na mocy entropowej zasady n ieoznaczoności (twierdzenie 8.3.3) mamy

H(A 1) + H(A2)

~ 111 .

Oznacza to, że suma nieoznaczoności obsenvacji 11i-kubito,vego stanu w bazach 8 1 i 8 2 wynosi nie n1niej niż 111 bitów! Z drugiej strony, nieoznaczoność pojedynczej obserwacji nie może być oczywiście większa niż 1n bitów: obserwacja względem do,volnej bazy daje ciąg x = x 1 ... x,,, E {O, I }111 z prawdopodobieńst\van1i p, takin1i, że

L Px = 1. Entropia Shannona dana jest przez

xeir; - LPx logpx XE~

i osiąga n1aksimum gdy p, =

;mdla każdego x E {O, I }

111 ,

a zatem maksymal-

na nieoznaczoność 'vynosi 1n bitów. Dolne ograniczenie \vystępujące w zasadzie nieoznaczoności (m•ierdzenie 8.3.2) zależy od komutatora [A, BJ oraz od stanu lx). Jeżeli [A, B] =O, to ograniczenie to jest trywialne. Czy dla entropo,vej zasady nieoznaczoności jest podobnie? Odpowiedź jest pozyty\vna. Jeżeli operatory A i B komutuj ą ze sobą, to zgodnie z lematem 8.2.9 mają one \vspólną bazę złożoną z ortonormalnych wektorÓ\V \Vłasnych. Wtedy jednak c = max l(b;jaj) I = I i dolne ograniczenie jest oczyv;iste.

8.4. I Stany kwantowe jako operatory Przyjrzyjn1y się

układo\vi

)z C

..

® (X1 „t2, ... ,X11") =

.:r,,

lx11 2 X1Xi 2 X2X1• lx21

X1x;;

„t,,„'( X11 Xi

lx„ 12

XzX:,

U\vaga 8.4.2. Także w przypadku macierzy g taką że p; należy do stanu lx;)) istnieje wtedy i tylko wtedy, gdy istnieje operacja fizyczna pozwalająca na \vyt\vorzenie stanu lx;) z dodatkowej inforn1acji p;. Przyjn1ując P1 = . .. = Pk = p, otrzy1nuje1ny klasyczne t\vicrdzcnie o nieklono\vaniu Woottcrsa i Zurka (t\vierdzenic 2.3.1). Do,vód. Jeżeli istnieje odwzoro\vanie V' E L(H„ ® Hm) spełniające \varunck

V'(IO)(OI ® p;) = lx;)(xd ® p;', to szukane od\vzoro\vanie V 1nożna tat\VO otr.i:ymać jako rozszerzenie. Załóżmy zatem, że istnieje od\vzorowanie V o własnościach podanych w za ło­ żeniach. Z len1atu 8.4.3 \yYllika, że każdy stan p; E Hm można przedstawić jako \vynik częścio\vej operacji śladu \yYkona nej na stanic czystym, \vyznaczonym przez \vektor y; E H,,, ® H,,,. Ponadto, na mocy l\vierdzenia 8.4.7, istnieje otoczenie H 0 , takie że V może być interpreto\vane jako Od\vzoro\vanie unitarne \V przestrzeni H„ ® H„ ® Hm® Hm® Ho: U(x; ® O® y; ® o)= x; ® X;® Z;,

gdzie o E H0 , a z; E H,,, ® Hm ® H 0 • Ponieważ U jest unitarne, wykorzystując lcrnat 8.2.5, 1namy, że dla każdego i,j E {I, .. . , k}

(x; ® 0 ® y; ® ojxj ® O® Yi ® o) = (x; ® X; ® zdxi ® Xj ® zj) . Ró\vnanie (8.63)

można zapisać \V

(8.63)

postaci

(8.64)

188

8.4. Sta ny kwantowe jako operatory

Z założenia zawsze mamy (x;lxj) -I O, a

\Vięc

(O© Y; © o!O© Yj © o)= (x; © z;l xj © Zj)

(8.64) daje (8.65)

dla każdego i,j E { 1, . . . , k} . Z lematu 8.2.8 'A'Ynika, że istnieje unitarne odwzorowanie U' E L(H11 ® Hm ® Hm® H0 ), takie że dla każdego i E {I, .. . , k}

U'(O® Y; © o)= x; © z;. Szukane od\vzorowanic V' otrzymujemy przez wykonanie operacji śladu \VH0 i drugiej kopii Hm . O Zasada nieusu'A1 al ności, sfo rn1 ułowana przez Patiego i Braunsteina (66], brzrn i n astępująco: jeżeli x 1, • •• , xk nie za\viera stanó\v ortogonalnych, to nie istnieje operacja fizyczna poZ\val ająca na usunięcie kopii x;. Oznacza to, że nie jest n1ożliwe (w rozu1nieniu następnego twierdzenia) wykonanie operacji

jx;)lx;) W na

>-+

jx)IO).

rzeelY'vistości istnieje n1ożliwość wykonania operacji usu\va nia: n1 ożna przykład, jak wskazano w pracy (66], u\vzględnić otoczenie i zdefiniować

.

operację

jx;)lx;) jo) ,_. jx;)IO)jo;), która w gruncie rzeczy polega jedynie na wymianie pon1iędzy otoczeniem a drugą kopią stanu x;. W takiin przypadku stan x; zostaje zachowany \V otoczeniu i n1ożna go dokładnie odtworzyć. Z drugiej strony, operacja wymaz)"vania jest wykonalna, j eżeli pFL)ljmiemy postula t rzutowania. Wystarczy wtedy dokonać obse1wacji drugiej kopii stanu lx;) lx;), a następnie zamienić stan wyj ściowy na IO) (48]. Twierdzenie 8.4.9 (Zasada nieusuwalności) . Przyjmijmy, że x 1 , ••• , x k E H 11 oraz O E H11 są określo ne jak \vyżej . Jeżeli istnieje całkowicie dodatnie odwzoro\vanie usu,vające d rugą kopię X;, tzn. Od\vzorowanie, dla którego speł nione jest

lx;)(xd ® lx;)(xd ,_. lx;)(xd ® jO)(OI,

„

to wektory X; n1ożna całko\vicie odtworzyć z otoczenia. Dowód. Za tóżn1y, że istnieje całko\v i c i e dodatnie odwzoro\vanie speł niające założe n ia hvierdzenia. Na mocy nvierdzenia 8.4.7 istnieją: przestrzeń H 0 , \vektory o, 01 , . .. , Ok E H0 oraz unitarne odwzorowanie U E L(H11 ® H11 ® H0 ), spełniające

U(x ; ® x; ® o)=

x; ® O® o;. 189

8. Dodatek A. Fizyka kwantowa

Z lematu 8.2.5 wynika, że dla każdego i,j E { 1, . . . , k}

(x; 0 X; 0 olxj © Xj© o) = (x; 0 0 © o;Jxj © 0 0 oj), co

n1ożna zapisać

jako

(x;Jxj)(x; 0 ojxj 0 o) = (x;jxj)(O0 o;jO0 Oj) lub (8.66)

(x; 0 ojxj 0 o)= (O0 o;JO0 Oj)-

Len1at 8.2.8 stwierdza, że istnieje unitarne od\'1zoro,vanic U' E L(H11 0 H0 ) , takie że dla każdego i E { I,. . „ k}

U'(x; 0 o) = 0 © o;. Ponieważ

U' jest unitarne, więc istnieje odwzoro\vanic od\vrotnc do niego, O a zatem istnieje możli\vość odzyskania z otoczenia stanów X;.

±] Zadania 1.

Pokaż, że

wynik operacji brania śladu

li

Tr(A) =

L (x;!Ax;) i=I

nie za leży od \vyboru bazy ortonormalnej {x 1 , • . • ,x11 } . 2. Pokaż, że jeżeli P jest operatorem samosprzężonym H„ istnieje podprzestrzeń W E H," taka że P = Pw.

-->

H„ i P 2 = P, to

3. Niech >- 1, •• • , .>- 11 będą \vartościami własnym i samosprzężonego operatora A, a { x1, .. . , x11 } ortonormalnyn1 zbioren1 odpo\v i adaj ących in1 wektoró\v wlasnych. Sprawdź, że A= >- dx1)(xd + ... + >-11lx11)(x11I ·

4. Wykaż

pra\vdzi\\1 0ść tożsamości

polaryzacyjnej

3

(xly) =

! L / (y + / xiy + / x). k=O

Posługuj ąc s ię

tym równaniem, pokaż, że jeżeli llAxll = llxll dla dowolnego x E H11 , to dla wszystkich x, y E H11 zachodzi (AxlAy) = (xly).

190

8.5. Zadania

5. UdO\vOdnij, że

.>..(ix1 )(x1 I + lx2)(x2D = .>..(lx~ )(x\ I + l x~ )(x~ I), gdzie I

= X1 COS O: -

I

.

X1

.

X2 $111 O:,

X2 =X ) Sin Cl'. + X2 COS O:,

a o: jest liczbą

rzeczywistą.

6. Udo\vodnij, że dla dowolnych x, y E H„ i A, 8: H„ IAx)(Byl =Alx)(ylB' . 7.

Opierając się

--->

H„ zachodzi ró\vność

na ró\vnaniu

p(t) = U(t)p(O)U . (t)

i reprezentacji U(t) =

e - iiH,

\vypro\vadź uogólnione ró\vnanie Schrodingera

1 t 1l

i ' p(t) = [H, p(t)).

„

9 Dodatek B. Podstawy matematyczne Celern tego rozdziału jest zaznajo111ienie czytelnika z podsta\vO\vy1ni pojęcia­ mi matematycznyrni wyko rzysty\vanyn1i w książce.

g.1.1 Teoria

gru p

l.1J Wiadomości wstępne Grupą

G nazywamy zbiór z od\vzoro\vaniem G x G

G, tzn. z reguh1, która jednoznacznie opisuje, w jaki sposób z pary uporządkowanej (g 1,g2 ), gdzie g 1 ,g2 E G, ut\vo rzyć elen1ent g E G. Działa nie to często nalY\vane jest 111110 żeniem lub doda\vaniem i oznaczane odpowiednio g = g 1g 2 lub g = g, + g2 . -'>

Ponadto wymaga si ę, aby grupa za,viera ła wyróżniony element, nalY\vany elementem jednostko,vym lub neutralnym. Element neutralny oznaczamy przez 1 (w notacji multiplikatywnej) lub O('v notacji addyty\vnej). DodatkO\VO n1usi istnieć operacja, która każdy element g E G przeprowadza w jego element od,vrotny f? 1 (\v notacji addyty\vnej element przechvny - f?). Działania określone \VG muszą spelniać następujące aksjomaty grupy (w notacji n1ultiplikaty,vnej): 1. Dla dowolnych elen1entów 81, 82 i 83, 8 1(g2f?3) = (g1g2)f?3. 2. Dla każdego g, g I = lg = g. 3. Dla każdego g, gg- 1 = g- 1g = I. Jeżeli dodatko,vo spełniona jest wlasność 4. Dla dowolnych elementó\v g1, 82, 1?182 = 828 1, to G naz)'\vamy grupą abelo,vą lub przemienną . 1 Ściśle biorąc, grupą pow in niśmy nazywać czwórkę (G, , I), gdzie G jest zbiorern elementów gru py, · oznacza mnożenie, -I od\vrotność, a l element neutralny. Jeżeli jednak nie będzi e to pro,vadziło do nieporozumień , to symbolem G będziemy oznaczać zarówno grupę jak i sam zbiór.

„-

Przykład

9.1.1. Zbiór liczb ca łko\vitych Z z dodawaniem jako działan iem grupo,vym t'.vorzy grupę abelową; Ojest elementem neutralnym, a odwzorowanie n ,...... - n od\vrotnością. Z drugiej strony, zbiór liczb naturalnych N ={ L, 2,3, . . . }

z tymi samymi działaniami nie tworzy grupy, gdyż po pienvsze N nie Jest zamknięty ze \VZględu na ochvrotność n ,...... - n, a po drugie w N nie istnieje cle1nent neutralny.

192

9.1. Teoria

rup

Przykład

9.1.2. Zbiór liczb zespolonych bez O tworzy grupę abelową wzglę­ dem mnożenia. Elernentem neutralnym jest 1, a odwzorov-+ z- • jest odwrotnością.

Przykład 9.1..3. Zbiór nieosobliwych macierzy (tzn. takich, których wyznacznik jest różny od O) nad C o wyn1iarach n x n t\vorzy grupę ze względ u na mnożenie rnacierzy. Grupę tę nażywa się grupą linio,vą nad C i oznacza się

ją

przez GL,,(C). Nie jest to jednak grupa abelo\va, chyba że n·= I i \vtedy n1amy do czynienia z grupą z poprzedniego przykładu. Wracając do aksjomatów grupy, z u\vagi na pie1wszy \Varunek możemy opuszczać nav;iasy i p isać po prostu g 1g2g3 = gi (g2g3) = (g1g2)g3. Ocz}'\v iście U\vaga ta jest słuszna ta kże dla iloczynó\v za\vie raj ących więcej n iż trzy elen1enty. Iloczyn g . .. g (k razy) biydzicmy oznaczać przez (kg \Vnotacji addyty,vnej). Definiujemy także g0 = l oraz g- k = (g- 1) k (Og = O, - kg = k(- g) w notacji adddytywnej).

t

9.1.2. I Podgrupy, warstwy Podgrupą

H grupy G nalY\vamy grupę za\va rtą ·w G \V następuj ącym sensie: H zawiera siiy v.1 G jako zbiór, a działa nia grupowe (iloczyn, odwrotność i element neutralny1) są działaniami w G zawężonymi do zbioru H. Fakt, że g1upa H jest podgrupą grupy G oznaczan1y przez H ~ G.

Przyjmijn1y, że H jest podgrupą n1ultiplikat}'\vnej grupy C. Warsnvą grupy G \vzględem podgrupy H (\vyznaczoną przez element g E G) nazywan1y zbiór (9. 1)

gH = {gh : h E H}.

Podamy teraz kilka prostych, lecz użytecznych u\vag. Po pierwsze, każdy element g E G należy do jakiej ś warst\vy, na przykład do gH. Jest tak, gdyż H jako podgrupa zawiera elen1ent neutralny 1, a zaten1 g = gł E gH. Wynika stąd, że \Varstv. y \vzględen1 danej podgrupy H pokrywają całą grupiy G. Zauważ1ny, że w szczegó lności dla dowolnego h E H nian1y hH = H, gdyż H jako grupa jest zamk nięta ze \VZględu na n1noże nie i każdy elen1ent h 1 E H należy do hH 1

('11 = h(h- 1h1)). Pozostałe

uwagi \V)•razirny \Vforn1ie

n astępujących

lemató\v. 1 Lemat 9.1.1. g1H = g2H wtedy i tylko wtedy, gdy g; g2 EH. Do\vód. Jeżeli g 1H = g2H, to musi istnieć h E H takie, że g2 = g ,h. Stąd 1 1 g ; g 2 = h E H. Z drugiej strony, jeżeli g ; g2 = h E H, to g2 = g1H, a zaten1 g2H=g1hH = g1 H.

O

1

1

U\vaga 9.1.1. Zau\vażmy, że g; g2 E H wtedy i tylko \Vtedy, gdy g; g1 E H. Jest tak dlatego, że H zawiera odv.1 rotno~ 1 dla pewnego i oraz takiego /(, że k = /( K'. Ale \vtedy IĆ !(' + 11;'Ł = k + n;'Ł ~ z:,. Wynika stąd , że

a zatern

1.p(111) · ... · 1.p(11r) = 1z;,, 1· .. . · IZ7.,I = 1z;,, 198

x ... x

Z7,,I = 1z;,1=1.p(n).

Teraz n1 oże1ny j uż policzyć rząd grupy Z7i: niech /1 = p~' · . .. · p~' będzie rozkladen1 liczby /1 na czynni ki pier.vsze, p; /; Pj dla i/. j. Wtedy a' )

•.. E9 Gm. W tyrn celu załóżmy, że Xi, ... , Xm są charaktera rni G1, ... , G,,,. Pon ieważ C = G1 E9 ... E9 Gm, każdy elernent g E G można jednoznacznie przedsta\vić ·w postaci Dowód. Z

~

9.2.l wiemy,

~

że

~

g =g1+ . .. +g„„ gdzie g; E C;. To pozwala nam na zdefinio,vanie funkcji

x:G _, C \ {O} jako (9.7)

teraz zobaczyć, że x jest charakterem G. Ponadto, jeśli nieje element g; E G;, taki że x ;(g;) f X;(g;). Stąd Łat\vo

xj f X;, to ist-

x'(g;) = x 1CO) . . . x;(g;) . .. x,,,(O)

f

X1(0) · · · X;(g;) · · · Xm(O) = X(g;),

co oznacza, że charaktery C zdefiniowane ró\vnaniem (9.7) są różne dla róż­ nych Xi, .. . , Xm· Z drugiej strony wszystkie charaktery G mogą być wyrażone ró,vnaniem (9.7). A zatem, jeżeli X jest charakterem G, to r11ożen1y zdefiniować X; przez zawę­ żenie x do G;. Łat\vo teraz st\vierdzić, że każdy X; jest charakterern G; oraz X = X1 · · · Xm· O Aby zil ustrO\\•ać

pojęcie

charakteru, omówin1y teraz kilka przykładów.

Przykł ad 9.2.2. Rozważmy IF'~', 111-\vymiarową przestrzeń \vektorową nad eiałen1

liczb dwójko,vych.

Każdy elen1ent \V

\vi~c

grupa IF'~' nia rozkład:

addyty\vnej grupie IF'~' ma

rząd

2, tak

111 składnikó\V

Teraz pozostaje 'vyznaczyć charaktery IF'2,

gdyż

na mocy lematu 9.2.1 charak-

tery IF'~' są po prostu 111-krotnyrn iloczynern charakterów JF2 . Ale charaktery IF'2 = Ł2 znaleźliśmy już \V przykładzie 9.2.1:

1203

9. Dodatek B. Podstawy matematyczne

dla y E {O, l}. Zatem Xy(x)

=(- 1yl)·• ·

każdy

„

. · ( -

charakter ~,

=(-

I f • >;.,

można zapisać \V

postaci

1)'''',

gdzie x · y = x 1y 1 + ... + x111 y,,, jest Z\vykłym iloczynem r61v X= (Xi, ... ,X111) i y = ()'1 •... •Y111).

1vewnętrznym

wekto-

9.2.2. J Ortogonalność charakterów będzie skończoną grupą abelo1vą.

Funkcje f: G -+ C l\vorzą przestrzeń 1vektoro1vą V nad C z doda1vaniem i mnożeniem przez skalar zdefinio1vanymi punkto1vo: (.f + h)(g) = f(g) + h(g) oraz (c · f)(g) = c · f(g) (patrz także podrozdział 9.3). O przestrzeni V możen1y nlyśleć także 1v inny sposób: każda funkcja/: G--+ C może być postrzegana jako n-tka Niech G = {g 1, ••• ,g11 }

(fg ,•. .. •fg.) = (f(g, ), . .. ,/(g„)).

(9.8)

Widać 1vięc, że przestrzeń

V ma wymiar 11. Naturalną bazą V są 1vektory (O, I, .. . , 0), ... , e„ (0. O, ... , I). Innymi sło1vy e; jest

e1 =( I, O, ... , 0), ei = funkcją G --+ C zdefinio1vaną jako

=

. . _ { I jeżeI i i = j ,

c,(g, ) Zwykły

O 1v prz.cci1vnyn1 przypadku.

iloczyn we1vnętrzny na przestrzeni V zdefinio1vany jest jako li

(/ Jh) = L,.f(g;)h(g; )

(9.9)

i=ł

i 1v naturalny sposób \\'YZnacza on

norn1ę

111111 = ·/(hjh).

Baza {e1, • •• , e„} jest

oczywiście

we1vnętrznego. Inną bazą

Lemat 9.2.2.

Jeżeli

(X; IXi ) -_ { 11O

ortogonalna względem zwykłego iloczynu ortogonalną jest baza charakteró1v.

X; oraz Xi

jeżeli

są

charakterami G, to

i"'j ,

(9.10)

jeieli i = j .

Dowód. Po pienvsze, warto zau1vażyć,

iż

2

1 = Jx(g)J = x · (g)x(g),

z czego 1vynika, że x •(g) = x (g) - 1 dla każdego g E G. Wó1vczas li

li

(x;l'X.i) = L A- 1

204

xi(gk)Yj(gk) =

li

L x; (gk)Xi(g,) = 'L, k- 1

_ {O - n

k= I

jeżeli i jeżeli

fe j,

i = j,

co w istocie oznacza, że X"X =ni, czyli x- 1 = ~x·. Ponieważ jednak każda 11

macierz komutuje z macierzą do niej a to można zapisać jako

odwrotną, \vięc

mamy

także

XX* = nl,

(XX");; = { no jeże l i i fe j, , jeżeli i = j,

lub

też li

I: Xk(g;)xi:(gj) = { ~ k- 1

jeże li i jeżeli

f

j, i = j.

(9.ll)

205

9. Dodatek B. Podstawy matematyczne

Równania (9.10) oraz (9.11) znane są jako relacje ortogonal ności charakterÓ\V. Zauważn1y także, że wybierając \V (9.10) Xj jako charakter trywialny, a w (9.11) gj jako e le1n e11t neutralny, otrzymujemy u żyteczne stwierdzenie: Stwierdzen ie 9.2.1. li

X(gk) =

L

jeżeli

x jest charakterem tryv1ialnyn1,

{o w przeciwny1n przypadku.

(9.12)

k= I li

LXk(g) =

jeżeli

g jest ele111enten1 neutral nyn1, \V przeciwnym przypadku.

{o

(9.13)

k- 1

w;•zachodzi syrnetria X;(gj) = Xj(g;), a zaten1 dla obu grup

W gtupach Z„ oraz

możemy powyższe zależności zapisać za pomocą jed nego

ró,vnan ia. W Z 11 mamy

jeżel i

x =O, w prleciwnyn1 przypadku,

a \ V •r"""'2

~( -

I )''l' = {

6"'

jeżeli \V

x = O, przechvnym przypadku.

)'€ ~"2

l.2.3. I Dyskretna t ransformata Fou riera Dysponujemy teraz wszystkimi 3rodkami potrzebnymi do zdefiniowania dyskretnej transformaty Fouriera. Do,volny clc.rncnt f E V (przypomnijmy, że V jest przestrzenią wektoro\vą funkcji G --+ C) posiada jednoznaczną reprezen-

tację \vzględe111 bazy B = ~

Jnx1 .... , Jnx11 }:

{

~

f=f1B1 + ... +J,,B„.

(9.1 4) ~

Definicja 9.2.1. Funkcj C, (x, y) .._, (xly) spełniające dla wszystkich c E C oraz x, y, z E V następujące \varunki 1. (x ly) = (ylx)•,

2. (xlx) ; (1 + d;)r;

2r;. A zate1n

> y > r, > 2r3 > 4r5 > ... > 2' r2;+1 · n. jest nieparzyste, to x n- 2

x > 2 -i- „„_, > 2 Wyn ika stad, n

~

że

2 < 1og,o (f(x) + 2

n-1 i

n

> 2 --i

r,„ a zatem

I

r„ ~ 2 --r . D la n parzystego mamy

nierówność

f.(x) = llog ioxJ

11 - I

it - 2

x > 2 -r jest zawsze

> log 10 x -

I

>

I) + 2 = O(f (n )). Wnioskujemy

11 ;

2

spełniona.

logro 2 - 1 i dalej

więc, że

dla liczb x

>y

rnożna obliczyć nwd(x, y), wykonując 0(f (x) 3) elementarnych działań arytmetycznych.

9.4. Teoria liczb

9.4.2. J Ułamki łańcuchowe PrLykłacl

9.4.1. Zastosujmy algorytm Euklidesa do pary (263, 189):

263 = I · 189 + 74. 189=2·74+41, 74 = I · 41 + 33, 4 1 = 1 . 33 + 8. 33 = 4. 8 + 1. Obliczenia kończyn1y w następny1n kroku, zn ajdując nwd(263, 189) = I. Dzieląc każde z po\vyższyeh równań, 01rzyn1l1je111y 263

74 1 1119= +189' 189

41

74

33

74 = 2 + 74'

4T = I + 41' 41 8 33 = I + 33' 33

I

s=4+sZau,vaż1ny, że ulamek \\'YStępujący po prawej stronie jest odwrotnością ułam­ ka znajdującego się po lewej stronie następnego ró\vnan ia. Stąd, \rykonując

kolejne podstawienia, otrzymujemy 263

I

189 = l + - - -- , - -

(9.25)

2 + - - - , .,- -

l+ - - 1l+

I

4+ 8 Wyrażenie

(9.25) jest przykładem skończonego ułan1ka ł a ńcucho,vcgo. W ten sposób można oczywiście rozwinąć każd.x 1 +(I - >.)x2) ;;o >.j(x1) +(I - >.}/(x2) dla AE [O, I) ix1,x2E l.

227

9. Dodatek B. Podstawy matematyczne

Dowód. Najpierw dowiedziemy wyniku pomocniczego: jeżeli f jest rosnącą. nieujcn111ą fu n kcją określoną na liczbach naturalnych, taką żef(.s"') = 11if{s), to fl.s) = Klogs dla pewnej dodatniej stałej K. Wyb ierzn1y do\volną liczbę naturalną n i ustaln1y 111, takie że sm ~ 2" < s111 +1 . Wtedy ~ & log2 '' '== log s