Universität Dortmund
Fachbereich Informatik
Lehrstuhl für effiziente Algorithmen
und Komplexitätstheorie

Algorithmen für auf adiabatischer Entwicklung basierende Quantenrechner

von:
Klaus Fehlker

Juli 2003

Inhaltsverzeichnis

1 Einleitung ... 3
1.1 Quantenrechner ... 3
1.2 Adiabatische Quantenberechnungen ... 4
1.3 Aufgabenstellung der Diplomarbeit ... 6

2 Quantenmechanische Grundlagen ... 9
2.1 Mathematische Vorbemerkungen ... 9
2.2 Die Schrödingergleichung ... 15
2.3 Die adiabatische Entwicklung ... 19

3 Anwendungen der adiabatischen Entwicklung in der Informatik ... 29
3.1 Grundlagen der theoretischen Informatik ... 29
3.2 Ein Algorithmus für MAX-3-SAT durch adiabatische Entwicklung ... 32
3.3 Ein Algorithmus für GRAPH ISOMORPHISM durch adiabatische Entwicklung ... 40

4 Abschätzungen der Erfolgswahrscheinlichkeit ... 65
4.1 Definitionen und Voraussetzungen an die Hamiltonoperatoren ... 65
4.2 Klassifikation der Eigenwerte ... 66
4.3 Abschätzung der Eigenwertdifferenz durch Gerschgorin-Kreise ... 70
4.4 Abschätzung der Eigenwertdifferenz nach Weinstein ... 77
4.5 Eigenwertberechnung nach Courant und Weyl ... 80
4.6 Analyse der Erfolgswahrscheinlichkeit ... 82

5 Implementierung 89
5.1 Lastenheft ... 89
5.2 GUI-Programmierung mit Qt ... 90
5.3 Die Architektur von PITA-Quamputation ... 91
5.4 Verfahren zur Ermittlung von Eigenwerten und -vektoren ... 96
5.5 Bestimmung der essentiellen Eigenwertdifferenz ... 101
5.6 Vergleich der Analysen der adiabatischen Entwicklung ... 103

6 Zusammenfassung und Ausblick ... 109

A Handbuch ... 111
A.1 Installation ... 111
A.2 Der Programmstart ... 111
A.3 Eingabemöglichkeiten für Probleminstanzen ... 112
A.4 Auswertung ... 113

Literaturverzeichnis ... 117

Kapitel 1

Einleitung

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 7! {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. Der zweite, sehr bekannt gewordene Algorithmus ist der von Lov Grover [Gro96] zur Suche in unstrukturierten Datenbanken. Gesucht wird eine Eingabe, für die eine gegebene Funktion f : {0, 1}n 7! {0, 1} den Wert 1 annimmt. Es darf darin nur ein Orakel für f benutzt werden, welches den Funktionswert einer Eingabe liefert. Im Gegensatz zu klassischen Rechnern, die im Erwartungswert (2n) Orakelaufrufe benötigen, hat der Algorithmus von Grover eine Komplexität von O(2n/2). Quantenrechner haben also für Algorithmen, die lediglich ein Orakel für f benutzen und die Struktur der Funktion nicht anderweitig ausnutzen dürfen, einen quadratischen Komplexitätsvorsprung vor Turingmaschinen. Man kann auch zeigen, dass dieses Ergebnis für Quantenrechner optimal ist.

Doch trotz großer Anstrengungen im Bereich der Quanteninformationsverarbeitung bleiben die Algorithmen von Grover und Shor seit mehreren Jahren die einzigen Algorithmen für Quantenrechner, die nach derzeitigem Kenntnisstand eine effizientere Problemlösung bieten als klassische Rechner. Auch deren physikalische Implementierung sieht sich vor extrem große Probleme gestellt. Die von Chuang et al. entwickelte, momentan leistungsstärkste Realisierung eines Quantenrechners konnte im Dezember 2001 mit Hilfe von sieben Qubits, dem Quantenrechner-Analogon zum klassischen Bit, die Zahl 15 faktorisieren [VSB+01].

Ursache für die Trägheit des Fortschritts ist zum Einen die nicht intuitive Arbeitsweise von Quantenrechnern, welche auf einer überlagerung verschiedener Zustände eines Systems von Qubits arbeiten. Im Gegensatz dazu steht die langjährige Praxis der Informatiker, Systeme zu betrachten, die in jedem Zeitpunkt einen genau definierten Zustand einnehmen. Ein Vergleich mit Randomisierung ist nicht angemessen, da verschiedene Berechnungswege bei Quantencomputern destruktiv interferieren können. Außerdem können Qubits miteinander verschränkt sein, was bedeutet, dass der Zustand des einen Qubits von dem des Anderen abhängt. Diese wichtigen Eigenschaften sind mit klassischer Randomisierung nicht erreichbar.

[...]