Algorithmen für auf adiabatischer Entwicklung basierende Quantenrechner

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.3 Die adiabatische Entwicklung

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.3 Ein Algorithmus für GRAPH ISOMORPHISM durch adiabatische Entwick- lung

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.4 Abschätzung der Eigenwertdifferenz nach Weinstein
4.5 Eigenwertberechnung nach Courant und Weyl
4.6 Analyse der Erfolgswahrscheinlichkeit

5 Implementierung
5.1 Lastenheft
5.2 GUI-Programmierung mit Qt
5.3 Die Architektur von PITA-Quamputation
5.4 Verfahren zur Ermittlung von Eigenwerten und -vektoren
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

Literaturverzeichnis

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 be- reits 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) entwickel- te, 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 Einga- ben 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 Gegen- satz 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 Funk- tion f : {0, 1}n → {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, Syste- me 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 miteinan- der verschränkt sein, was bedeutet, dass der Zustand des einen Qubits von dem des An- deren abhängt. Diese wichtigen Eigenschaften sind mit klassischer Randomisierung nicht erreichbar. Außerdem gehören die theoretischen Modelle der endlichen Quanten-Automaten (QFAs) in keine der klassischen Komplexitätsklassen: Während das einfache Beispiel einer regulären, und somit eher leichten Sprache Lreg = {0∗1∗} für QFAs ein Problem darstellt, wird das klassische Beispiel einer nicht-regulären, also für klassische Automaten nicht er- kennbaren Sprache Lnicht−reg = {0n1n|n ≥ 1} durch 2-Wege-QFAs mit Wahrscheinlichkeit mindestens[12]+ ϵ mit ϵ > 0 erkannt, wie Kondacs und Watrous in [KW97] gezeigt haben.

Zum Anderen muss im Idealfall ein Quantenrechner komplett von der Umwelt abgeschlos- sen sein, um Dekohärenz, also den Verlust von Informationen an das umgebende System und damit die Zerstörung der ÜberlagerungderverschiedenenZustände, zu verhindern. Die heutigen Annäherungen an diesen Idealfall sehen Fehlerkorrekturcodes vor, deren Theorie zwar ausgearbeitet ist, die Implementierung leidet aber immer noch unter großen techni- schen Problemen. Lediglich die Kryptographie kann sich die Quanteneigenschaften bereits kommerziell zu Nutze machen, wie Naica-Loebell in ihrem Artikel [NL02] schrieb.

1.2 Adiabatische Quantenberechnungen

Die bisher für Quantenrechner gefundenen Algorithmen werden in Analogie zu klassischen Rechnern auf Schaltkreisen, so genannten Quantenschaltkreisen (QSKs), aufgebaut. Diese unterliegen bestimmten Einschränkungen aufgrund der Tatsache, dass für sie, unter ande- rem wegen ihrer Größe, nicht die klassische Näherung der quantenphysikalischen Gesetze gilt. Diese klassische Näherung erlaubt es z.B. mit klassischen Bits auch irreversible Rechenoperationen durchzuführen.

Diese Diplomarbeit beschäftigt sich mit einem relativ neuen Ansatz im Bereich der Quan- tenrechner, der adiabatischen Quantenberechnung. Die Funktionsweise ist hierbei grund- legend anders als bei Quantenschaltkreisen, da sich das Gesamtsystem aus den n Qubits immer im jeweiligen Grundzustand |Ψ0〉, also dem Zustand mit der geringsten Energie, befindet. Dieser Grundzustand, und somit auch dessen Energie, hängt sowohl von der je- weiligen Realisierung eines Qubits als auch von dessen Umgebung ab. Die Umgebung kann dabei z.B. aus weiteren Qubits bestehen, so dass die Zustände aller Qubits voneinander abhängen können. Bei den bisher üblichen Quantenrechnern, die auf Quantenschaltkreisen aufbauten, ging man davon aus, die Qubits direkt zu manipulieren um eine gewünschte Überlagerung von Einzelzuständen zu erhalten. Ziel ist es bei der adiabatischen Entwick- lung jedoch, eine Umgebung zu konstruieren, so dass der Grundzustand innerhalb dieser Umgebung zu Anfang eine einfach zu konstruierende Überlagerung aller möglichen Einga- ben für das zu lösende Problem kodiert. Der Verlauf des Algorithmus gestaltet sich nun so, dass die Umgebung derart verändert wird, dass am Ende der Grundzustand innerhalb dieser Umgebung genau eine Lösung der gegebenen Instanz des Problems repräsentiert. Unter bestimmten Bedingungen bleibt das System im Grundzustand und man erhält die Lösung des Problems.

In der Quantenmechanik wird dies durch folgenden Formalismus ausgedrückt: Die ener- getisch möglichen Zustände werden durch eine Matrix H, dem sogenannten Hamiltonope- rator, repräsentiert. Die Eigenwerte dieser Matrix bestimmen die möglichen Energien, die ein System unter dem Einfluss dieses Operators haben kann. Die dazugehörigen Eigen- vektoren sind die Zustände, in denen sich das System befinden kann. Die adiabatische Entwicklung gestaltet sich nun so, dass der Gesamt-Hamiltonoperator eine Interpolation ist zwischen einem Basis-Hamiltonoperator HB , dessen Grundzustand leicht zu erstellen ist, und einem Problem-Hamiltonoperator HP , dessen Grundzustand die Lösung der be- trachteten Probleminstanz kodiert. Laut dem Adiabatensatz, siehe z.B. [Mes79a], bleibt das System im Grundzustand, solange die Interpolation langsam genug vonstatten geht. Man erhält also die Lösung einer Probleminstanz dadurch, dass man ein System aus Qubits im Grundzustand zu HB initialisiert und dieses System sich in den Grundzustand zu HP entwickeln lässt. Am Ende misst man diesen Grundzustand und erhält eine Lösung für die Probleminstanz.

Eine untere Schranke für die Dauer der Entwicklung ist das eigentliche Problem bei der Analyse der adiabatischen Entwicklung. Die übliche Abschätzung für die Entwicklungszeit

T lautet gemäß [vDMV02]

Abbildung in dieser Leseprobe nicht enthalten

(1.1)

[Abbildung in dieser Leseprobe nicht enthalten] dieSupremumsnorm(s.[vDMV[02]])desOperators,welcheauchGren- zennorm genannt wird (s. [Sto[99]]) und gmin ist der minimale Abstand der beiden niedrigs- ten Eigenwerte von H(t) während der Entwicklung. Die beiden Energieniveaus sind für ein einfaches Beispiel in Abbildung 1.1 dargestellt. Hierin ist auf der x-Achse der Inter- polationsparameter s(t) ∈ [0, 1], der die zeitliche Kontrolle der Entwicklung übernimmt, aufgetragen. Die untere Kurve deutet an, wie sich die Energie des Grundzustands entwi- ckelt, und die obere Kurve beschreibt die Entwicklung des ersten Energieniveaus. Der Wert gmin wird in diesem Fall der Abstand der Niveaus zum Zeitpunkt s = 0.5 sein.

Neben der Angabe der Entwicklungszeit stellt der Energieoperator HP , in den die Problem- instanz kodiert wird, ein weiteres Problem dar. Dieser muss lokal sein. Das bedeutet, dass das Problem in eine polynomielle Anzahl nicht notwendigerweise disjunkter Teilprobleme zerfallen muss, die sich jeweils nur auf eine konstante Anzahl von Qubits auswirken. Diese Einschränkung rührt daher, dass die Qubits untereinander nur beschränkt wechselwirken können.

Dadurch, dass die Teilprobleme im Allgemeinen nicht disjunkt sind, entstehen Überschnei- dungen. Bei Graphproblemen sind die Teilprobleme z.B. Teilgraphen und die Überschnei- dungen z.B. Knoten oder auch Kanten, die in verschiedenen Teilgraphen vorkommen. Die Lokalitätsforderung sagt nun zudem aus, dass diese Überschneidungen nicht zu groß sein sollten.

1.3 Aufgabenstellung der Diplomarbeit

Mit dieser Diplomarbeit sollte untersucht werden, inwieweit eine verbesserte Analyse der Laufzeit der adiabatischen Entwicklung unter anderem durch Eigenwertabschätzungen er- reicht werden kann. Weiterhin sollte ein Werkzeug geschaffen werden, welches dem Leser die Wirkungsweise der adiabatischen Quantenberechnung auf verschiedenen Probleminstanzen näherbringt.

1.3.1 Theoretischer Anteil dieser Arbeit

Bisherige Analysen von adiabatischen Quantenberechnungen nutzen die lineare Interpola- tion zwischen dem Basis-Hamiltonoperator und dem Problem-Hamiltonoperator mit dem Interpolationsparameter s. Die Hamiltonoperatoren sind Matrizen, die die energetisch möglichen Zustände bestimmen und in denen sich die von außen mögliche Steuerung des Systems niederschlägt. s verknüpft man meist durch die Gleichung s(t) =tT mitderZeittundder Gesamtdauer der Entwicklung T .

Abbildung in dieser Leseprobe nicht enthalten

Die Dauer wird maßgeblich von dem reziproken Quadrat der kleinsten Differenz der beiden untersten Energieniveaus bestimmt (s. Abbildung 1.1). Da die Differenz bisher in den meis- ten Simulationen ein ausgeprägtes, lokales Minimum durchläuft, können große Abschnitte wesentlich schneller durchlaufen werden als es (1.1) angibt. Eine bessere Abschätzung erhält man, wenn man die Entwicklung in infinitesimal kleine Abschnitte einteilt und jeden Abschnitt mit der geforderten Zeit durchläuft. Die dadurch gewonnene asymptotische untere Schranke (s. z.B. [vDMV02])

Abbildung in dieser Leseprobe nicht enthalten

(1.3)

ist analytisch für die meisten Probleme nicht zu lösen. Im Rahmen der Diplomarbeit sollten Ideen entwickelt werden, inwieweit diese Abschätzung konkretisiert werden kann.

Weiterhin sollte ein Algorithmus für das Problem GRAPH ISOMORPHISM entwickelt werden und hinsichtlich einer möglichen Realisierbarkeit auf derzeitigen Implementierungen von Quantenrechnern analysiert werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1.1: Die untersten Energieniveaus einer adiabatischen Entwicklung

1.3.2 Praktischer Anteil dieser Arbeit

Praktisches Ziel dieser Arbeit war es, ein Werkzeug zu entwickeln, welches die Analyse des Algorithmus mittels adiabatischer Entwicklung für die Probleme MAX-3-SAT und GRAPH ISOMORPHISM, zwei Probleme aus der theoretischen Informatik, unterstützt. Folgende Aufgaben sollten dabei im Besonderen behandelt werden:

1. Implementierung effizienter und ergonomischer Methoden zur Eingabe einer Pro- bleminstanz.
2. Entwicklung eines modularen Konzeptes, so dass die Anwendung auch zur Analyse von adiabatischen Entwicklungen bezogen auf andere Probleme angewandt werden kann.
3. Plattformunabhängigkeit, so dass die Anwendung, sowohl unter Linux/Unix als auch unter Windows läuft.
4. Die zentrale Problematik bei der adiabatischen Entwicklung ist der Abstand be- stimmter Energieniveaus. Dieser Abstand sollte visualisiert werden, wobei der An- wender die Zusammenhänge der Niveaus von der Anwendung erläutert bekommen soll.
5. Einfluss der Ergebnisse aus dem theoretischen Teil der Arbeit.
6. Hinsichtlich der Tatsache, dass eine Verkürzung der Laufzeit der Entwicklung ne- gative Auswirkungen auf das Ergebnis hat, ist es wünschenswert, die Möglichkeit zu haben, die Gesamtzeit der Entwicklung möglichst genau vorherzusagen. Dieser Anforderung sollte nachgegangen werden.
7. Darstellung des Grundzustandes zu jedem Zeitpunkt der Entwicklung. Die Transfor- mation dieses Zustandes von einer Überlagerung aller möglichen Eingaben hin zu der Lösung des Problems sollte somit nachvollziehbar sein.

Die Anwendung trägt den Namen Performance Improvement Tool for Adiabatic Quantum Computation, kurz PITA-Quamputation.

Kapitel 2 Quantenmechanische Grundlagen

In diesem Kapitel werden wir die Grundlagen zusammentragen, auf denen der Formalismus der Quantenmechanik aufbaut. Das Ziel ist es, einen Überblick zu bekommen, mit dem wir das Prinzip der adiabatischen Entwicklung verstehen können.

2.1 Mathematische Vorbemerkungen

In der Quantenmechanik wird im Allgemeinen mit Operatoren gerechnet, also mit Abbildungen von Funktionen auf Funktionen. Im Folgenden beschränken wir uns auf Räume mit endlicher Dimension N . Da bei den Operatoren aber immer die Linearität vorausgesetzt wird, können wir diese auch als Matrizen betrachten.

Definition 2.1 (hermitesch, unitär) Eine Matrix U heißt unitär, wenn gilt

Abbildung in dieser Leseprobe nicht enthalten

mit I = Identität. U† entsteht aus U durch Komplexkonjugation und Transposition. Gilt für eine Matrix H

Abbildung in dieser Leseprobe nicht enthalten

so nennt man H hermitesch oder selbstadjungiert.

Bemerkung 2.2 Physikalische Größen werden durch hermitesche Matrizen beschrieben, da diese reelle Eigenwerte besitzen.¹

Die Ursache dafür, dass gerade die hermiteschen Operatoren physikalische Größen, soge- nannte Observablen, beschreiben, ist, dass die Eigenwerte der Operatoren eben genau die möglichen Werte der zugehörigen Größen repräsentieren. Vereinfacht können wir den Zusammenhang so verstehen: Wenn die Energie eines Teilchens durch einen Operator mit den Eigenwerten 10 und 100 dargestellt wird, kann dieses Teilchen nur die Energien 10 und 100 Joule haben. Weil physikalische Größen (Energie, Ort, Impuls, ...) aber nur reelle Werte annehmen können - es gibt keinen imaginären Ort -, dürfen Operatoren nur reelle Eigenwerte besitzen, wenn sie diese Größen repräsentieren sollen.

Definition 2.3 (Dirac-Notation, ket- und bra-Vektoren) Im endlichdimensionalen Fall werden Zustände von Systemen durch normierte Vektoren des Vektorraums CN beschrieben. In der Dirac-Notation benutzt man für einen Zustandsvektor zum Zustand Ψ den ket-Vektor |Ψ〉. Der dazu duale bra-Vektor 〈Ψ| entsteht durch Komplexkonjugation und Transposition von |Ψ〉. Die Norm |·| für einen Zustand |Ψ〉 ist definiert als die Wurzel des Skalarproduktes der Vektoren 〈Ψ| und |Ψ〉:

Abbildung in dieser Leseprobe nicht enthalten

Die Namen bra und ket kommen von dem Wort braket (engl. Klammer) in Zusammenhang mit der Schreibweise des Skalarproduktes. Den Zustandsraum nennt man auch Hilbertraum, welcher im endlichdimensionalen Fall definiert ist als ein vollständiger Vektorraum mit zugehörigem Skalarprodukt. Die Norm ∥·∥ für Matrizen H des Hilbertraums H ist üblicherweise die Grenzennorm lub2(H) aus [Sto99]

Abbildung in dieser Leseprobe nicht enthalten

die übereinstimmt mit der Wurzel des größten Eigenwertes λmax der Matrix H†H. Üblich sind auch die Bezeichnungen

”Operatornorm“oder ”Supremumsnorm“.

Bemerkung 2.4 Jede hermitesche Matrix H besitzt eine Basis aus Eigenvektoren |k〉, die die Eigenzustände eines Systems repräsentieren. Sie genügen der Eigenwertgleichung

Abbildung in dieser Leseprobe nicht enthalten

mit λk ∈ R Eigenwert zu |k〉. Der Operator lässt sich in dieser Basis darstellen als ∑

Abbildung in dieser Leseprobe nicht enthalten

Im Folgenden bezeichnen wir die Indizes mit dem Buchstaben k, um einer Verwechslung mit ı = √−1 vorzubeugen. Mit Hilfe des Gram-Schmidt-Verfahrens [NC00a] können die Eigenvektoren zu einer orthonormalen Basis transformiert werden, so dass fortan |k〉 einen Basisvektor einer orthonormalen Basis darstellt. Es gilt also für zwei dieser Basisvektoren |k₁〉 und |k₂〉 mit δk₁,k₂ das Kroneckerprodukt

Abbildung in dieser Leseprobe nicht enthalten

(2.5)

Falls der Operator H von einem Parameter, z.B. t, abhängig ist, so schreiben wir die Abhängigkeit der Eigenzustände von diesem Parameter aufgrund der Übersichtlichkeit nicht als Argument, sondern als Index an den Zustand. So ist |k〉t ein Eigenzustand von H(t) zum Eigenwert λk(t). Wir wollen aber die betrachteten Systeme soweit abstrahieren, dass uns weitere mögliche Abhängigkeiten, z.B. von Ortskoordinaten, nicht interessieren. Da diese aber prinzipiell existieren können verwenden wir für Ableitungen nach t die Sym- bole der partiellen Ableitung [Abbildung in dieser Leseprobe nicht enthalten]

Definition 2.5 (kommutierende Operatoren) Wenn zwei Operatoren in Rechnungen vertauschbar sind, so sagt man, sie kommutieren. Man notiert dazu

[A, B] = 0 (2.6)

mit

[A, B] := A B − B A. (2.7)

Üblich ist auch der etwas gewöhnungsbedürftige Ausdruck eH, in dem der Operator im Exponenten steht. Seine Wirkung auf einen Zustand |Ψ〉 erschließt sich aus der Reihenentwicklung der Exponentialfunktion. Der Zustand |Ψ〉 wird dabei nach einer Basis von Eigenzuständen |k〉 des Operators H entwickelt:

Abbildung in dieser Leseprobe nicht enthalten

Wenn ein Operator im Exponenten steht, so bedeutet dies also, dass wir den Zustand, auf den dieser Operator wirkt, in eine Basis aus Eigenzuständen des Operators entwickeln müssen. Der k-te Summand dieser Entwicklung erhält sodann als zusätzlichen Koeffizien- ten eλk , mit λk Eigenwert zum Eigenzustand |k〉. Weitere konstante Vorfaktoren vor dem Operator im Exponenten übertragen sich auf den Eigenwert im Exponenten, wie sich leicht nachrechnen lässt.

Falls H von einem Parameter t abhängig ist, so gilt insbesondere

Abbildung in dieser Leseprobe nicht enthalten

12 Kapitel 2. Quantenmechanische Grundlagen

Das Qubit

Um den Begriff Qubit als das quantenmechanische Analogon zum klassischen Bit ein- zuführen, können wir z.B. ein Elektron betrachten. Elementarteilchen haben eine physi- kalische Eigenschaft, die wir Spin nennen und die wir als Eigendrehimpuls des Teilchens interpretieren können. Diese Observable kann für Elektronen bezüglich einer vorgegebenen Achse genau zwei Werte annehmen (Der Einfachheit halber seien die möglichen Werte ±1). Der Spin ist also eine Observable, bzgl. der das Elektron genau zwei Zustände annehmen kann. Ein solches Zwei-Zustands-System nennt man Qubit. Die hermiteschen Matrizen, die die Spin-Observablen für die drei Raumrichtungen x, y und z beschreiben, lauten

Abbildung in dieser Leseprobe nicht enthalten

mit zugeh¨origen orthonormalen Eigenzust¨anden zu den Eigenwerten ±1. Die Basiszust¨ande der Basis, in der die Zust¨ande und Matrizen angeben sind, werden durch die Eigenvektoren von a2 gegeben und wir schreiben k¨urzer

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Ein Qubit kann sich nun in einer ¨ Uberlagerung, oder auch Superposition von verschiedenen Eigenzust¨anden befinden. Die Entwicklung eines beliebigen Zustandes | i nach diesen Eigenzust¨anden induziert dabei die im Allgemeinen komplexen Koeffizienten ak. Diese Koeffizienten werden Amplituden genannt.

Abbildung in dieser Leseprobe nicht enthalten

Wird ein Qubit gemessen, welches sich im Zustand (2.13) befindet, so misst man mit Wahrscheinlichkeit |ak|2 denWert λk und das System befindet sich anschließend im Zustand | i = |ki. Dies wird im Allgemeinen als Kopenhagener Deutung der Quantenph¨anomene bezeichnet. Die Wahrscheinlichkeitsinterpretation ist durch die Normierung des Zustandes | i mathematisch abgesichert. Es gilt somit:

Abbildung in dieser Leseprobe nicht enthalten

Die Tatsache, dass die Amplituden nicht unbedingt positiv sein m¨ussen, sondern im Allgemeinen komplex sind, begr¨undet den entscheidenden Vorteil der Interferenz gegen¨uber klassischen, probabilistischen Methoden. Siehe hierzu auch Nielsen und Chuang [NC00b].

Mehrere Qubits

Unter dem Begriff System von Qubits verstehen wir einen Zusammenhang von sich untereinander beeinflussenden Qubits. Mit Hilfe des sowohl für Vektoren als auch für Matrizen definierten Kroneckerproduktes

Abbildung in dieser Leseprobe nicht enthalten

können wir ein System von Qubits mathematisch beschreiben. Setzt sich ein System aus n Qubits zusammen, so schreiben wir die resultierenden Eigenzustände des Gesamtsystems durch das Kroneckerprodukt der Eigenzustände des Spin-Operators σ_z :

Abbildung in dieser Leseprobe nicht enthalten

Hierin wird k als Binärzahl der 0-1-Folge k₁ . . . kn aufgefasst. Sind die einzelnen Qubits physikalisch unabhängig voneinander, so lässt sich ein Zustand |Ψ〉 des Gesamtsystems faktorisieren zu

Abbildung in dieser Leseprobe nicht enthalten

Falls dies nicht möglich sein sollte, so nennen wir die Qubits miteinander verschränkt. Ein Beispiel für zwei verschränkte Qubits ist das EPR-Paar benannt nach seinen Entdeckern Einstein, Podolsky und Rosen. Bei einer Messung können also nur die Zustände |00〉 oder |11〉 auftreten. Die Messungen der Qubits sind also abhängig voneinander - daher der Ausdruck verschränkt.

Abbildung in dieser Leseprobe nicht enthalten

Auch Operatoren können separierbar sein, so dass sich die Wirkung des Operators auf einzelne Qubits explizit angeben lässt. Für diese Separation wird ebenfalls das ⊗-Zeichen verwendet:

Abbildung in dieser Leseprobe nicht enthalten

Bemerkung 2.6 Operatoren, die nur auf 1, 2 oder eine Menge von Qubits eine nicht- triviale Wirkung haben, bezeichnen wir mit geklammerten oberen Indizes der Qubits oder der Qubitmenge, auf die der Operator wirkt. Auf die anderen Qubits wirkt dann die Iden- tität.

Basiswechsel

Ein Wechsel zwischen orthonormalen Basen kann im Allgemeinen durch unitäre Matrizen erfolgen. Ein Basiswechsel ist jedoch nur ein mathematisches Hilfsmittel ohne physikalische Auswirkung, wie folgende Bemerkung zeigt:

Bemerkung 2.7 Die Eigenwerte sind unabhängig von der betrachteten orthonormalen Ba- sis.

Beweis: Es gelte: H |Ψ〉 = λ |Ψ〉, also ist λ der Eigenwert des Operators H zum Eigenzu- stand |Ψ〉. Weiterhin sei U der unitäre Operator, der den Basiswechsel durchführt. Dann folgt

Abbildung in dieser Leseprobe nicht enthalten

Ein Basiswechsel bedeutet also lediglich eine andere Darstellung der Operatoren und Zu- stände. Der Wert einer Größe, also der Eigenwert dieses Operators, verändert sich hierdurch nicht.

Ein wichtiges Mittel, unter anderem für Basiswechsel, ist die in [NC00a] bewiesene Vollständigkeitsrelation

Abbildung in dieser Leseprobe nicht enthalten

Wollen wir einen Zustand, der in einer Basis |k〉 , k ∈ {0, . . . N − 1} aus orthonormalen Eigenvektoren zu einem Operator H gegeben ist, in eine Darstellung bezüglich einer Basis |k′〉 , k ∈ {0, . . . N −1} aus orthonormalen Eigenvektoren zu einem Operator H′ umwandeln, so können wir dies leicht mit Hilfe von (2.19) durchführen:

Abbildung in dieser Leseprobe nicht enthalten

Die Koeffizienten in der neuen Basis sind nun durch die Klammer gegeben. Das Skalarprodukt 〈k′|k〉 wird im Englischen auch als inneres Produkt der beiden Vektoren 〈k′| und |k〉 bezeichnet. Für zwei Basisvektoren der gleichen orthonormalen Basis ist dies 0 für verschiedene und 1 für identische Basisvektoren. Drücken wir die neuen Basisvektoren in der Basis der alten aus - oder umgekehrt -, so können wir mit Hilfe des Skalarprodukts die Koeffizienten in (2.20) berechnen.

2.2 Die Schrödingergleichung

Die Schrödingergleichung hat in der Quantenmechanik eine sehr große Bedeutung. Viele quantenmechanische Problemstellungen lassen sich darauf reduzieren, für eine gegebene Energieverteilung die Lösungen der dazugehörigen Schrödingergleichung zu finden. Dabei wollen wir hier nicht den allgemeinen unendlichdimensionalen Fall betrachten, sondern die aus dem vorherigen Abschnitt bekannten Grundlagen für Zustände aus Hilberträumen mit endlicher Dimension weiterführen.

Definition 2.8 (zeitabhängige Schrödingergleichung) Die zeitabhängige Schrödingergleichung ist eine Differentialgleichung der Form in der die Lösungen |Ψ〉t die möglichen Zustände eines gegebenen Systems beschreiben. ℏ ist das Plancksche Wirkungsquantum dividiert durch 2π, ℏ = 1.05457 · 10[34]J s. Der Operator H(t) ist der Hamiltonoperator, der auch Energieoperator genannt wird, da er die Dimension einer Energie hat. Seine Eigenwerte Ek(t) sind die möglichen Energiewerte, die ein Teilchen oder auch ein ganzes System von Teilchen besitzen kann.

Abbildung in dieser Leseprobe nicht enthalten

Der Zustand selbst wird durch die Amplituden beschrieben, die er in der Darstellung einer bestimmten Basis, zum Beispiel aus den zu H(t) gehörenden Eigenzuständen |k〉t, annimmt.

Definition 2.9 (Grundzustand, degenerierte Zustände) Der Grundzustand eines Sy- stems ist derjenige Eigenzustand zu H(t), welcher den niedrigsten Energieeigenwert besitzt. Dieser wird mit |0〉t bezeichnet. Unter Umständen gibt es mehrere Eigenzustände zum glei- chen Energieeigenwert und man sagt dann, der Zustand sei degeneriert oder entartet.

Das System befindet sich also zu einem Zeitpunkt t′ im Grundzustand, wenn gilt: [Abbildung in dieser Leseprobe nicht enthalten]

Abbildung in dieser Leseprobe nicht enthalten

Falls H unabhängig von t ist, so existiert die allgemeine, formale Lösung wie sich durch einsetzen in (2.21) leicht verifizieren lässt. |ΨS 〉t stellt hierbei einen zeitabhängigen Zustandsvektor dar, der gleichzeitig Lösung der Schrödingergleichung ist. |ΨH 〉 ist die zeitunabhängige Komponente dieses Zustandes. Weiterhin sagt man, |ΨS 〉 ist eine Lösung im Schrödingerbild und |ΨH 〉 ist eine Lösung im Heisenbergbild. Dieser Aussage werden wir im nächsten Abschnitt genauer nachgehen.

2.2.1 Das Wechselwirkungsbild

In der Quantenmechanik werden hauptsächlich drei Ansätze zur Lösung der Schrödingergleichung mit zeitunabhängigem Hamiltonoperator H angeboten.

Das nach Erwin Schrödinger benannte Schrödingerbild stellt die Zusammenhänge so dar, wie es in Gleichung (2.21) beschrieben wurde. Wenn der Hamiltonoperator zeitunabhängig ist, dann wird die zeitliche Entwicklung der Zustände durch (2.22) beschrieben.

Werner Heisenberg favorisierte hingegen Zustände, die sich über die Zeit nicht ändern. Deshalb führte er mit Hilfe des unitären Operators S†(t) = eℏ Ht und des zeitunabhängigen Hamiltonoperators H aus dem Schrödingerbild eine Transformation durch. Der Zustand |ΨS 〉t aus dem Schrödingerbild wird zu S†(t) · |ΨS 〉t = |ΨH 〉 im Heisenbergbild und ist zeitunabhängig.

Die Schrödingergleichung im Heisenbergbild hat nun die folgende Gestalt:

Wollen wir nun Situationen beschreiben, in denen zwei oder mehrere Teilchen miteinander in Wechselwirkung treten, z.B. ein freies Elektron, welches in die Nähe eines Atomes gelangt, so können wir das Wechselwirkungsbild verwenden. Der Hamiltonoperator kann dann aufgespalten werden in die Summanden H0 und V , wobei letzterer den Einfluss der Wechselwirkung enthält. H0 beschreibt die energetisch möglichen Zustände der einzelnen Teilchen, wenn man sie isoliert voneinander betrachtet.

Um nun einen gegebenen Zusammenhang, z.B. die Schrödingergleichung eines Systems, in das Wechselwirkungsbild zu transformieren, benutzen wir die unitäre Transformation Es sei angemerkt, dass die beiden Operatoren H0 und U (t) kommutieren, da sie bzgl. der gleichen Basis diagonalisierbar sind. Sie dürfen in Gleichungen also vertauscht werden. Die damit aus (2.21) resultierende Differentialgleichung lautet: ∂

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Der Vorteil des Wechselwirkungsbildes ist, dass die Lösungen ohne Wechselwirkung meist gut bekannt sind. Wir stellen uns ein einfaches Atom vor, in dem die Elektronen ihre sta- tionären Zustände in den einzelnen Energieniveaus eingenommen haben. Die Wechselwir- kung erfolgt nun mit einem freien Elektron, welches unter anderem durch seine elektrische Anziehungskraft den Hamiltonoperator beeinflusst. Dadurch, dass die Zeitabhängigkeit der Lösungen von (2.26) ausschließlich durch diese Wechselwirkung VW (t) beeinflusst wird, ist die Berechnung der Zustände |ΨW 〉t wesentlich einfacher im Vergleich zu der von |ΨS 〉_t.

Die Wechselwirkung V kann im Allgemeinen selbst noch von der Zeit abhängen wie z.B. bei der adiabatischen Entwicklung. Der daraus resultierende Hamiltonoperator H(t) würde die Gleichung (2.21) zu komplex machen. Ohne den Ansatz des Wechselwirkungsbildes wäre eine analytische Lösung für die Zeitentwicklung der Zustände nicht herzuleiten. Aus (2.26) lassen sich jedoch nützliche Näherungen ableiten, wie z.B. bei Dawydow [Daw73].

2.2.2 Das Bild der sich drehenden Achsen

Für den Beweis des Adiabatensatzes, auf dem diese Arbeit aufbaut, ist es notwendig, das Bild der sich drehenden Achsen einzuführen. Im Allgemeinen kann ein Hamiltonoperator H(t) zeitabhängig sein und hat demnach zeitabhängige Eigenwerte und -vektoren. Letztere werden als sich verändernde Eigenräume, bzw. laut [Mes79a] als sich drehende Achsen aufgefasst, so dass wir H(t) durch die Einführung von Projektionsoperatoren Pk(t) auf diese Achsen wie folgt schreiben können:

Abbildung in dieser Leseprobe nicht enthalten

Diese Projektionsoperatoren, die die Drehungen der Achsen beinhalten, können wir mit einem geeigneten, unitären Operator A(t) auch schreiben als

Abbildung in dieser Leseprobe nicht enthalten

Der Drehoperator A†(t) führt also eine Drehung auf die Achsen zum Zeitpunkt t = 0 durch. Die Projektion erfolgt nun auf die k-te Achse zu t = 0 und der dadurch erhaltene Zustand wird anschließend auf die k-te Achse zum Zeitpunkt t zurück gedreht. Analog zum Wechselwirkungsbild transformiert sich der Hamiltonoperator beim Übergang in das Bild der sich drehenden Achsen nun zu Wir erkennen, dass im Bild der sich drehenden Achsen lediglich die Eigenwerte, nicht je- doch die Projektionsoperatoren zeitabhängig sind. Diese müssen also nur einmal für den Zeitpunkt t = 0 berechnet werden. Den Zustand transformieren wir analog zum Wechsel- wirkungsbild zu

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

und den Hamiltonoperator zu

Abbildung in dieser Leseprobe nicht enthalten

so dass die Schrödingergleichung im Wechselwirkungsbild die Form (2.34) hat. Diese erhalten wir aus der Schrödingergleichung im Schrödingerbild wie folgt:

Abbildung in dieser Leseprobe nicht enthalten

Mit diesen Vorbemerkungen sollten wir nun in der Lage sein, den Beweis aus [Mes[79]a] des im nächsten Kapitel besprochenen Adiabatensatzes, auf dem die Diplomarbeit aufbaut, nachvollziehen zu können. Als umfassende Lehrbücher über Quantenmechanik für eine tiefergehende Untersuchung haben sich z.B. Messiah [Mes[79]b] und [Mes[79]a], sowie Dawydow [Daw[73]] bewährt.

2.3 Die adiabatische Entwicklung

Als adiabatische ( = ohne Wärmeaustausch) Entwicklung wird ein zeitlich fortschreitender Prozess bezeichnet, der in einem isolierten System abläuft und während der Prozessdauer näherungsweise keine Energie mit seiner Umgebung austauscht. Das Attribut ”adiabatisch“ wird nicht im strengen Sinne benutzt. Der Austausch von Energie findet jedoch so langsam statt, dass der gesamte Vorgang als adiabatisch bezeichnet werden kann.

Abbildung in dieser Leseprobe nicht enthalten

Vom mathematischen Standpunkt her setzen wir bei der adiabatischen Entwicklung einen zeitabhängigen Hamiltonoperator an, und betrachten die Zeitentwicklung für Fälle, in denen T sehr groß wird. Dies bedeutet, dass die Entwicklung vom anfänglichen Operator H0 zum Zieloperator H1 sehr langsam vollzogen wird. Aufgrund der einfacheren Notation substituieren wir den TermtT.

Lemma 2.10 Sei s :=tT, dann lautet die Schrödingergleichung im Bild der sich drehenden Achsen mit dem Hamiltonoperator (2.36)

Abbildung in dieser Leseprobe nicht enthalten

Beweis: Diese Gleichung unterscheidet sich von (2.34) nur durch den Faktor T vor H(A)(t). Dieser entsteht durch die Substitution von t durch s und Anwendung der Kettenregel auf der linken Seite und in K(A)(s) (s. (2.35)). ⋄

Der Adiabatensatz lautet nun gemäß [Mes79a] wie folgt:

Satz 2.11 (Adiabatensatz) Seien die Definitionen wie in Lemma 2.10 und |ΨA〉s eine Lösung der Schrödingergleichung aus diesem Lemma. Weiterhin sei Pk(s) der zweimal stetig differenzierbare Projektionsoperator auf die nichtentarteten, orthonormalen Eigenzustände |k〉s des Hamiltonoperators H(s) und UT (s) der Operator, der die von T · H(s) induzierte Zeitentwicklung der Zustände im Schrödingerbild beschreibt:

Abbildung in dieser Leseprobe nicht enthalten

Dann folgt, dass für große T das System in jedem Zeitpunkt s nahe einem Eigenzustand ist, sofern es sich zu Anfang in einem Eigenzustand befunden hat:

Abbildung in dieser Leseprobe nicht enthalten

Im asymptotischen Grenzfall stimmt also die Projektion eines über die Zeit entwickelten Zustandes auf einen Eigenzustand |k〉s zu einem beliebigen Zeitpunkt s überein mit dem über die Zeit bis zu s entwickelten Grundzustand |k〉0.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Sei |ΦT 〉s eine Lösung der Näherung der Schrödingergleichung aus Lemma 2.10. Dann bezeichnen wirals adiabatische Näherung, worin A die Drehung des Bildwechsels beschreibt.

Dies bedeutet: Befindet sich das System am Anfang der Entwicklung im Eigenzustand |k〉s=0 und hat es dort einen bestimmten Energieeigenwert λk(s = 0), so hat für große Entwicklungsdauern T der Eigenzustand |k〉s während der Entwicklung bis zum Zeitpunkt s = 1 einen großen Anteil am Zustand |Ψ〉s des Systems. Näherungsweise können wir annehmen, dass das System während der Entwicklung in diesem Eigenzustand |k〉s von H(s) zum Eigenwert λk(s) bleibt. Insbesondere bleibt ein System mit hoher Wahrscheinlichkeit im Grundzustand, wenn es sich zu Anfang in diesem befunden hat. Eine obere Schranke für den Fehler dieser Annäherung liefert der Adiabatensatz.

Als Voraussetzung wird dabei meist genannt, dass die Zustände nicht entartet sind, zu ei- nem Eigenwert also nicht mehrere Zustände existieren. In unseren weiteren Überlegungen nehmen wir jedoch an, dass es ausreicht, wenn der anfangs angenommene Eigenzustand während der Entwicklung nicht entartet ist. Weiterhin nehmen wir für die Anwendungen des Adiabatensatzes in späteren Kapiteln an, dass die Eigenvektoren stetig in s differen- zierbare Funktionen sind und die Voraussetzungen des Adiabatensatzes somit erfüllt sind.

2.3.1 Gültigkeit und Dauer der adiabatischen Näherung

Eine genaue Herleitung des Adiabatensatzes übersteigt den Rahmen dieser Diplomarbeit, da der Beweis recht langwierig ist. Ein wichtiges Element ist jedoch eine analytische Darstellung der Wahrscheinlichkeit pi→j , mit der ein System von dem Eigenzustand |i〉0 des ursprünglichen Hamiltonoperators in einen Eigenzustand |j〉1 von H1 übergeht. Falls die Voraussetzungen des Adiabatensatzes erfüllt sind und somit unter anderem der betrachtete Zustand im Laufe der Entwicklung nicht entartet ist, dann folgt für pi→j

Abbildung in dieser Leseprobe nicht enthalten

wobei die Gleichungen dem Messiah [Mes79a] §17.2.7 entnommen wurden. Als Übungsaufgabe finden wir an dieser Stelle das folgende Lemma:

Lemma 2.12 Für i = j, ωj,i :=λj(t)−λi(t)

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

mit |0〉_t , |1〉_t , . . . Vektoren einer orthonormalen Basis aus Eigenvektoren zu H(t). Mit der Produktregel folgt hieraus

Abbildung in dieser Leseprobe nicht enthalten

Da die Vektoren |k〉 orthonormal sind, folgt nun mitdie Behauptung.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Wir erhalten nun aus (2.45) eine obere Schranke für die Wahrscheinlichkeit ϵ, einen Zustand

Abbildung in dieser Leseprobe nicht enthalten

Daraus folgt für die Dauer T (ϵ), bei der der Zustand |i〉t mit Wahrscheinlichkeit kleiner als ϵ verlassen wird:

Abbildung in dieser Leseprobe nicht enthalten

Diese Abschätzung wird meist angenähert durch die Wahrscheinlichkeit, dass sich der Zustand in den nächsten benachbarten, bzw. bei Betrachtung des Grundzustandes in den ersten, angeregten Zustand entwickelt. Die Summe wird also in der Regel nicht berechnet und im Nenner wird ωj,i zu Im Fall des Grundzustandes schätzen wir die Näherung der Entwicklungszeit also mit folgendem Ausdruck ab

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Die Variable gmin ist bei der Analyse der Entwicklungsdauer meist von entscheidender Bedeutung, da in manchen Fällen der Zähler in (2.47) lediglich polynomiell groß in der Eingabelänge des Problems ist, gmin jedoch exponentiell klein oder kleiner wird und die Entwicklung somit mindestens exponentiell lange dauern muss, um mit der gegebenen Wahrscheinlichkeit den Zustand beizubehalten.

Falls die Eigenwertdifferenz Null wird, so wird der Gesamtzustand zu einer Überlagerung der Eigenzustände zu den betrachteten Eigenwerten. Ein Verschwinden der Differenz ist jedoch nicht immer problematisch, wie wir in Kapitel 4 sehen werden. Für die beiden niedrigsten Eigenwerte ist dies sogar unter bestimmten Voraussetzungen unmöglich, wie Ruskai [Rus02] zeigte.

Unabhängig vom Adiabatensatz kann man auch mit Hilfe der Störungsrechnung und dem Wechselwirkungsbild eine Näherungslösung für die Übergangswahrscheinlichkeit angeben (s. Messiah [Mes79a] §17.1 oder Dawydow [Daw73] §92). Als Kriterium für die Gültigkeit dieser Näherung wird im Allgemeinen folgende Ungleichung herangezogen:

Hierin wird ωi,j =λi−λjℏ alsBohrscheFrequenzbezeichnet,undistproportionalzuderDiffe- renz der i-ten und j-ten Energie im Spektrum der Energieeigenwerte zu den Eigenzuständen |i〉 und |j〉 von H0. Obwohl das Ergebnis ähnlich ist besteht ein entscheidender Unterschied darin, dass hier die Übergangswahrscheinlichkeit zwischen zwei Eigenzuständen zu H0 anstatt H(t) betrachtet wird. Zur Anwendung dieser Abschätzung müssen demnach die Methoden zum Basiswechsel aus Kapitel 2.1 angewandt werden.

2.3.2 Adiabatische Entwicklung vs. Quantenschaltkreise

Üblicherweise werden Quantenrechneralgorithmen durch Quantenschaltkreise (QSK) angegeben, in denen ausschließlich unitäre Operatoren und Messungen erlaubt sind (s. zum Beispiel Nielsen und Chuang [NC00a]). Von diesem Modell unterscheidet sich der Ansatz der adiabatischen Entwicklung so stark, dass van Dam et al. es in [vDMV02] als neues Paradigma für das Design von Quantenrechneralgorithmen vorschlagen. Deshalb folgen nun einige wesentliche Unterschiede.

Anwendung

Bei der adiabatischen Entwicklung konstruiert man aus einer gegebenen Probleminstanz einen zeitabhängigen Hamiltonoperator H(t). Die Lösung der Instanz wird durch den Grundzustand des Energieoperators zum Zeitpunkt H(T ) = H1 kodiert. In der Regel ist dieser jedoch schwer herzustellen, deshalb wird das System in den leicht zu erstellenden Grundzustand eines Anfangsoperators H0 initialisiert. Anschließend interpoliert man die Energieoperatoren analog zu (2.36), so dass sich das System aus Qubits nach dem Adiaba- tensatz auch am Ende der Interpolation noch im Grundzustand befindet. Dabei induziert H(t) auf dieses System aufgrund der Schrödingergleichung den unitären Zeitentwicklungs- operator²

der die zeitliche Änderung der Zustände hin zu einer Lösung der Instanz beschreibt.

Die Lehre der Quantenschaltkreise kommt allerdings von der anderen Seite, indem sie Bausteine benutzt, die eben diese unitären Operationen durchführen. Diese werden dann durch einen passenden, zeitunabhängigen Hamiltonoperator und eine dementsprechende Entwicklungszeit physikalisch realisiert. Der Nachteil hierbei ist, dass das Zeitintervall, in dem der Hamiltonoperator wirkt, sich genau an die Vorgabe T halten muss, um die geforderte unitäre Operation exakt auszuführen. Ein Abweichen von dieser Zeit führt dazu, dass die durchgeführte Operation nicht mehr der Vorgabe entspricht und man somit ein falsches Ergebnis erhält. Die adiabatische Entwicklung leidet hingegen nicht darunter, wenn die Entwicklungszeit verlängert wird. Eine Verkürzung resultiert aber auch hier in einer erhöhten Wahrscheinlichkeit ein falsches Messergebnis zu produzieren.

Messungen

Messungen beschreiben bei den Quantenschaltkreisen ein gewolltes Zerfallen der Überla- gerung verschiedener Eigenzustände. Es kann dabei auch nur ein Teil der Qubits gemessen werden, so dass die anderen in eine Überlagerung aus weniger Eigenzuständen übergehen und die nachfolgenden Bausteine des Schaltkreises vom Messergebnis abhängen. Damit werden z.B. if-then-else Anweisungen durchgeführt und auch fehlerkorrigierende Codes ar- beiten mit diesen partiellen Messungen. Auf der anderen Seite kann auch durch ein gleich- zeitiges Messen aller Qubits ein Eigenzustand des Gesamtsystems gewonnen werden. Die Information, welcher Zustand bei der Messung eingenommen wurde, ist das Messergebnis.

Bei dem Ansatz der adiabatischen Entwicklung werden ausschließlich Messungen des Ge- samtsystems vollzogen. Weiterhin geht man davon aus, dass das Messergebnis der Grundzu- stand des gegebenen Problemoperators ist. Dadurch erhält man mit entsprechender Wahr- scheinlichkeit eine Lösung für das gegebene Problem oder die Antwort, dass es keine solche Lösung gibt.

Simulation

Die adiabatische Entwicklung kann durch Quantenschaltkreise approximiert werden, indem der Gesamtoperator H(t) zu diskreten Zeitpunkten t0, t1, . . . , tm betrachtet wird. Die von H(ti) induzierte Veränderung des Zustandes kann durch eine unitäre Transformation reali- siert werden (s. Ahoronov und Ta-Shma [ATS03]). Da beliebige, unitäre Transformationen auf n Qubits durch [Abbildung in dieser Leseprobe nicht enthalten] Ein-Qubit- und C-Not-Bausteine simuliert werden können [NC00a], ist eine Realisierung der adiabatischen Entwicklung durch Quantenschaltkreise prinzipiell möglich.

Dekohärenz

Als Dekohärenz wird der Informationsverlust eines Systems bezeichnet. Dabei treten die Qubits in Wechselwirkung mit ihrer Umwelt und werden so mit dieser verschränkt. Die Zeit, mit der sich eine Überlagerung aus zwei Zuständen a0 |Ψ0〉 + a1 |Ψ1〉 einer statistischen Mischung aus dem Zustand |Ψ0〉 mit Wahrscheinlichkeit a[20]und|Ψ1〉mita1 annähert, wird Dekohärenzzeit genannt (s. Nielsen und Chuang [NC[00]a] für eine ausführlichere Diskussion). Innerhalb dieser Zeit die Algorithmen zu beenden, ist ein weiteres Problem der Realisierungen von Quantenrechnern.

Van Dam et. al haben jüngst in [vDMV[02]] durch analytische und numerische Berechnun- gen den Einfluss der Dekohärenz auf die adiabatische Entwicklung in Abhängigkeit von der Temperatur untersucht. Ihr Resultat war nicht weiterführend, solange hohe Tempe- raturen betrachtet wurden. Bei tiefen Temperaturen konnte indes ein positiver Effekt der Dekohärenz auf die Erfolgswahrscheinlichkeit der Entwicklung festgestellt werden. Die Au- toren begründen dies damit, dass bei tiefen Temperaturen der Haupteffekt von Dekohärenz, also Kopplung des Systems aus Qubits mit der Umwelt, der ist, dass das System durch Abgabe von Energie in den Grundzustand gedrängt wird. Da der Grundzustand aber eben das erklärte Ziel der adiabatischen Entwicklung ist, kann man von einem positiven Effekt ausgehen. Die Temperatur muss dabei allerdings so gewählt sein, dass die Energie des Systems unterhalb der Energie des ersten, angeregten Zustandes ist.³

Die numerischen Berechnungen der Autoren sind mit Vorsicht zu genießen, da in ihren Beispielen einfaches Kühlen den gewünschten Grundzustand ebenfalls schnell herbeigeführt hätte. Nichtsdestotrotz gehen sie von einem Gewinn aus, wenn das Prinzip der adiabatischen Entwicklung mit einer Kühlung kombiniert wird.

Diese Kombination kann natürlich nicht mehr als adiabatisch angesehen werden, da Kühlen bedeutet, einem System Energie zu entziehen - es findet also ein Energieaustausch statt. Allerdings befinden sich die betrachteten Systeme idealerweise über den gesamten Entwicklungszeitraum im Grundzustand, so dass ein weiterer Energieentzug aus dem System nicht mehr möglich ist. Lediglich einen unerwünschten Übergang in ein höheres Energieniveau kann eine Kühlung wieder rückgängig machen. Daher erhoffen sich van Dam et al. hierdurch eine erhöhte Erfolgswahrscheinlichkeit.

Verwischen der Überlagerung

In einem Quantenschaltkreis existiert meist zu jedem Zeitpunkt eine Überlagerung von verschiedenen Eigenzuständen des Systems aus Qubits. Das System wird durch den wir- kenden Hamiltonoperator H beschrieben, so dass die Vektoren |k〉 eine orthonormale Basis aus Eigenzuständen von H bilden und der Zustand |Ψ〉 des Systems in dieser Basis wie folgt lautet:

Abbildung in dieser Leseprobe nicht enthalten

Diese Überlagerung aus Eigenzuständen zu H unterliegt der zeitabhängigen Schrödingergleichung (2.21).

Betrachten wir nun die formale Lösung der Schrödingergleichung (2.22), so sehen wir, dass die Zustände zeitlich nicht konstant sind. Vielmehr verändert sich die Überlagerung in Quantenschaltkreisen, ohne dass eine Manipulation der Qubits, wie z.B. die Anwendung des nächsten Bausteins im Schaltkreis, Einfluss darauf genommen hätte. Dieses Zerfliessen der Überlagerung (engl. Dephasing) ist ein Problem, da es den einzelnen Zuständen eine relative Phase hinzufügt, die das Messergebnis verfälschen kann. Zum besseren Verständnis mag folgende Gleichung dienen, die durch Einsetzen von |Ψ〉 in die formale Lösung (2.22)

Abbildung in dieser Leseprobe nicht enthalten

Jeder Zustand |k〉 der Überlagerung bekommt also die Phase −λkℏ zugewiesen, wobei λk der Eigenwert zum Eigenzustand |k〉 ist. Im Allgemeinen sind die λk verschieden, so dass sich die Phasen nicht wie eine physikalisch nicht relevante globale Phase ausklammern lassen.

Ein entscheidender Vorteil der Quantenberechnung mittels adiabatischer Entwicklung ist nun, dass sich das System immer im jeweiligen Grundzustand befindet. Zur Erinnerung: Der Grundzustand ist der Zustand, in dem das System die niedrigste Energie besitzt. Da dies zu jedem Zeitpunkt der Fall ist, stellt der Zustand |Ψ〉t bezüglich einer orthonormalen Basis des Energieoperators H(t) keine Überlagerung aus Eigenzuständen, sondern genau den niederenergetischsten Eigenzustand dar. Da also im Idealfall nur ein Eigenzustand eingenommen wird, kann auch keine relative Phase zwischen verschiedenen Eigenzuständen das Messergebnis zerstören.

Desweiteren arbeiten die Quantenrechner, wie auch klassische Computer, sequentiell. Ein Schritt bedeutet hierbei die plötzliche Anwendung einer unitären Transformation auf das System, respektive einer ad hoc auftretenden Veränderung des Hamiltonoperators. Nach einer kurzen Einschwingphase wird dann der erwünschte Folgezustand, meist eine Überlage- rung, eingenommen, woran sich die nächste Transformation anschließt. Kann nun diese Fol- getransformation nicht rechtzeitig durchgeführt werden, entsteht ein Zeitverzug, während dessen der Hamiltonoperator konstant bleibt. Dieser Zeitverzug erzeugt eine störende re- lative Phase.

Bei der adiabatischen Entwicklung hingegen kann ein vergleichbarer Zeitverzug nur von Vorteil sein, da der Zustand niedrigster Energie bei gleichzeitiger Kühlung des Systems bevorzugt wird. Eine Verzögerung würde also eine, evtl. durch Fehler in der Abschirmung entstandene Überlagerung wieder zurück in den gewünschten Grundzustand bringen (s. [vDMV02]).

Generell sollte die adiabatische Entwicklung allerdings mit klassischen, in Anlehnung an Kühlungsprozeduren entstandenen Algorithmen wie simulated annealing nicht verwechselt werden, da der Zustand mit der geringsten Temperatur nicht mit der Zeit sondern von Anfang an eingenommen wird und sich statt des Zustandes die Umgebung verändert. Farhi et al. sprachen diese Thematik bereits in [FGGS] an. Aus physikalischer Sicht existiert ebenfalls ein fundamentaler Unterschied, da ein Kühlprozess in einem Zustand enden kann, der nicht der gewünschte Grundzustand ist, aus dem sich das System allerdings auch nicht ausschließlich durch Abkühlung befreien kann. Siehe [vDMV02] für weitere Details.

Physikalische Realisierungen

Mit Blick auf eine mögliche Implementierung müssen einige Einschränkungen gemacht werden, bei der adiabatischen Entwicklung an die Hamiltonoperatoren, bei Quantenschalt- kreisen an die unitären Operatoren. Zum Beispiel müssen sich die Basis- und Problem- Hamiltonoperatoren als Summe von hermiteschen Operatoren Hc formulieren lassen, wel- che sich immer nur auf eine bestimmte Anzahl von Qubits auswirken (s. [WJB03]) - analog sollten sich die unitären Operatoren aufteilen lassen. Die Probleme für eine Realisierung nehmen mit der Anzahl der durch ein Hc beeinflussten Qubits stark zu. Auch die Anzahl der Summanden Hc, aus denen sich der Operator zusammen setzt, sollte dabei nicht allzu groß sein. Da jeder einzelne Summand bestimmt werden muss, ist eine triviale obere Schranke durch die Lösungszeit des betrachteten Problems auf klassischen Rechnern vorgegeben.

Die Ursache liegt darin, dass derzeitige Realisierungen von Qubits das Problem haben, dass nicht beliebig viele Qubits beliebig miteinander in Wechselwirkung treten können. Im Beispiel des NMR-Quantencomputers konnten diese durch die Atomkerne eines aus bisher maximal sieben unterscheidbaren Atomen bestehenden Moleküls realisiert werden. Durch die Nähe der Kerne innerhalb des Moleküls ist eine gegenseitige Beeinflussung untereinan- der möglich. Auf größere Maßstäbe lässt sich die Idee jedoch nicht ohne Weiteres auswei- ten, da die Konstruktion von Molekülen mit vielen unterscheidbaren Atomen schwierig ist - zumal durch die endliche Anzahl von chemischen Elementen eine obere Schranke für die Anzahl von Qubits mit dieser Technik gegeben ist. Die einzelnen Hc sollten sich demnach nur auf Qubits auswirken, die z.B. durch räumliche Nähe gut miteinander wechselwirken können. In diesem Punkt bietet die adiabatische Quantenberechnung gegenüber den Quantenschaltkreisen keine offensichtliche Verbesserung. Allerdings konnten im Experiment auch schon auf adiabatischer Entwicklung basierende Algorithmen durch NMR-Quantenrechner implementiert werden (s. [SvDH+03]).

Kapitel 3 Anwendungen der adiabatischen Entwicklung in der Informatik

3.1 Grundlagen der theoretischen Informatik

Die Verbesserung der Laufzeiten verschiedener Algorithmen ist eine der Hauptaufgaben der theoretischen Informatik. Diese Laufzeiten hängen von vielen Faktoren ab wie z.B. der zugrundeliegenden Datenstruktur oder aber auch dem Rechnermodell, auf dem sie angewandt werden. Parallelrechner beispielsweise können viele Algorithmen in weniger Re- chenschritten ausführen als sequentiell arbeitende Rechner. Allerdings interessiert in der theoretischen Informatik, speziell der Komplexitätstheorie, meist nur, ob ein Algorithmus polynomiell oder exponentiell viele Rechenschritte, abhängig von der Eingabelänge |w|, benötigt. Man sagt auch, ein Problem habe polynomielle bzw. exponentielle Komplexität, wenn es Algorithmen mit höchstens polynomieller Laufzeit gibt, bzw. alle Algorithmen für dieses Problem mindestens exponentielle Laufzeit besitzen. Hinsichtlich dieser Fokussie- rung zeigte sich bisher für jede neu entwickelte Rechnerart, abgesehen vermutlich von den Quantenrechnern, dass die Probleme stets in die gleiche Komplexitätsklasse einzuordnen sind. Daher beschäftigt sich die theoretische Informatik mit den in den 30er Jahren von Alan Turing entwickelten Turingmaschinen.

Definition 3.1 (Turingmaschine, DTM und NTM) Eine Turingmaschine (TM) ist ein Rechnermodell, welches durch ein Tupel (Q, q0, δ, Γ, Σ, F ) beschrieben werden kann. Zu diesem Rechner gehört ein unendlich langes, beschreibbares Band, auf das Buchstaben aus dem Bandalphabet Γ geschrieben werden können. Die Maschine befindet sich in einem Zu- stand aus der Zustandsmenge Q = {q0, . . . , qN } und ist zu Beginn im Startzustand q0. Für die unten erklärten Entscheidungsprobleme wird zusätzlich die Menge F ⊆ Q der ak- zeptierenden Zustände mit angegeben. Zu Beginn der Berechnung befindet sich auf dem Band die Eingabe w aus Buchstaben des Eingabealphabets Σ und der Lese-/Schreibkopf befindet sich am Anfang von w.

[...]

---

¹ Siehe Nielsen und Chuang [NC00a] für einen Beweis, dass die Eigenwerte reell sind. 9

² Die Unitarität folgt leicht aus U†(T ) · U (T ) = eℏ 0

³ Zur Umrechnung von Energie in Temperatur siehe [Ger99]