Algorytmy kwantowe

„Algorytmy kwantowe”, Mika Hirvensalo, Opis / Nota wydawcy / Synopsis

Książka wprowadza w dziedzinę obliczeń kwantowych. Zamieszczone w niej treści są przeznaczone zarówno dla tych czytelników, którzy dopiero rozpoczynają zgłębianie poruszanej tematyki, jak i bardziej zaawansowanych.

W publikacji wiele miejsca poświęcono omówieniu dwóch ważnych dla tej dziedziny algorytmów:
• algorytmu szybkiej faktoryzacji,
• algorytmu wyszukiwania Grovera.

Pozycja wyróżnia się spośród innych tego typu publikacji zastosowaniem podejścia informatycznego zamiast klasycznego ukierunkowania na fizykę. Książka jest napisana w sposób przystępny, zawiera wiele przykładów i ćwiczeń, które ułatwiają zrozumienie przekazywanych treści. Dzięki temu grono jej odbiorców może być większe: oprócz informatyków również specjaliści innych dziedzin, np. matematycy i fizycy.

---

Obliczenia kwantowe cieszą się w ostatnich latach ogromnym zainteresowaniem. Przyczyną tego jest fakt, że zastosowanie komputerów kwantowych stwarza nadzieję na znaczną redukcję czasu wykonywania obliczeń dla wielu praktycznych problemów, np. przeszukiwanie baz danych. W przypadku algorytmu faktoryzacji, mającego zastosowanie w kryptografii, istnieje nawet możliwość pokonania bariery wykładniczej złożoności obliczeniowej. Przewaga komputerów kwantowych nad klasycznymi ma swoje źródło w kwantowej równoległości obliczeń: informacja w maszynie kwantowej jest reprezentowana przez stany kwantowe - wektory z przestrzeni Hilberta, a obliczenia dokonywane są na superpozycji stanów. Oczywiste jest więc, że projektowanie i analiza algorytmów kwantowych wymaga z jednej strony biegłości w stosowaniu formalizmu matematycznego mechaniki kwantowej, a z drugiej strony gruntownej znajomości teorii obliczeń.

Książka Miki Hirvensalo Algorytmy kwantowe jest wprowadzeniem w dziedzinę obliczeń kwantowych z punktu widzenia informatyka/matematyka. Wychodząc od modelu klasycznej maszyny Turinga, autor omawia podstawowe zagadnienia teorii obliczeń, a następnie wprowadza model maszyny kwantowej. W dalszej kolejności szczegółowo analizuje przykłady potencjalnego zastosowania obliczeń kwantowych, m.in. algorytm faktoryzacji Shora oraz algorytm wyszukiwania Grovera. Ważną, z dydaktycznego punktu widzenia, częścią książki są dwa dodatki, stanowiące blisko połowę jej objętości. Zawierają one podstawowe pojęcia i twierdzenia fizyki kwantowej oraz wybranych działów matematyki, niezbędne do zrozumienia przedstawionych wcześniej algorytmów kwantowych.

Należy podkreślić, że dbanie o formalizm matematyczny pozwoliło autorowi na przedstawienie całości materiału w bardzo jasny i spójny sposób. Jest to dużą zaletą książki, gdyż zwykle język używany w tak odległych pojęciowo dziedzinach nauki, jak fizyka kwantowa i informatyka, jest znacząco różny. Z tego względu książka ta może być źródłem wiedzy dla osób niebędących specjalistami, w szczególności zaś dla studentów pragnących rozpocząć prace w tej nowej, dynamicznie rozwijającej się gałęzi informatyki. Z drugiej strony czytelnicy bardziej zaawansowani znajdą tu przegląd najważniejszych algorytmów kwantowych wraz z dokładną ich analizą.

„Algorytmy kwantowe”, Mika Hirvensalo, Dane Techniczne

• Algorytmy kwantowe
  Język oryg.: angielski, Tytuł oryg.: Quantum computing
• Autor: Mika Hirvensalo, Tłumacz: Paweł Zabierowski,
• Wydawca: Wydawnictwa Szkolne i Pedagogiczne Spółka Akcyjna
• Seria: idee, metody i narzędzia informatyki
• Kategorie: Nauki ścisłe, Podręczniki
• Identyfikatory numeryczne: ISBN: 83-02-09155-3
• rok wydania: 2004, wydanie: 1
• ilość stron: 244
• wymiary: 165/235 mm

„Algorytmy kwantowe”, Mika Hirvensalo, Spis treści

Przedmowa do wydania polskiego

Przedmowa do drugiego wydania

Z przedmowy do pierwszego wydania

1. Wstęp

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

2. Informacja kwantowa

2.1. Bity kwantowe
2.2. Rejestry kwantowe
2.3. Twierdzenie o nieklonowaniu
2.4. Obserwacja
2.5. Teleportacja kwantowa
2.6. Kodowanie supergęste
2.7. Zadania

3. Maszyny obliczeniowe

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

4. Szybka faktoryzacja

4.1. Kwantowa transformata Fouriera
4.1.1. Podstawy
4.1.2. Transformata 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
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

5. Znajdowanie ukrytej podgrupy

5.1. Uogólniony algorytm Simona
5.1.1. Wiadomości wstępne
5.1.2. Algorytmy
5.2. Przykłady
5.2.1. Znajdowanie rzędu
5.2.2. Logarytm dyskretny
5.2.3. Oryginalny problem Simona
5.3. Zadania

6. Algorytm wyszukiwania Grovera

6.1. Problemy wyszukiwania
6.1.1. Problem spełnialnoś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 metody wzmacniania
6.3. Zastosowania metody wyszukiwania Grovera
6.3.1. Wyszukiwanie w przypadku nieznanej liczby rozwiązań

7. Dolne ograniczenia na złożoność dla obwodów kwantowych

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

8. Dodatek A. Fizyka kwantowa

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
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 poduktadó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

9. Dodatek B. Podstawy matematyczne

9.1. Teoria grup
9.1.1. Wiadomości wstępne
9.1.2. Podgrupy, warstwy
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

Bibliografia
Indeks