Komputer kwantowy. Programowanie, algorytmy, kod - ebook

Komputery kwantowe nie są już tylko urządzeniami teoretycznymi. Nie są też futurystycznym monstrum, obcą maszyną, która zamieni całe istniejące oprogramowanie w jakąś jego niezrozumiałą alternatywę. Komputery kwantowe (QPU) staną się raczej radykalnym rozszerzeniem możliwości współczesnej informatyki, które pozwoli nam rozwiązać problemy dotychczas nierozwiązywalne. Istnieją ważne zadania, z którymi QPU potrafią sobie świetnie poradzić, a których rozwiązanie byłoby niemożliwe na jakimkolwiek standardowym urządzeniu komputerowym. Z drugiej strony z wieloma standardowymi obliczeniami QPU nie radzi sobie dużo lepiej niż najzwyklejszy laptop. Z punktu widzenia programisty zatem stanowi rodzaj koprocesora o ciekawych możliwościach.

Oto przewodnik po wspaniałym, nieodkrytym jeszcze do końca świecie informatyki kwantowej. Aby ją zrozumieć, niepotrzebny jest doktorat z fizyki kwantowej i wyższej matematyki. Dzięki tej książce opanujesz zestaw pojęć niezbędnych do zrozumienia działania QPU, dowiesz się, jakie problemy mogą rozwiązać aplikacje QPU i nauczysz się korzystać z narzędzi do pisania programów dla QPU. Zaprezentowane tu koncepcje są bogato ilustrowane przykładami, które można łatwo uruchomić na darmowym symulatorze QCEngine. Istnieje też możliwość korzystania z fizycznych QPU (kilka prototypów QPU udostępniono w chmurze). Interesującą, choć nieco trudniejszą częścią przewodnika jest rozdział poświęcony zastosowaniu obliczeń kwantowych w uczeniu maszynowym.

W tej książce:

• koncepcje programowania procesorów kwantowych
• kubity, superpozycja i teleportacje kwantowe
• prymitywy QPU
• wzmacnianie amplitudy, kwantowa transformacja Fouriera i szacowanie fazy
• przykłady aplikacji QPU

QPU: zrób pierwszy krok ku technologii przyszłości!

 

Wstęp 9

 

1. Wprowadzenie 13

• Wymagania wstępne 13
• Czym jest QPU? 14
• Podejście praktyczne 15
  • Elementarz QCEngine 15
  • Natywne instrukcje QPU 17
  • Ograniczenia symulatorów 20
  • Ograniczenia sprzętu 20
• QPU a GPU: charakterystyka ogólna 20

CZĘŚĆ I. PROGRAMOWANIE DLA QPU

2. Jeden kubit 25

• Krótkie spojrzenie na fizyczny kubit 26
• Wprowadzenie notacji kołowej 29
  • Rozmiar kół 29
  • Rotacja kół 30
• Pierwsze operacje QPU 31
  • Instrukcja QPU: NOT 32
  • Instrukcja QPU: HAD 32
  • Instrukcja QPU: READ 33
  • Instrukcja QPU: WRITE 33
  • Czas na praktykę: idealnie losowy bit 34
  • Instrukcja QPU: PHASE(?) 37
  • Instrukcje QPU: ROTX(?) i ROTY(?) 38
• COPY: brakująca operacja 38
• Łączenie operacji QPU 39
  • Instrukcja QPU: ROOT-of-NOT 39
• Czas na praktykę: kwantowy łowca szpiegów 41
• Podsumowanie 44

3. Wiele kubitów 45

• Notacja kołowa rejestrów multikubitowych 45
• Rysowanie rejestru wielokubitowego 48
• Operacje jednokubitowe w wielokubitowych rejestrach 48
  • Czytanie kubitu w wielokubitowym rejestrze 50
