Quantenrechner haben in den letzten Jahren einen regelrechten Boom ausgelöst, sowohl bei den Informatikern als auch bei den Physiker. Historisch gesehen sind die Grundlagen bereits seit dem ersten Viertel des zwanzigsten Jahrhunderts bekannt. Eine Ausnutzung der physikalischen Phänomene für Berechnungen wurde allerdings erst in Angriff genommen, als David Deutsch 1985 das Modell des Universellen Quantencomputers (UQC) entwickelte, in welchem beliebige physikalische Systeme, also auch klassische Computer, simuliert werden können.
Mit Hilfe dieses theoretischen Modells eines Quantencomputers zeigten Deutsch und Josza [DJ92] an einem einfachen Beispiel, dass ein solcher universeller Quantencomputer bzgl. der Auswertung einer Funktion, man sagt auch die Abfrage eines Orakels, eine stärkere Rechenleistung hat als klassische Rechner, wie z.B. die Turingmaschine. Gegeben sei eine Funktion f:{0,1}n→ {0,1}, welche entweder konstant ist oder deren Anzahl an Eingaben mit Ausgabe 1 und 0 gleich ist. Für diese Funktion kann der UQC mit nur O(1)vielen Funktionsauswertungen entscheiden, welche der beiden Eigenschaften f erfüllt. Im Gegensatz dazu benötigt eine Turingmaschine superpolynomiell viele Funktionsauswertungen.
Wesentlich populärer wurden die Quantenrechner, als Peter Shor 1994 einen Algorithmus [Sho97] vorstellte, der sowohl das Problem der Primfaktorzerlegung, als auch das des diskreten Logarithmus mit polynomiell vielen Rechenschritten löste - zwei Probleme, von denen man annimmt, sie haben keine effiziente Lösung auf Turingmaschinen. Damit verbunden ist auch die Unsicherheit des RSA-Kryptosystems, welches auf der Komplexität der Primfaktorzerlegung aufbaut.
Inhaltsverzeichnis
1 Einleitung
1.1 Quantenrechner
1.2 Adiabatische Quantenberechnungen
1.3 Aufgabenstellung der Diplomarbeit
2 Quantenmechanische Grundlagen
2.1 Mathematische Vorbemerkungen
2.2 Die Schrödingergleichung
2.2.1 Das Wechselwirkungsbild
2.2.2 Das Bild der sich drehenden Achsen
2.3 Die adiabatische Entwicklung
2.3.1 Gültigkeit und Dauer der adiabatischen Näherung
2.3.2 Adiabatische Entwicklung vs. Quantenschaltkreise
3 Anwendungen der adiabatischen Entwicklung in der Informatik
3.1 Grundlagen der theoretischen Informatik
3.2 Ein Algorithmus für MAX-3-SAT durch adiabatische Entwicklung
3.2.1 Definitionen
3.2.2 Zielsetzung
3.2.3 Definition eines Beispiels
3.2.4 Der Basis-Hamiltonoperator HB
3.2.5 Problem-Hamiltonoperator HP
3.2.6 Gesamt-Hamiltonoperator
3.3 Ein Algorithmus für GRAPH ISOMORPHISM durch adiabatische Entwicklung
3.3.1 Kodierung der Permutationsmatrizen
3.3.2 Beispiel
3.3.3 Basis-Hamiltonoperator HB
3.3.4 Problem-Hamiltonoperator HP
3.3.5 Der Gesamt-Hamiltonoperator
3.3.6 Diskussion der Lokalitätsforderung
3.3.7 Alternative Problemlösungsansätze
3.3.8 Resumée
4 Abschätzungen der Erfolgswahrscheinlichkeit
4.1 Definitionen und Voraussetzungen an die Hamiltonoperatoren
4.2 Klassifikation der Eigenwerte
4.3 Abschätzung der Eigenwertdifferenz durch Gerschgorin-Kreise
4.3.1 Grundlagen zu Gerschgorin-Kreisen
4.3.2 Analyse der oberen Eigenwertdifferenz
4.3.3 Analyse von Af,g
4.4 Abschätzung der Eigenwertdifferenz nach Weinstein
4.5 Eigenwertberechnung nach Courant und Weyl
4.6 Analyse der Erfolgswahrscheinlichkeit
4.6.1 Vergleich der Analysen
5 Implementierung
5.1 Lastenheft
5.2 GUI-Programmierung mit Qt
5.3 Die Architektur von PITA-Quamputation
5.3.1 Das Model-View-Control-Konzept bei PITA-Quamputation
5.3.2 Erweiterbarkeit
5.3.3 Testsystem
5.4 Verfahren zur Ermittlung von Eigenwerten und -vektoren
5.4.1 Reduktion einer Matrix auf symmetrische Tridiagonalgestalt
5.4.2 Bestimmung von ausgewählten Eigenwerten einer symmetrischen Tridiagonalmatrix
5.4.3 Bestimmung des Eigenvektors zur Eigenwertnäherung einer symmetrischen, irreduziblen Tridiagonalmatrix
5.4.4 Bestimmung ausgewählter Eigenwerte und -vektoren des Hamiltonoperators H(t)
5.5 Bestimmung der essentiellen Eigenwertdifferenz
5.6 Vergleich der Analysen der adiabatischen Entwicklung
6 Zusammenfassung und Ausblick
A Handbuch
A.1 Installation
A.2 Der Programmstart
A.3 Eingabemöglichkeiten für Probleminstanzen
A.4 Auswertung
Zielsetzung & Themen
Diese Diplomarbeit untersucht die Effizienz und Laufzeitanalyse von adiabatischen Quantenalgorithmen für komplexe Probleme der theoretischen Informatik, wobei insbesondere verbesserte Eigenwertabschätzungen und eine praktische Umsetzung als Softwarewerkzeug im Vordergrund stehen.
- Analyse und Optimierung der Laufzeit adiabatisch entwickelter Quantenalgorithmen.
- Untersuchung der Probleme MAX-3-SAT und GRAPH ISOMORPHISM.
- Entwicklung des Softwaretools "PITA-Quamputation" zur Visualisierung und Analyse der Algorithmen.
- Mathematische Fundierung durch Eigenwert- und Erfolgswahrscheinlichkeitsabschätzungen.
- Implementierung von effizienten Verfahren zur Eigenwert- und Eigenvektorbestimmung.
Auszug aus dem Buch
1.1 Quantenrechner
Quantenrechner haben in den letzten Jahren einen regelrechten Boom ausgelöst, sowohl bei den Informatikern als auch bei den Physiker. Historisch gesehen sind die Grundlagen bereits seit dem ersten Viertel des zwanzigsten Jahrhunderts bekannt. Eine Ausnutzung der physikalischen Phänomene für Berechnungen wurde allerdings erst in Angriff genommen, als David Deutsch 1985 das Modell des Universellen Quantencomputers (UQC) entwickelte, in welchem beliebige physikalische Systeme, also auch klassische Computer, simuliert werden können.
Mit Hilfe dieses theoretischen Modells eines Quantencomputers zeigten Deutsch und Josza [DJ92] an einem einfachen Beispiel, dass ein solcher universeller Quantencomputer bzgl. der Auswertung einer Funktion, man sagt auch die Abfrage eines Orakels, eine stärkere Rechenleistung hat als klassische Rechner, wie z.B. die Turingmaschine. Gegeben sei eine Funktion f : {0, 1}^n → {0, 1}, welche entweder konstant ist oder deren Anzahl an Eingaben mit Ausgabe 1 und 0 gleich ist. Für diese Funktion kann der UQC mit nur O(1) vielen Funktionsauswertungen entscheiden, welche der beiden Eigenschaften f erfüllt. Im Gegensatz dazu benötigt eine Turingmaschine superpolynomiell viele Funktionsauswertungen.
Wesentlich populärer wurden die Quantenrechner, als Peter Shor 1994 einen Algorithmus [Sho97] vorstellte, der sowohl das Problem der Primfaktorzerlegung, als auch das des diskreten Logarithmus mit polynomiell vielen Rechenschritten löste – zwei Probleme, von denen man annimmt, sie haben keine effiziente Lösung auf Turingmaschinen. Damit verbunden ist auch die Unsicherheit des RSA-Kryptosystems, welches auf der Komplexität der Primfaktorzerlegung aufbaut.
Zusammenfassung der Kapitel
1 Einleitung: Diese Einleitung führt in die historische Entwicklung von Quantenrechnern ein, erläutert grundlegende Algorithmen von Shor und Grover und beschreibt die Aufgabenstellung sowie das Ziel der vorliegenden Diplomarbeit.
2 Quantenmechanische Grundlagen: Das Kapitel vermittelt die notwendigen mathematischen und physikalischen Grundlagen, inklusive der Schrödingergleichung, dem Wechselwirkungsbild und dem zentralen Adiabatensatz, um die Funktionsweise adiabatischer Quantenberechnungen zu verstehen.
3 Anwendungen der adiabatischen Entwicklung in der Informatik: Hier werden spezifische Algorithmen für MAX-3-SAT und GRAPH ISOMORPHISM im Modell der adiabatischen Entwicklung hergeleitet und ihre Lokalititätseigenschaften diskutiert.
4 Abschätzungen der Erfolgswahrscheinlichkeit: Dieses Kapitel widmet sich der mathematischen Analyse der Erfolgswahrscheinlichkeit, wobei neue Methoden wie Gerschgorin-Kreise und Weinstein-Abschätzungen genutzt werden, um Eigenwertdifferenzen zu klassifizieren.
5 Implementierung: Der praktische Teil der Arbeit beschreibt das Lastenheft, die Softwarearchitektur sowie die Verfahren zur numerischen Bestimmung von Eigenwerten und Eigenvektoren des entwickelten Tools PITA-Quamputation.
6 Zusammenfassung und Ausblick: Das abschließende Kapitel fasst die Ergebnisse der Arbeit zusammen und gibt einen Ausblick auf die Weiterentwicklung adiabatischer Algorithmen.
Schlüsselwörter
Adiabatische Quantenberechnung, Quantenrechner, Hamiltonoperator, MAX-3-SAT, GRAPH ISOMORPHISM, Eigenwertdifferenz, Erfolgswahrscheinlichkeit, PITA-Quamputation, Turingmaschine, Komplexitätstheorie, Gerschgorin-Kreise, Ising-Modell, Quanten-Algorithmen, Simulation, Software-Design.
Häufig gestellte Fragen
Worum geht es in dieser Diplomarbeit grundsätzlich?
Die Arbeit beschäftigt sich mit dem relativ neuen Ansatz der adiabatischen Quantenberechnung, einem Paradigmenwechsel gegenüber klassischen Quantenschaltkreisen, und analysiert deren Anwendungspotenzial sowie die praktische Implementierung durch ein Softwarewerkzeug.
Was sind die zentralen Themenfelder?
Zentrale Felder sind die theoretische Informatik, die Quantenmechanik sowie die numerische lineare Algebra, insbesondere im Kontext von komplexen Problemstellungen wie MAX-3-SAT und GRAPH ISOMORPHISM.
Was ist das primäre Ziel der Arbeit?
Das primäre Ziel ist es, die Laufzeit- und Erfolgswahrscheinlichkeitsanalysen für adiabatische Quantenalgorithmen durch mathematische Abschätzungen zu verbessern und ein Analysewerkzeug namens PITA-Quamputation zu entwickeln.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit nutzt mathematische Formalismen der Quantenmechanik, insbesondere Hamiltonoperatoren und den Adiabatensatz, sowie Methoden der numerischen Informatik zur Eigenwertabschätzung und Algorithmensimulation.
Was wird im Hauptteil behandelt?
Der Hauptteil gliedert sich in die theoretische Herleitung von Algorithmen für MAX-3-SAT und GRAPH ISOMORPHISM, die mathematische Fundierung der Erfolgswahrscheinlichkeitsanalyse sowie die detaillierte Beschreibung der Software-Implementierung.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit wird durch Begriffe wie Adiabatische Quantenberechnung, Hamiltonoperator, Gerschgorin-Kreise, Erfolgswahrscheinlichkeit und die Implementierung einer spezialisierten Softwareumgebung charakterisiert.
Wie unterscheidet sich die adiabatische Entwicklung von Quantenschaltkreisen?
Während Quantenschaltkreise auf sequenziellen unitären Operationen basieren, behält die adiabatische Entwicklung das Gesamtsystem im energetischen Grundzustand, wodurch relative Phasenprobleme vermieden werden können.
Was leistet das Tool PITA-Quamputation?
PITA-Quamputation ermöglicht die Modellierung und Analyse der Eigenwertentwicklung für verschiedene Probleminstanzen und bietet grafische Vergleichsmöglichkeiten für unterschiedliche analytische Abschätzungsverfahren.
- Citar trabajo
- Dipl. Inform. Klaus Fehlker (Autor), 2003, Algorithmen für auf adiabatischer Entwicklung basierende Quantenrechner, Múnich, GRIN Verlag, https://www.grin.com/document/49782
