Nach der technologischen Revolution, die die Erfindung des Computers ausgelöst hat, steht mit der Zusammenführung von Computing und Quantenmechanik die nächste bevor: Quantum Computing. Anschaulich und auf Beispiele gestützt führt dieses Buch in die Grundlagen des Quantum Computing ein. Was ein Quantencomputer ist und was er kann wird anhand von Algorithmen erläutert, also anhand von konkreten Rechenverfahren. Dieser an den Grundlagen orientierte Zugang befähigt Leserinnen und Leser aktuelle und auch künftige Entwicklungen einzuordnen. Um zu verstehen, wie Quantencomputer rechnen, erklärt der Autor, der als Professor für Informatik an der TH Brandenburg lehrt, zunächst die einfachen quantenmechanischen Prinzipien und stellt diese so anwendungsorientiert wie nur möglich dar.
Neben den einführenden Kapiteln, die selbst grundlegende Begriffe wie Berechnung oder Algorithmus ausführlich erläutern, widmen sich die folgenden Kapitel 5 bis 8 den Anwendungen des Quantum Computing. Alle wesentlichen Ergebnisse wie etwa Grovers Suchalgorithmus oder Shors Faktorisierungsalgorithmus werden detailliert und intuitiv verständlich dargestellt. Zudem werden Ergebnisse der Forschung wie Teleportation und Quantenkryptographie präsentiert. Diese Kapitel vermitteln vertiefendes Wissen als Vorbereitung auf die Lektüre der Forschungsliteratur. Für alle, die sich noch einmal die mathematischen Grundlagen ins Gedächtnis rufen wollen, bietet der Anhang eine knappe Darstellung zum Nachschlagen.
Das Buch erscheint in der Reihe "Computational Intelligence" und richtet sich an Studierende der Informatik, aber auch an alle anderen Interessierten. Für die 5. Auflage wurde das Buch vollständig durchgesehen und aktualisiert. Neu hinzugekommen ist das Thema Fehlerkorrektur für Quantenbits.
Matthias Homeister ist Professor für Informatik an der Technische Hochschule Brandenburg.
(Verlagstext)
Inhaltsverzeichnis
Vorwort IX
1 Einleitung 1
1.1 Eine neue A rt des Rechnens........................................................ 1
1.2 Über dieses B u c h ........................................................................ 8
2 Vom Bit zum Quantenregister 9
2.1 Was ist eine Berechnung? . ........................................................ 10
2.1.1 Die Turingmaschine....................................................... 13
2.1.2 Schaltkreise.................................................................... 14
2.1.3 Der Sprung in die Quantenwelt: Schrödingers Katze . 17
2.2 Das Q u a n te n b it........................................................................... 20
2.3 Rechenschritte auf einem Quantenbit....................................... 23
2.4 Der erste Algorithmus: Ein Zufallsgenerator.......................... 26
2.5 Quantenregister.......................................................................... 28
2.6 Der zweite Algorithmus: Das Problem von D e u ts c h ............... 33
2.7 Die Rolle des Tensorprodukts.................................................... 37
2.8 Das Messen von Quantenregistern................... 44
2.9 Noch einmal das Problem von Deutsch.................................... 50
2.10 Bestandsaufnahme: Die drei Prinzipien des Quantum Computing 51
2.11 Verschränkung.............................................................................. 53
2.12 Die Hadamard-Transformation und mehrere B its ....................... 59
2.13 Der Algorithmus von Deutsch-Jozsa....................................... 62
3 Vom Quantenregister zum Quantenschaltkreis 67
3.1 L a u fz e it........................................................................................ 68
3.2 Klassische Schaltkreise und K o m p le xitä t................................. 75
3.3 Quantengatter und Quantenschaltkreise................................. 76
3.4 Quantenbits kopieren: Das No-Cloning-Theorem.................... 81
3.5 Umkehrbare Berechnungen.......................................... 84
3.6 Unterscheidbare Zustände ........................................................... 93
3.7 Gestörte Berechnungen................... 95
4 Hilfsmittel aus der Theoretischen Informatik 101
4.1 Komplexitätsklassen....................................................................... 101
4.2 Randomisierte Algorithmen . ....................................................... 106
4.2.1 Mit dem Zufall rechnen....................................................106
4.2.2 Ein Primzahltest.................................................................107
4.2.3 Probabilistische Komplexitätsklassen.............................. 110
4.3 Unlösbare Probleme? NP-Vollständigkeit................................... 113
4.4 Quantenkomplexitätstheorie.......................................................... 118
4.5 Die Churchsche These....................................................................121
5 Teleportation und dichte Kodierung 125
5.1 Q uantenteleportation....................................................................127
5.2 Dichte K o d ie ru n g .......................................................................... 131
5.3 Verschränkte B i t s .......................................................................... 133
6 Suchen 137
6.1 Die Nadel im Heuhaufen ............................................................. 138
6.2 Die Grover-Iteration.......................................................................140
6.3 Eine geometrische Veranschaulichung..........................................146
6.4 Varianten der Quantensuche .......................................................153
6.4.1 Suche nach einer von mehreren Lösungen.....................153
6.4.2 Suche bei unbekannt vielen L ö su n g e n ..........................155
6.4.3 Die Suche nach dem M in im u m .......................................156
6.4.4 Z ä h le n .................................................................................159
6.5 Anwendungen von Grovers Algorithmus ................................... 159
6.6 Grovers Algorithmus ist von optimaler Größenordnung .... 161
6.7 Folgen für die Fähigkeiten von Quantencomputern...................166
7 Geheime Botschaften 169
7.1 Alice, Bob und E v e ....................................................................... 170
7.2 Quantenverschlüsselung: das BB84-Protokoll . 174
7.3 Lauschstrategien..............................................................................182
7.4 Quanten Verschlüsselung mit Verschränkung.............................187
8 Klassische Verschlüsselungen knacken: Primfaktorzerlegung 193
8.1 Faktorisierung und Verschlüsselung: RSA-Kryptographie . . . 194
8.2 Die Suche nach P e rio d e n ............................................................. 199
8.3 Die schnelle Fouriertransformation................................ 206
8.4 Die Quanten-Fouriertransformation.............................................214
8.5 Simons A lgorithm us....................................................... 218
8.6 Shors A lgorithm us.......................................................................... 223
8.7 Jenseits von S h o r ................................................................. 231
9 Fehler korrigieren 237
9.1 Dekohärenz und Fehler auf Q u a n te n b its ................................... 237
9.2 Klassische Fehlerkorrektur............................................................. 242
9.3 Herausforderungen bei der Korrektur von Quantenbits .... 242
9.4 Qubits gegen Fehler sichern..........................................................243
9.4.1 Bitflip-Code m it Syndrom: Korrektur des Codewords 243
9.4.2 Der Bitflip-Code: Korrektur des D a te n b its ...................245
9.4.3 Korrektur von P h ase flips ................................................ 246
9.5 Shors 9-Q ubit-C ode................................................ 247
9.6 A u s b lic k .................................................................... 250
10 Quantenhardware 253
10.1 Anforderungen.................................................................................253
10.2 Photonen ....................................................................................... 255
10.2.1 Mach-Zehnder-Interferometer..........................................255
10.2.2 Zufallszahlen.......................................................................258
10.2.3 Kryptographie....................................................................259
10.3 Kernspinresonanz.......................................................................... 263
10.4 lonenfallen....................................................................................... 265
10.5 Einwegberechnungen m it Clusterzuständen................................266
10.6 S upraleiter....................................................................................... 269
10.7 Adiabatische Quantencomputer................................................... 271
11 Zur Geschichte der Quantenmechanik 277
11.1 Max Planck: das Quantum der W irk u n g ................................... 277
11.2 Albert Einstein: Spukhafte Fernwirkung ................................... 279
11.3 Niels Bohr: Kopenhagen................................................................ 280
11.4 Werner Heisenberg: Ein großes Q u a n te n e i................................283
11.5 Erwin Schrödinger: Katzen und W e lle n ...................................... 285
11.6 Zur Geschichte des Quantencomputers...................................... 286
A Mathematische Grundlagen 289
A .l Komplexe Zahlen ............................................... 289
A.2 Vektorräume . . . 291
A.2.1 Was sind Vektorräume?.................................................. 291
A.2.2 Basen und U nterräum e...................................................293
A.2.3 Winkel und Abstände in einem V e k to rra u m ............294
A.2.4 Projektionen......................................................................296
A.3 M a trize n ......................................................................................... 297
A.4 Kombinatorik und Wahrscheinlichkeit.........................................299
A.5 Ganze Z a h le n ................................................................................301
A.5.1 Teiler und V ielfache.........................................................301
A.5.2 Modulares R echnen......................................................... 301
A.5.3 Zur D iv is io n ............................ 303
B Lösungen ausgewählter Übungsaufgaben 305
Literatur 315
Symbole und Abkürzungen 321
Quantengatter 322
Namen- und Sachwortverzeichnis