Quantenalgorithmen

Inhaltsverzeichnis

1. Frontmatter

2. Kapitel 1. Einleitung

   Johannes A. Buchmann

   Zusammenfassung

   Im Vorwort wird erl "autert, warum Quantenalgorithmen ein interessantes und wichtiges Thema darstellen. Gründe sind die große Bedeutung der Digitalisierung, der wachsende Bedarf an Rechenleistung sowie Bedrohungen der Cybersicherheit. . Die folgenden Kapitel werden kurz zusammengefasst und die Logik der Darstellung wird erläutert: Grundlagen aus Informatik, Mathematik und Quantenphysik gefolgt von der Darstellung wichtiger Algorithmen und ergänzt von einem Appendix. Es folgen Hinweise für die Verwendung des Buches in Vorlesungen je nach Schwerpunkt: angewandt oder Grundlagen-orientiert. Am Schluss stehen Danksagungen.

3. Kapitel 2. Klassische Berechnungen

   Johannes A. Buchmann

   Zusammenfassung

   Das Kapitel behandelt die Theorie klassischer Berechnungen, soweit sie für das Verständnis von Quantenalgorithmen notwendig ist. Es beginnt mit der Theorie klassischer Algorithmen. Ein Schwerpunkt liegt auf probabilistischen Algorithmen und deren Komplexitätsanalyse. Die Analyse probabilistischer Algorithmen kann nämlich leicht auf die Analyse von Quantenalgorithmen übertragen werden. Die anschließend vorgestellten klassischen Komplexitätsklassen dienen als Vorlage für die Definition von Quantenkomplexitätsklassen. Der zweite Teil des Kapitels ist den klassischen Booleschen Schaltkreisen gewidmet, insbesondere der Theorie reversibler Schaltkreise, die in Quantenschaltkreise übersetzt werden können. Das Kapitel behandelt u.a. sogenannte universelle Mengen klassischer Gatter sowie uniforme Schaltkreisfamilien und ihre Beziehung zu klassischen Algorithmen und deren Komplexität. Es wird auch gezeigt, dass jeder boolesche Schaltkreis in einen reversiblen Schaltkreis umgewandelt werden kann - ein wichtiges Ergebnis, das später verwendet wird, um zu zeigen, dass jede boolesche Funktion von einem Quantenschaltkreis berechnet werden kann.

4. Kapitel 3. Hilberträume

   Johannes A. Buchmann

   Zusammenfassung

   Das Kapitel stellt die Theorie endlich-dimensionaler komplexer Hilberträume vor. Sie ist grundlegend für die die Modellierung der Physik, die für Quantenalgorithmen und die Formulierung der relevanten quantenmechanischen Postulate benötigt wird. Das Kapitel beginnt mit den notwendigen Grundlagen, einschließlich wichtiger Konzepte wie innere Produkte, Orthogonalität und lineare Abbildungen. Es führt auch den Zerlegungssatz von Schur ein, der im folgenden sehr wichtig wird. Im weiteren Verlauf macht das Kapitel die Leser:innen mit Hermiteschen, unitären, normalen und anderen für die Quantenmechanik wichtigen Operatoren vertraut. Von besonderer Bedeutung ist der Spektralsatz und seine Konsequenzen, die wichtige Eigenschaften dieser Operatoren zeigen. Außerdem befasst sich das Kapitel mit Tensorprodukten endlich-dimensionaler Hilberträume, die für die Modellierung von Quantenalgorithmen eine entscheidende Rolle spielen. In diesem Zusammenhang wird auch der Schmidtsche Zerlegungssatz behandelt, der es erlaubt, verschränkte Quantensystemen zu charakterisieren.

5. Kapitel 4. Quantenmechanik

   Johannes A. Buchmann

   Zusammenfassung

   Das Kapitel behandelt die Grundlagen der Quantenmechanik, die für das Verständnis von Quantenalgorithmen notwendig sind, insbesondere die relevanten quantenmechanischen Postulate. Um deren Bedeutung für Quantenalgorithmen zu verdeutlichen, werden sie angewendet, um grundlegende Konzepte wie Quantenbits, Quantenregister, Quantengatter und Quantenschaltkreise einzuführen. Einfache Beispiele für Quantenberechnungen sollen das Verständnis der Leser:innen weiter vertiefen. Darüber hinaus erläutere ich die geometrische Interpretation der Zustände von Quantenbits als Punkte auf der sogenannten Blochkugel und stelle eine alternative Beschreibung der Quantenmechanik mithilfe sogenannter Dichteoperatoren vor. Dieser Ansatz erlaubt es, die Eigenschaften von Komponenten zusammengesetzter Quantensysteme zu modellieren.