• Wizualizowanie większej liczby kubitów 51
• Instrukcja QPU: CNOT 52
• Czas na praktykę: wykorzystanie par Bella w dzielonej losowości 55
• Instrukcje QPU: CPHASE i CZ 56
  • Sztuczka QPU: odbicie fazowe 57
• Instrukcja QPU: CCNOT (bramka Toffoliego) 59
• Instrukcje QPU: SWAP i CSWAP 60
  • Test SWAP 61
• Tworzenie operacji warunkowej 63
• Czas na praktykę: zdalnie kontrolowana losowość 66
• Podsumowanie 68

4. Teleportacja kwantowa 69

• Czas na praktykę: teleportujmy sobie coś 69
• Spacer po programie 74
  • Krok 1. Utworzenie splątanej pary 75
  • Krok 2. Przygotowanie ładunku 75
  • Krok 3.1. Połączenie ładunku ze splątaną parą 76
  • Krok 3.2. Wprowadź ładunek w superpozycję 76
  • Krok 3.3. Odczytaj oba kubity Alice 77
  • Krok 4. Odbierz i przekształć 78
  • Krok 5. Weryfikacja wyniku 78
• Interpretowanie wyników 80
• Jak naprawdę używa się teleportacji? 81
• Zabawne wypadki przy teleportacji 81

CZĘŚĆ II. PRYMITYWY QPU

5. Kwantowe arytmetyka i logika 85

• Dziwnie odmienne 85
• Arytmetyka na QPU 87
  • Czas na praktykę: budowanie operatorów inkrementacji i dekrementacji 87
• Dodawanie dwóch kwantowych liczb stałoprzecinkowych 90
• Ujemne liczby stałoprzecinkowe 91
• Czas na praktykę: bardziej złożona matematyka 92
• Prawdziwa kwantowość 93
  • Wykonanie kwantowo-warunkowe 94
  • Wyniki kodowane w fazie 95
• Odwracalność i kubity skreczowe 96
• Odwracanie skutków obliczeń 98
• Mapowanie logiki booleanowskiej do operacji QPU 101
  • Podstawowa logika kwantowa 101
• Podsumowanie 103

6. Wzmacnianie amplitudy 105

• Czas na praktykę: konwersja między fazą a wielkością 105
• Iteracja wzmacniania amplitudy 108
• Więcej iteracji? 108
• Wiele wejść z flipem 111
• Wykorzystanie wzmocnienia amplitudy 116
  • AA i QFT jako szacowanie sumy 116
  • Przyspieszanie konwencjonalnych algorytmów za pomocą AA 117
• Wewnątrz QPU 117
  • Intuicja 117
• Podsumowanie 119

7. QFT: Kwantowa transformata Fouriera 121

• Ukryte wzorce 121
  • QFT, DFT i FFT 123
• Częstotliwości w rejestrze QPU 123
• DFT 126
  • Rzeczywiste i zespolone wejścia DFT 128
  • DFT dowolnego sygnału 130
• Używanie QFT 132
  • QFT jest szybka 132
• Wewnątrz QPU 139
  • Zrozumienie zasad 140
  • Operacja po operacji 141
• Wnioski 145

8. Szacowanie fazy kwantowej 147

• Uczymy się o operacjach QPU 147
• Fazy własne uczą nas czegoś użytecznego 148
• Co robi szacowanie fazy 149
• Jak korzystać z szacowania fazy 150
  • Wejścia 150
  • Wyjścia 152
• Drobnym drukiem 153
  • Dobór rozmiaru rejestru wyjściowego 153
  • Złożoność 154
  • Operacje warunkowe 154
• Szacowanie fazy w praktyce 154
• Wewnątrz QPU 155
  • Jak to działa? 156
  • Operacja po operacji 157
• Podsumowanie 159

CZĘŚĆ III. ZASTOSOWANIA QPU

9. Prawdziwe dane 163

• Dane liczbowe 163
• QRAM 165
• Kodowanie wektorów 168
  • Ograniczenia kodowania amplitudy 171
  • Kodowanie amplitudy i notacja kołowa 172
