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 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.
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.
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.
In der vorliegenden Arbeit behandeln wir verschiedene Themen aus dem Gebiet der Quanteninformationstheorie. Die unterschiedlichen Ergebnisse sollen entweder die Anwendung theoretischer Konzepte auf reale Experimente erleichtern oder bei der weiterfuhrenden Arbeit an zentralen Fragen helfen. Im Detail werden folgende Punkte untersucht: Wir wenden uns als Erstes der Fragestellung zu, unter welchen Vorraussetzungen eine gegebene Menge an Erwartungswerten mit den ersten beiden Momenten der Spinoperatoren eines Zustandes von Gesamtspin j kompatible ist. Hierbei liegt das Hauptaugenmerk auf einer operationellen Beschreibung, so dass man direkt mit den Momenten arbeiten kann, anstatt den kompletten Dichteoperator zu verwenden. Wir zeigen, dass diese Charakterisierung physikalischer Momente zu dem Problem der Bose-symmetrischen Erweiterungen fur speziell bestimmte Zweiqubit Zustande aquivalent ist. Mittels dieser Umformulierung bestimmen wir operationelle Teil- und Ubermengen der exakten Menge, um somit auf einfache Art und Weise Momente identifizieren zu konnen, die sicher physikalisch sind, als auch andere, die eindeutig inkompatibel mit den Vorhersagen der Quantenmechanik sind. Diese approximative Losung gewinnt mit steigender Gesamtspinzahl j an Genauigkeit, und konvergiert im Limes gegen die exakte Losung. Im nachsten Abschnitt beschaftigen wir uns mit dem Konzept der Verschrankungszeugen; der gebrauchlichsten Methode zur Verschrankungsdetektion. Wir untersuchen, wie man die Qualitat eines linearen Verschrankungszeugen durch quadratische, nichtlineare Terme verbessen kann, so dass man mehr verschrankte Zustande auf einmal detektiert. Das betrachtete Verbessungsschema hat den Vorteil dass man es iterative benutzen kann. Dies liefert eine Abfolge von Verschrankungszeugen mit Nichtlinearitaten immer hoherer Ordnung, deren Starke in jedem Schritt zunimmt. Die entwickelte Iterationsmethode kann fur verschiedene Aufgaben verwendet werden und wir betrachten zwei ausgezeichnete Extremfalle: Entweder optimieren wir fur einen vorgegeben Zielzustand oder fur alle moglichen Zustande gleichmassig. Im restlichen Teil der Arbeit untersuchen wir verschiedene Moglichkeiten, wie man bereits vorhandene Ideen besser an reale Experimente anpasst. Hier sei angemerkt dass viele Anwendungen der Quanteninformationstheorie nur fur stark idealisierte Systeme vorgeschlagen und diskutiert wurden und somit nicht direkt fur das Experiment anwendbar sind. Dieser Punkt ist fur das Feld der Quantenschlusselverteilung von besonderer Bedeutung, da man die vorbehaltslose Sicherheit eines realen, durch ein Experiment generierten Schlussels zeigen mochte und nicht nur fur die einer idealisierten Version davon. Mit diesem Ziel im Hinterkopf untersuchen wir zuerst die theoretische Idee des Squash Modells. Dieses bietet einen eleganten Ausrechentrick', der es erlaubt, die Sicherheitsanalyse eines idealisierten Quantenschlusselverteilungsprotokolls direkt fur das reale Experiment zu verwenden. Wir entwickeln einen Formalismus zur Prufung dieses Squash Modells fur einen gegebenen Messaufbau und betrachten relevante Messschemen mit und ohne dieser Eigenschaft. Im Gegensatz zu diesem theoretischen Modell behandlen wir auch eine experimentelle Moglichkeit, die es uns erlaubt, die Sicherheitsanalyse des idealisierten Systems direkt fur das reale Experiment zu verwenden. Dazu benutzen wir die Idee, dass man durch die Kombination eines variablen Strahlteilers mit einem einfachen Click/No-Click' Detektor, die Statistik von photonauflosenden Detektoren erhalten kann. Durch diese Hardwareanderung ist es moglich, die sicherheitsrelevanten Parameter direkt abzuschatzen. Diese Methode bietet somit auch einen Weg, die Sicherheit eines realen Quantenschlusselverteilungsexperiments zu beweisen, fur das die theoretische Squash Modell Idee nicht funktioniert. Als Ergebnis erhalt man unter anderem einen neuen Distanzrekord fur ein reales Quantenschlusselverteilungsexperiment mit derzeitiger Technologie. Als letzten Punkt betrachten wir das Problem der experimentellen Verschrankungsverifizierung. Bei dieser Verifizierung hat man oftmals ein Praktikabilitatsproblem, weil man---ob verschiedener Grunde---meistens nur ein sehr vereinfachtes Modell fur die verwendenten Messapparate benutzt. Wir zeigen, dass man in diesem Fall der Fehlinterpretation der beobachteten Messausgange durchaus Fehler machen kann, allerdings untersuchen wir in erster Linie Bedingungen, unter denen ein falschlicher Verschrankungsnachweis ausgeschlossen werden kann. Zu diesem Zweck verwenden wir ein dem Squash Modell ahnliches, aber weniger restriktives Konzept. Eine interessante Anwendung liefern die ublicherweise mittels Tomographie durchgefuhrten Verschrankungstests, die man typischerweise fur parametrische Fluoreszenz Quellen oder fur photonische Mehrparteienexperimente verwendet. Wir zeigen, dass diese sehr einfach fehlerfrei gemacht werden konnen.