6. Kapitel 5. Die Theorie der Quantenalgorithmen

   Johannes A. Buchmann

   Zusammenfassung

   Aufbauend auf den Grundlagen der Informatik, Mathematik und Physik aus den ersten drei Kapiteln behandelt das Kapitel die Theorie der Quantenalgorithmen. Zunächst führe ich Ein-Qubit-Gatter wie die Pauli- und das Hadamard-Gatter ein und zeige, dass deren Operationen als Drehungen der Blochkugel im dreidimensionalen Raum interpretiert werden können. Danach diskutiere ich Mehr-Qubit-Operatoren, insbesondere sogenannte kontrollierte Operatoren. Außerdem stelle ich Ancilla-Operatoren vor, die zusätzliche Qubits in Quantenschaltkreise einfügen und Löschgatter, die Qubits entfernen können. Ergebnisse aus der Theorie klassischer reversibler Schaltkreise werden verwendet, um zu zeigen, dass jede Boolesche Funktion von einem Quantenschaltkreis berechnet werden kann. Im Gegensatz zum klassischen Szenario ist es im Quantenfall jedoch unmöglich, alle Quantenoperatoren mit endlich vielen Quantengattern zu implementieren. Stattdessen stelle ich endliche Mengen von Quantengattern vor, mit deren Hilfe alle Quantenoperatoren beliebig genau approximiert werden können. Schließlich führt das Kapitel in die Quantenkomplexitätstheorie ein und nutzt dabei die Analogie zwischen klassischen probabilistischen Algorithmen und Quantenalgorithmen. Dabei wird auch die Komplexitätsklasse \(\text {BQP}\) (Bounded-Error Quantum Polynomial Time) definiert.

7. Kapitel 6. Die Algorithmen von Deutsch und Simon

   Johannes A. Buchmann

   Zusammenfassung

   Das Kapitel stellt frühe Algorithmen vor, die die Arbeitsweise von Quantencomputern illustrieren. Ich beginne mit dem Algorithmus von David Deutsch aus seiner bahnbrechenden Arbeit von 1985 [Deu85] und seiner Verallgemeinerung durch David Deutsch und Richard Jozsa aus dem Jahr 1991 [DJ92]. Danach beschreibe ich den von Daniel R. Simon 1994 vorgeschlagenen Algorithmus [Sim94]. Es ist der erste Quantenalgorithmus, der eine quadratische Beschleunigung gegenüber den entsprechenden besten klassischen Algorithmen bietet. Bei der Beschreibung dieser Algorithmen werden zwei Schlüsselprinzipien deutlich, die wesentlich dazu beitragen, dass Quantenalgorithmen klassischen Berechnungsverfahren überlegen sein können. Das erste Prinzip ist die Quantenparallelität, die ausnutzt, dass sich Quantenregistern in einer Überlagerung von Quantenzuständen befinden können. Das zweite Prinzip ist die Quanteninterferenz, die es Quantenalgorithmen ermöglicht, die Wahrscheinlichkeit erwünschter Ergebnisse sehr groß zu machen, während unerwünschte Ergebnisse unterdrückt werden. Hierfür wird häufig das wichtige Phase-Kickback-Verfahren verwendet, das ebenfalls in diesem Kapitel erläutert wird.

8. Kapitel 7. Die Algorithmen von Shor

   Johannes A. Buchmann

   Zusammenfassung

   Das Kapitel behandelt die bekanntesten Quantenalgorithmen, nämlich Peter Shors Algorithmen zur Faktorisierung ganzer Zahlen und Berechnung diskreter Logarithmen [Sho94]. Ich skizziere zunächst Shors Faktorisierungsalgorithmus und gebe so einen Leitfaden für die nachfolgenden Konzepte und ihre Verwendung. Anschließend stelle ich das wichtigste Hilfsmittel von Shors Algorithmen vor: die Quanten-Fourier-Transformation. Ich erkläre, wie dieser Operator und sein Inverses mithilfe einfacher Quantengatter implementiert werden können. Mithilfe der Quanten-Fourier-Transformation wird das Problem der sogenannten Quantenphasenschätzung gelöst. Diese Methode ermöglicht die Entwicklung eines polynomiellen Quantenalgorithmus zur Berechnung der Ordnung einer ganzen Zahl modulo einer anderen positiven ganzen Zahl. Dieser Ordnungsalgorithmus erlaubt dann die Faktorisierung ganzer Zahlen in Polynomzeit. Darüber hinaus erläutere ich in diesem Kapitel, wie mittels Quantenphasenschätzung diskrete Logarithmen modulo positiver ganzer Zahlen in Polynomzeit berechnet werden können.

9. Kapitel 8. Quanten-Suche und Quanten-Zählen

   Johannes A. Buchmann

   Zusammenfassung

   Das Kapitel präsentiert den Grover-Suchalgorithmus aus dem Jahr 1996, einen weiteren bedeutenden Quantenalgorithmus mit vielfältigen Anwendungen. Dieser Algorithmus sucht nach einem Element mit einer bestimmten Eigenschaft in einer unstrukturierten Menge und bietet einen quadratischen Geschwindigkeitsvorteil gegenüber herkömmlichen Techniken. In diesem Zusammenhang erläutere ich auch das Konzept der Amplitudenverstärkung, die im Grover-Algorithmus eine zentrale Rolle spielt. Darüber hinaus behandele ich die Quantenzälalgorithmen von Gilles Brassard, Peter Høyer und Alain Tapp aus dem Jahr 1998 [BHT98]. Sie nutzen den Grover-Algorithmus und die Quantenphasenschäung, um die Löngsanzahl des oben erwäten Suchproblems zu bestimmen.

10. Kapitel 9. Der HHL-Algorithmus

    Johannes A. Buchmann

    Zusammenfassung

    Dieses Kapitel skizziert den HHL-Algorithmus, der Eigenschaften von Lösungen großer, dünn besetzter linearer Gleichungssysteme über den komplexen Zahlen finden kann. Der Hauptzweck dieses Kapitels ist es zu zeigen, wie die Ideen der zuvor in diesem Buch vorgestellten Algorithmen den Entwurf eines solchen fortgeschrittenen Algorithmus ermöglichen.

11. Backmatter