Wprowadzenie do algorytmów kwantowych

autorzy :  Krzysztof Giaro, Marcin Kamiński

format :  B5
objętość :  168 str.

ISBN  83-87674-57-5

Streszczenie
Spis treści



STRESZCZENIE

Pomysł budowy komputera, który działałby zgodnie z prawami fizyki kwantowej i w sposób istotny wykorzystywał te prawa, ma niemalże dwadzieścia lat. Przez ten czas prowadzone były zarówno badania teoretyczne, jak i prace nad konstrukcją komputera kwantowego. Jakkolwiek postęp w dziedzinie technologii jest znaczny, to nie dysponujemy jeszcze maszynami liczącymi, których działanie trzeba wyjaśniać na poziomie fizyki kwantowej. Podejmowane dotychczas próby konstrukcji należy nazwać eksperymentami.

W dziedzinie badań teoretycznych osiągnięto szereg ważnych rezultatów. Opracowano model obliczeń kwantowych, podano pierwsze algorytmy i stworzono teorię ich złożoności obliczeniowej. Z tych pierwszych studiów wynika, że komputer kwantowy może rozwiązywać pewne zadania szybciej niż maszyny klasyczne. Brak jednak dokładnych wyników, a siłą napędową dalszych badań jest nadzieja, że problemy, których nie można efektywnie rozwiązać w modelu klasycznym, będą miały takie rozwiązanie w modelu kwantowym.

Celem tej pracy jest prezentacja kwantowego modelu obliczeń. Szczególny nacisk położono na zagadnienia matematyczne i informatyczne. Zadbano o wyjaśnienie podstaw teoretycznych, podanie pełnych dowodów poprawności algorytmów kwantowych oraz szacowanie złożoności obliczeniowej.


SPIS TREŚCI

Wprowadzenie

Rozdział I. Wprowadzenie matematyczne

I.1. Oszacowania asymptotycznego tempa wzrostu
I.2. Elementy teorii grup
I.3. Elementy teorii liczb
I.4. Pierścienie i ciała
I.5. Ułamki łańcuchowe

Rozdział II. Wprowadzenie do algorytmów klasycznych

II.1. Standardowe modele obliczeń i złożoność algorytmów
II.2. Proste procedury arytmetyczne

Rozdział III. Mechanika kwantowa

III.1. Przestrzenie Hilberta
III.2. Operatory liniowe
III.3. Postać macierzowa operatorów i wektorów
III.4. Wartości własne operatora
III.5. Interpretacja fizyczna

Rozdział IV. Obliczenia kwantowe

IV.1. Bit kwantowy
IV.2. Rejestry kwantowe

Rozdział V. Model algorytmu kwantowego

V.1. Sieć bramek kwantowych
V.2. Aproksymacja bramek kwantowych
V.3. Kwantowa maszyna Turinga

Rozdział VI. Zagadnienie Deutscha-Jozsa oraz problem Simona

VI.1. Problem Deutscha-Jozsa
VI.2. Problem Simona

Rozdział VII. Algorytm Grovera

VII.1. Problem szukania elementu w zbiorze
VII.2. Prezentacja algorytmu
VII.3. Omówienie algorytmu
VII.4. Realizacja algorytmu
VII.5. Analiza algorytmu
VII.6. Przypadek wielu rozwiązań
VII.7. Strategia uruchamiania algorytmu
VII.8. Nieznana liczba rozwiązań
VII.9. Ograniczenia procedur kwantowych z "czarnymi skrzynkami"

Rozdział VIII. Algorytm Shora

VIII.1. Rząd elementu modulo N
VIII.2. Probabilistyczny test pierwszości
VIII.3. Kwantowa transformata Fouriera
VIII.4. Kwantowy algorytm znajdowania rzędu elementu
VIII.5. Algorytm Shora
VIII.6. System kryptograficzny RSA

Rozdział IX. Inne zastosowania bitów i bramek kwantowych

IX.1. Kryptografia kwantowa - bezpieczne uzgadnianie klucza
IX.2. Stany EPR
IX.3. Teleportacja stanu kwantowego

Posłowie

Wykaz oznaczeń

Indeks

Bibliografia


Powrót do strony głównej  |   e-mail  |   Zamówienie