• Kodowanie macierzy 173
  • Jak operacja QPU może reprezentować macierz? 173
  • Symulacja kwantowa 174

10. Kwantowe wyszukiwanie 179

• Logika fazowa 180
  • Budowanie podstawowych operacji logiki fazowej 182
  • Budowanie złożonych zdań logiki fazowej 182
• Rozwiązywanie łamigłówek logicznych 185
  • O kotkach i tygrysach 185
• Ogólny przepis na rozwiązanie problemu spełnialności formuły logicznej 189
  • Czas na praktykę: rozwiązujemy formułę boolowską 3-SAT 190
  • Czas na praktykę: problem 3-SAT niespełniający kryteriów 192
• Przyśpieszanie konwencjonalnych algorytmów 194

11. Kwantowy supersampling 197

• Co QPU może zrobić dla grafiki komputerowej? 197
• Zwykły supersampling 198
• Czas na praktykę: obliczanie obrazów kodowanych fazą 199
  • Kwantowy shader pikseli 200
  • Wykorzystanie PHASE do rysowania 201
  • Rysowanie krzywych 203
• Próbkowanie obrazów kodowanych fazowo 204
• Ciekawszy obrazek 205
  • Supersampling 208
• QSS a konwencjonalny sampling Monte Carlo 208
  • Jak działa QSS 209
• Dodawanie koloru 214
• Podsumowanie 216

12. Algorytm faktoryzacji Shora 217

• Czas na praktykę: wykorzystanie algorytmu faktoryzacji Shora na QPU 218
• Jak właściwie działa algorytm Shora? 219
  • Czy w ogóle potrzebujemy QPU? 220
  • Podejście kwantowe 222
• Krok po kroku: faktoryzacja liczby 15 223
  • Krok 1. Inicjalizacja rejestrów QPU 224
  • Krok 2. Rozszerzenie do superpozycji kwantowej 224
  • Krok 3. Warunkowe mnożenie przez 2 227
  • Krok 4. Warunkowe mnożenie przez 4 228
  • Krok 5. Kwantowa transformata Fouriera 229
  • Krok 6. Odczytanie kwantowego wyniku 231
  • Krok 7. Logika cyfrowa 231
  • Krok 8. Sprawdzenie wyniku 234
• Drobnym drukiem 235
  • Obliczanie reszty z dzielenia 235
  • Czas a przestrzeń 236
  • Kopierwsze inne niż 2 236

13. Kwantowe uczenie maszynowe 237

• Rozwiązywanie układów równań liniowych 238
  • Opisywanie i rozwiązywanie układów równań liniowych 238
  • Rozwiązywanie układu równań liniowych za pomocą QPU 240
• Kwantowa analiza głównych składowych 249
  • Standardowa analiza składowych głównych 249
  • PCA z QPU 250
• Kwantowa maszyna wektorów podtrzymujących 254
  • Standardowe maszyny wektorów podtrzymujących 254
  • SVM z QPU 257
• Inne aplikacje uczenia maszynowego 260

CZĘŚĆ IV. PERSPEKTYWY

14. Bądź na bieżąco: przewodnik po literaturze 265

• Od notacji kołowej po wektory zespolone 265
• Subtelności i uwagi na temat terminologii 267
• Podstawy miary 268
• Rozkład bramki i kompilacja 269
• Teleportacja bramek 271
• Galeria sław 271
• Wyścig: komputery kwantowe a klasyczne 272
• Uwaga na temat algorytmów opartych na wyroczni kwantowej 273
  • Algorytm Deutscha-Jozsy 273
  • Algorytm Bernsteina-Vaziraniego 273
  • Algorytm Simona 274
• Języki programowania kwantowego 274
• Obietnica kwantowej symulacji 275
• Korekcja błędu i urządzenia NISQ 276
• Co dalej? 276
  • Książki 276
  • Notatki z wykładów 277