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
- Einleitung
- Quantenrechner
- Adiabatische Quantenberechnungen
- Aufgabenstellung der Diplomarbeit
- Quantenmechanische Grundlagen
- Mathematische Vorbemerkungen
- Die Schrödingergleichung
- Die adiabatische Entwicklung
- Anwendungen der adiabatischen Entwicklung in der Informatik
- Grundlagen der theoretischen Informatik
- Ein Algorithmus für MAX-3-SAT durch adiabatische Entwicklung
- Ein Algorithmus für GRAPH ISOMORPHISM durch adiabatische Entwicklung
- Abschätzungen der Erfolgswahrscheinlichkeit
- Definitionen und Voraussetzungen an die Hamiltonoperatoren
- Klassifikation der Eigenwerte
- Abschätzung der Eigenwertdifferenz durch Gerschgorin-Kreise
- Abschätzung der Eigenwertdifferenz nach Weinstein
- Eigenwertberechnung nach Courant und Weyl
- Analyse der Erfolgswahrscheinlichkeit
- Implementierung
- Lastenheft
- GUI-Programmierung mit Qt
- Die Architektur von PITA-Quamputation
- Verfahren zur Ermittlung von Eigenwerten und -vektoren
- Bestimmung der essentiellen Eigenwertdifferenz
- Vergleich der Analysen der adiabatischen Entwicklung
- Zusammenfassung und Ausblick
- Handbuch
- Installation
- Der Programmstart
- Eingabemöglichkeiten für Probleminstanzen
- Auswertung
Zielsetzung und Themenschwerpunkte
Diese Diplomarbeit befasst sich mit der Entwicklung von Algorithmen für Quantencomputer, die auf der adiabatischen Entwicklung basieren. Ziel ist es, die Potenziale dieser Methode für die Lösung komplexer algorithmischer Probleme zu erforschen und praktische Implementierungen zu entwickeln.
- Adiabatische Quantenberechnungen als ein Ansatz zur Konstruktion von Quantenalgorithmen
- Anwendung der adiabatischen Entwicklung auf verschiedene algorithmische Probleme, wie z.B. MAX-3-SAT und GRAPH ISOMORPHISM
- Analyse der Erfolgswahrscheinlichkeit und Abschätzung der Laufzeit von adiabatischen Algorithmen
- Entwicklung einer Software-Implementierung (PITA-Quamputation) zur Simulation und Analyse adiabatisch gesteuerter Quantencomputer
- Bewertung der Praktikabilität und Grenzen von adiabatischen Quantencomputern
Zusammenfassung der Kapitel
- Kapitel 1: Einleitung
Dieses Kapitel gibt eine Einführung in die Thematik der Quantenrechner und der adiabatischen Quantenberechnung. Es werden die grundlegenden Konzepte und die historischen Entwicklungen dieser Gebiete erläutert.
- Kapitel 2: Quantenmechanische Grundlagen
Dieses Kapitel behandelt die relevanten quantenmechanischen Grundlagen, die für das Verständnis der adiabatischen Entwicklung notwendig sind. Es werden die Schrödingergleichung, die Adiabatische Entwicklung und verwandte Konzepte vorgestellt und erklärt.
- Kapitel 3: Anwendungen der adiabatischen Entwicklung in der Informatik
Dieses Kapitel untersucht die Anwendung der adiabatischen Entwicklung in der Informatik. Es werden Algorithmen für MAX-3-SAT und GRAPH ISOMORPHISM vorgestellt, die auf der adiabatischen Entwicklung basieren.
- Kapitel 4: Abschätzungen der Erfolgswahrscheinlichkeit
Dieses Kapitel behandelt die Analyse der Erfolgswahrscheinlichkeit und die Abschätzung der Laufzeit von adiabatischen Algorithmen. Es werden verschiedene Methoden zur Bestimmung der Eigenwertdifferenz, die einen wichtigen Faktor für die Erfolgswahrscheinlichkeit darstellen, vorgestellt und analysiert.
- Kapitel 5: Implementierung
Dieses Kapitel beschreibt die Entwicklung und Implementierung der Software PITA-Quamputation. Es werden die Architektur, die Funktionsweise und die wichtigsten Komponenten der Software erläutert.
Schlüsselwörter
Quantenrechner, adiabatische Entwicklung, Adiabatische Quantenberechnung, MAX-3-SAT, GRAPH ISOMORPHISM, Hamiltonoperator, Eigenwertdifferenz, Erfolgswahrscheinlichkeit, PITA-Quamputation, Software-Implementierung
- Quote paper
- Dipl. Inform. Klaus Fehlker (Author), 2003, Algorithmen für auf adiabatischer Entwicklung basierende Quantenrechner, Munich, GRIN Verlag, https://www.grin.com/document/49782
