Ziel dieser Arbeit ist es, den Begriff der Quanten-Kolmogorov-Komplexität formal zu definieren und seine wichtigsten Eigenschaften rigoros zu beweisen. Die klassische Kolmogorov-Komplexität ist ein bekanntes und nützliches Maß für die Zufälligkeit endlicher Wörter. In den letzten Jahren wurden unterschiedliche Quantenverallgemeinerungen der Kolmogorov-Komplexität vorgeschlagen. Die natürlichste Art der Verallgemeinerung stammt von Berthiaume u.a., die die Komplexität eines Quantenwortes definieren als die Länge der kürzesten Quanteneingabe für einen universellen Quantencomputer, die als Ausgabe das entsprechende Wort produziert. Abgesehen von kleinen Änderungen soll dieser Komplexitätsbegriff in der hier vorliegenden Arbeit untersucht werden. Zunächst untersuchen wir verschiedene Aspekte des zugrunde liegenden Modells der Quantenturingmaschine (QTM), und zwar mit größerer formaler Genauigkeit als in bisherigen Arbeiten. Anschließend wenden wir diese Resultate auf die Quanten-Kolmogorov-Komplexität an. Unser erstes Ergebnis, basierend auf der Arbeit von Bernstein und Vazirani, ist ein Beweis für die Existenz einer universellen QTM, die jede andere QTM für eine beliebige Anzahl von Zeitschritten simulieren kann, und dann selbst mit Wahrscheinlichkeit eins hält. Weiterhin zeigen wir, dass jede Eingabe, die eine QTM beinahe halten lässt, modifiziert werden kann, um eine Eingabe zu erhalten, die die universelle QTM vollständig halten lässt, wobei sich die Eingabelänge höchstens um eine konstante Anzahl von Qubits vergrößert. Daraus folgt, dass die Quanten-Kolmogorov-Komplexität die Invarianzeigenschaft besitzt, d.h. sie ist bis auf eine additive Konstante unabhängig von der Wahl der universellen QTM. Außerdem stimmt die Quantenkomplexität klassischer Wörter mit deren klassischer Komplexität überein, wieder bis auf eine additive Konstante. Die entsprechenden Beweise beruhen auf verschiedenen analytischen Abschätzungen. Weiterhin beweisen wir mehrere Sätze, die zeigen, dass nur wenige Quantenwörter kleine Quantenkomplexität besitzen können. Schließlich zeigen wir, dass bei ergodischen Quantendatenquellen Komplexitätsrate und Entropierate mit Wahrscheinlichkeit eins übereinstimmen. Den Abschluss der Arbeit bildet ein Ausblick auf eine mögliche Anwendung der Quanten-Kolmogorov-Komplexität in der statistischen Mechanik.
Ziel dieser Arbeit ist es, den Begriff der Quanten-Kolmogorov-Komplexität formal zu definieren und seine wichtigsten Eigenschaften rigoros zu beweisen. Die klassische Kolmogorov-Komplexität ist ein bekanntes und nützliches Maß für die Zufälligkeit endlicher Wörter. In den letzten Jahren wurden unterschiedliche Quantenverallgemeinerungen der Kolmogorov-Komplexität vorgeschlagen. Die natürlichste Art der Verallgemeinerung stammt von Berthiaume u.a., die die Komplexität eines Quantenwortes definieren als die Länge der kürzesten Quanteneingabe für einen universellen Quantencomputer, die als Ausgabe das entsprechende Wort produziert. Abgesehen von kleinen Änderungen soll dieser Komplexitätsbegriff in der hier vorliegenden Arbeit untersucht werden. Zunächst untersuchen wir verschiedene Aspekte des zugrunde liegenden Modells der Quantenturingmaschine (QTM), und zwar mit größerer formaler Genauigkeit als in bisherigen Arbeiten. Anschließend wenden wir diese Resultate auf die Quanten-Kolmogorov-Komplexität an. Unser erstes Ergebnis, basierend auf der Arbeit von Bernstein und Vazirani, ist ein Beweis für die Existenz einer universellen QTM, die jede andere QTM für eine beliebige Anzahl von Zeitschritten simulieren kann, und dann selbst mit Wahrscheinlichkeit eins hält. Weiterhin zeigen wir, dass jede Eingabe, die eine QTM beinahe halten lässt, modifiziert werden kann, um eine Eingabe zu erhalten, die die universelle QTM vollständig halten lässt, wobei sich die Eingabelänge höchstens um eine konstante Anzahl von Qubits vergrößert. Daraus folgt, dass die Quanten-Kolmogorov-Komplexität die Invarianzeigenschaft besitzt, d.h. sie ist bis auf eine additive Konstante unabhängig von der Wahl der universellen QTM. Außerdem stimmt die Quantenkomplexität klassischer Wörter mit deren klassischer Komplexität überein, wieder bis auf eine additive Konstante. Die entsprechenden Beweise beruhen auf verschiedenen analytischen Abschätzungen. Weiterhin beweisen wir mehrere Sätze, die zeigen, dass nur wenige Quantenwörter kleine Quantenkomplexität besitzen können. Schließlich zeigen wir, dass bei ergodischen Quantendatenquellen Komplexitätsrate und Entropierate mit Wahrscheinlichkeit eins übereinstimmen. Den Abschluss der Arbeit bildet ein Ausblick auf eine mögliche Anwendung der Quanten-Kolmogorov-Komplexität in der statistischen Mechanik.
Gegenstand der vorliegenden Arbeit ist die Untersuchung von quantenmechanischen und klassischen Markov-Prozessen und deren Anwendung im Bereich der stark korrelierten Vielteilchensysteme. Unter einem Markov-Prozess versteht man eine spezielle Art eines stochastischen Prozesses, dessen weitere dynamische Entwicklung unabhängig ist von der Vorgeschichte seiner Entwicklung und nur von der derzeitigen Konfiguration abhängt. Die Anwendung von Markov-Prozessen im Bereich der statistischen Mechanik von klassischen Vielteilchensystemen hat eine lange Geschichte. Markov-Prozesse dienen nicht nur der Beschreibung der Dynamik von stochastischen Systemen, sondern liefern vielmehr auch eine sehr praktische Methode, mit dereren Hilfe grundlegende Eigenschaften komplexer Vielteilchenprobleme in Form eines probabilistischen Algorithmus berechnet werden können. Ziel dieser Arbeit ist es das Verhalten von quantenmechanischen Markov Prozessen, dies sind Markov-Prozesse, welchen ein quantenmechanischer Konfigurationsraum zu Grunde liegt, zu untersuchen und mit deren Hilfe komplexe Vielteilchensysteme besser zu verstehen. Darüber hinaus formulieren wir einen Quantenalgorithmus, mit dessen Hilfe es möglich ist, die thermischen- und Grundzustandseigenschaften von quantenmechanischen Vielteilchensystemen zu berechnen. Nachdem wir eine kurze Einführung in das Feld der quantenmechanischen Markov-Prozesse gegeben haben, untersuchen wir deren Konvergenzeigenschaften. Wir finden Schranken für die Konvergenzraten der quantenmechanischen Prozesse, basierend auf einer Verallgemeinerung von geometrischen Schranken, welche für klassische Prozesse gefunden wurden. Wir verallgemeinern ein Abstandsmaß, die Chi-Quadrat Divergenz für nicht kommutative Wahrscheinlichkeitsräume, welches unseren Untersuchungen zu Grunde liegt. Diese Divergenz ermöglicht auch eine Verallgemeinerung der detaillierten Balance für quantenmechanische Prozesse. Danach konstruieren wir den Quantenalgorithmus, der als natürliche Verallgemeinerung des Metropolisalgorithmus für quantenmechanische Hamiltonoperatoren verstanden werden kann. Wir beabsichtigen damit zu zeigen, dass ein Quantencomputer in der Lage ist, als universeller Quantensimulator zu fungieren, welcher nicht nur die Dynamik eines Quantensystems beschreiben kann, sondern auch den Zugang zu statischen Berechnungen ermöglicht. Danach untersuchen wir die Korrelationseigenschaften von klassischen Nichtgleichgewichtszuständen mit Methoden der Quanteninformationstheorie. Wir konstruieren eine Klasse von Matrix-Produkt-Zuständen, deren Korrelationen anhand von klassischen Markov-Prozessen verstanden werden können. Schließlich untersuchen wir die Transporteigenschaften eines stationären Nichtgleichgewichtszustandes. Die dynamische Gleichung ist so konstruiert, dass der Transport je nach Parameterwahl entweder hauptsächlich stochastisch oder hauptsächlich kohärent stattfindet. Wir können somit die unterschiedlichen Formen des Transports innerhalb eines Modells miteinander vergleichen.
Diese Diplomarbeit befasst sich hauptsaechlich mit dem Nachweis und der Klassifizierung genuiner Vielteilchenverschraenkung in Quantensystemen, die aus beliebig vielen Qubits bestehen. Vielteilchen- verschraenkung ist die Grundlage der Vielkoerperphysik und es gibt viele potenzielle Anwendungen fuer sie in der Quanteninformation, etwa Quantenkryptographie. Wir beginnen diese Diplomarbeit mit einer kurzen Einfuehrung in quantenmechanische, endlich dimensionale Vielteilchenzustaende. Wir konzentrieren uns hauptsaechlich auf Teilchen mit zwei Freiheitsgraden, sogenannten Qubits, und deren Darstellungen. Anschließend legen wir unseren Fokus auf verschraenkte Zustaende und darauf wie man Verschraenkung detektieren und quantifizieren kann. Wir praesentieren die vier maximal verschraenkten Zustaende, die ein System, bestehend aus zwei Qubits, einnehmen kann und zeigen schematisch den Prozess des Distillierens von Verschraenkung. Dann kommen wir zum Haupthhema dieser Arbeit, Vielteilchenverschraenkung. Wir definieren k-separabilitaet und genuine Vielteilchen- verschraenkung, stellen einige genuin vielteilchenverschraenkte Zustaende vor und beschaeftigen uns mit der Detektion und der Klassifizierung solcher Zustaende. Im Hauptteil dieser Diplomarbeit prae- sentieren wir vier, von uns entwickelte Kriterien, die in wissenschaftlichen Journalen veroeffentlicht wurden. Mit all diesen Kriterien kann man genuin vielteilchenverschraenkte Zustaende detektieren und mit drei davon, ist es auch moeglich solche Zustaende zu Klassifizieren. Wir zeigen, dass die Zweckmaeßigkeit dieser Kriterien fuer Experimente, wegen ihrer hohen Widerstandsfaehigkeit gegen Stoerungen (noise resistance), der niedrigen Anzahl der Matrixelemente, die man von einem Zustand kennen muss um eines der Kriterien auf ihn anzuwenden und der Moeglichkeit jedes der vier Kriterien in Termen lokaler Erwartungswerte von Paulioperatoren anzuschreiben, vergleichsweise hoch ist. Im letzten Teil dieser Arbeit untersuchen wir, wie Verschraenkung entlang einer eindimensionalen, un- endlich langen, translationsinvarianten Kette aus Qubits verteilt sein kann und stellen eine Methode vor um Zustaende beliebig vieler benachbarter Qubits, einer solchen Kette, zu konstruieren. Die max- imale Menge an Verschraenkung, die in einem Zustand von zwei benachbarten Qubits stecken kann, ist hier das interessanteste Resultat. Wenn die naechste Nachbar Verschraenkung maximal ist, gibt es keine andere Art der Verschraenkung in dieser Kette. Wir zeigen, dass wenn das nicht der Fall ist, auch Verschraenkung zwischen einem Qubit und seinem ueberuebernaechstem Nachbarn moeglich ist. Außerdem zeigen wir, durch das Anwenden der von uns entwickelten Kriterien auf einen Zustand von vier benachbarten Qubits, dass auch genuine Vierteilchenverschraenkung in der Qubitkette moeglich ist.
Diese Dissertation beschäftigt sich mit der Frage, wie viel Rechenkraft Quantencomputer bieten können. Diese Frage geht in ihrer allgemeinsten Form weit über die aktuellen Möglichkeiten und Methoden der Komplexitätstheorie hinaus. Dennoch liefert die Komplexitätstheorie Beispiele von Problemen, die sogar für Quantencomputer als nicht effizient lösbar gelten. Andererseits können Quantencomputer vermutlich nicht effizient von klassischen Computern simuliert werden. Wir wollen mit dieser Arbeit zum Verständnis des dazwischen liegenden Bereichs von Problemen, die effizient auf Quantencomputern, aber nicht effizient auf klassischen Computern berechnet werden können, beitragen. Um besseren Einblick in die Fragestellung zu erlagen, entwickeln wir in dieser Dissertation klassische und quantenmechanische Algorithmen zur Lösung von Problemen, die unter einschränkenden Annahmen a priori als nicht effizient lösbar geltende Probleme dennoch effizient lösen. Wir erforschen in diesem Sinne also die Grenzen des auf Quantencomputern und klassischen Computern Machbaren, in dem wir Annahmen identifizieren, die dazu geeignet sind grundsätzlich als schwer geltende Probleme in den Bereich des Machbaren zu bringen. Im Speziellen entwickeln wir einen Quantenalgorithmus, der sogenannte Projective Entangled-Pair States (PEPS) effizient herstellen kann, sobald Injektivität und Wohlkonditierung des PEPS gegeben ist. In einem zweiten Schritt erweitern wir diesen Algorithmus auf sogenannte G-injektive PEPS, einer wesentlich allgemeineren Klasse von Quantenzuständen, die auch die exotische Eigenschaft der topologischen Ordnung besitzen können. Weiters entwickeln wir einen Quantenalgorithmus, der das im Allgemeinen für Quantencomputer als schwer geltende Problem den Grundzustand von lokalen Hamiltonoperatoren zu erzeugen löst, sofern diese die Voraussetzungen des (nicht-konstruktiven) Quanten-Lovász-Local-Lemma erfüllen und die Operatoren kommutieren. Unser Quantenalgorithmus kann in diesem Fall auch als unabhängiger, konstruktiver Beweis des Quanten-Lovász-Local-Lemmas betrachtet werden. Um die Grenze zu klassischen Computern zu erforschen, entwickeln wir einen klassischen Algorithmus, der das sehr allgemeine Problem Quantenschaltkreise zu simulieren unter gewissen Annahmen effizient lösen kann. Wäre es in voller Allgemeinheit lösbar, würden Quantencomputer keinen Vorteil bieten. Unser Algorithmus kann Quantenschaltkreise simulieren, die in ihrer Struktur jener des Quantenalgorithmus von Shor zur Faktorisierung ganzer Zahlen, der als exponentiell schneller als der schnellste bekannte klassische Faktorisierungsalgorithmus gilt, sehr ähnlich sind. Weiters treffen wir die Annahme, dass die erzeugte Wahrscheinlichkeitsverteilung annähernd dünn-besetzt ist. Unser Ergebnis impliziert daher, dass die von Algorithmen dieser Struktur erzeugte Wahrscheinlichkeitsverteilung notwendigerweise dicht-besetzt sein muss, um einen exponentiellen Geschwindigkeitsvorteil erzielen zu können.
Das Ziel dieser Doktorarbeit ist die Untersuchung der unbestimmten Kausalstrukturen, die mit der Quantenmechanik kompatibel sind, mithilfe eines auf Quanteninformation basierendem Ansatzes. Es ist zu erwarten, dass in Bereichen wo Quantenmechanik und die allgemeine Relativitatstheorie relevant sind, die kausale Beziehung zwischen Ereignisse unbestimmt wird. Ein Beispiel fur solch unbestimmte Kausalstrukturen ist der sogenannte gravitative Quantenswitch, wo die kausale Abfolge zweier Ereignisse durch die raumliche superposition eines massiven Gegenstandes kontrolliert wird. Der Prozessmatrizenformalismus ist ein allgemeines Modell zur Beschreibung von Situationen, in denen die kausale Ordnung zwischen Quantenereignisse unbestimmt ist. Dieser Formalismus enthalt Prozesse, die bisher keine physikalische Interpretation haben und die, wenn sie existierten, sogenannte kausale Ungleichungen verletzen konnten.
Ein Aspekt dieser Arbeit ist die Untersuchung der informationstheorischen Eigenschaften von Prozessen mit unbestimmter Kausalitat, vor allem der Quantenkontrolle von kausaler Ordnung — wie es beim Quantenswitch der Fall ist. Wir zeigen wie, im Kontex von verteilter Berechnung, der Quantenswitch Vorteile im Vergleich zu einfachgerichteter Quantenkommunikation mit bestimmter kausaler Ordnung erbringen kann.
Genauer gesagt, wir definieren eine dreigeteilte Kommunikationsaufgabe fur welche die Quantenswitch exponentielle Reduktion an benotigten Qubits aufweist. Auserdem untersuchen wir Behauptungen, dass der Quantenswitch verbesserte Kommunikation durch verrauschten Kanalen ermoglicht. Wir stellen fest, dass diese Verbesserung jedoch nicht auf die unbestimmte kausale Ordnung zuruckzufuhren ist, sondern auf die Fahigkeit die Anwendung der Kanale koharent zu kontrollieren.
Der zweite Teil dieser Arbeit befasst sich mit der Frage nach der Realisierbarkeit von Prozessen mit unbestimmter Kausalitat. Angetrieben durch den Mangel an physikalischer Interpretation fur viele interessante Prozesse, entwickeln wir das Konzept des kausalen Bezugsystems. Dadurch konnen wir eine bestimmte Klasse von Prozessen — reine Prozesse — vom Standpunk eines der beteiligten Beobachter beschreiben. Dabei stellt sich heraus, dass fur einen in Ereignis A lokalisierten Beobachter, das Ereignis eines anderen Beobachters B generell zeitlich delokalisiert erscheint. Wir untersuchen die kausalen Bezugsysteme interessanter Prozessen mit unbestimmten Kausalstruktur, und machen dadurch einige Fortschritte auf dem Wege zum Verstandnis vom Unterschied zwischen solchen Prozessen und dem besser verstandenen Quantenswitch. Ein letzter Aspekt, den wir in dieser Arbeit betrachten, ist wie man aus bekannten Prozessen neuen machen kann — Kompositionsregeln. Wir beweisen, dass es keine parallele Kompositionsregel fur allgemeine Prozessmatrizen gibt, die einige vernunftig anmutende Axiome erfullt.
Nach einer physikalischen Betrachtung der Quantenmechanik werden zunächst die benötigten mathematischen Grundlagen eingeführt bzw. wiederholt: Vektorräume, darauf aufbauend Hilberträume und die Tensorrechnung, gefolgt von den Grundlagen der Wahrscheinlichkeitsrechnung. Auf diesen Grundlagen wird ein Quantencomputer insoweit modelliert, wie es für die Formulierung von Algorithmen notwendig ist, d.h. als mathematisches Modell der Quantenbits, der Zeitentwicklung durch Gates und der abschließenden Messungen. Auf diesem Modell werden dann die klassischen Quantenalgorithmen jeweils vollständig eingeführt und erklärt. Schließlich wird die denkbare Umsetzung von Quantenalgorithmen auf heute existierende klassische Computer diskutiert.
Diese Dissertation untersucht Quantenbeweissysteme unter den komplementären Gesichtspunkten der perfekten Vollständigkeit und der Unverschränktheit. Wir konzentrieren uns auf zwei Varianten von QMA (Quantum Merlin–Arthur), dem Quantenanalogon zu NP. Informell ist QMA die Klasse der Entscheidungsprobleme, deren JA-Instanzen effizient anhand eines Quantenbeweiszustands verifiziert werden können. Die erste Variante, QMA₁, hat perfekte Vollständigkeit: Für jede JA-Instanz existiert ein Quantenbeweis, den der Verifizierer mit Wahrscheinlichkeit genau 1 annimmt. Das kanonische vollständige Problem für QMA₁ ist das Quantenerfüllbarkeitsproblem (QSAT). Wir untersuchen die Komplexitätsgrenze von (d_A×d_B)-QSAT, wobei jede Beschränkung auf ein d_A-dimensionales und ein d_B-dimensionales Qudit wirkt. Dazu zeigen wir die QMA₁-Vollständigkeit von (2×5)-QSAT und (3×4)-QSAT sowie von eindimensionalem (3×d)-QSAT für ein konstantes d. Perfekte Vollständigkeit führt dazu, dass die Definition von QMA₁ von der Gattermenge abhängt. Wir erzielen Fortschritte auf dem Weg zu einer universellen Gattermenge, indem wir für jeden zyklotomischen Körper ℚ(ζ_(2ʳ)) eine exakte Gattermenge angeben, mit der sich innerhalb von QMA₁ jede endliche Gattermenge über diesem Körper simulieren lässt. Mithilfe unserer Beweistechniken erhalten wir das erste 2-lokale QMA₁-vollständige Hamiltonian-Problem und das erste QMA₁(2)-vollständige Hamiltonian-Problem. Zudem zeigen wir die QMA₁-Vollständigkeit von Gapped Weighted Clique Homology und die PSPACE-Vollständigkeit von Clique Homology ohne Promise-Gap. Als Nächstes beweisen wir, dass QSAT-Instanzen mit einem gewichteten System distinkter Repräsentanten (WSDR) eine Produktzustandslösung haben, wobei ein WSDR ein verallgemeinertes Matching zwischen den lokalen Beschränkungen und den Qudits ist. Aufbauend auf diesem Beweis definieren wir zwei neue Unterklassen von TFNP, deren Totalität durch algebraische Prinzipien garantiert ist: MHS (multihomogene Gleichungssysteme) und SFTA (Fundamentalsatz der Algebra für dünnbesetzte Polynome). Die Suchvariante von QSAT mit einem SDR ist MHS-vollständig. Die zweite QMA-Variante, die wir untersuchen, ist QMA(2) und schränkt den Beweis auf einen Produktzustand der Form |ψ₁⟩ ⊗ |ψ₂⟩ ein. Ein Problem in QMA(2), von dem nicht bekannt ist, ob es auch in QMA liegt, ist das Problem der Konsistenz lokaler Dichtematrizen mit einem reinen Gesamtzustand (PureCLDM). Wir führen eine neue Komplexitätsklasse ein, die wir PureSuperQMA nennen, und zeigen, dass PureCLDM und das Problem der reinen N-Darstellbarkeit für diese Klasse vollständig sind. Als Nächstes beweisen wir, dass PureSuperQMA ⊆ PSPACE, indem wir die PureSuperQMA-Verifizierer in strukturierte Systeme quadratischer Gleichungen übersetzen und einen Algorithmus zur Lösung solcher Gleichungssysteme parallelisieren. Zum Vergleich: Die beste klassische obere Schranke für QMA(2) bleibt NEXP. Zum Schluss betrachten wir die Quantenpolynomialzeithierarchie (QPH) und ihre Variante mit reinen Zuständen (pureQPH), in der konkurrierende Beweiser unverschränkte Nachrichten an einen Verifizierer schicken. Wir zeigen, dass die zweite Ebene von pureQPH bereits QMA(2) enthält, beweisen Fehlerreduktion für pureQPH und zeigen, dass pureQPH = QPH gilt. Außerdem führen wir das quantifizierte Hamiltonian-Problem ein und geben natürliche vollständige Probleme für jede Ebene von pureQPH. Das zentrale Thema dieser Dissertation ist, dass unscheinbare Einschränkungen von Quantenbeweissystemen erhebliche komplexitätstheoretische Konsequenzen haben können, die quantenmechanischer Natur sind.