Quantum computation with indefinite causal structures

In dieser Dissertation wird untersucht, welche Kausalbeziehungen mit den Gesetzen der Quanteninformationsverarbeitung kompatibel sind. Sie ist durch die Erwartung motiviert, dass jede Theorie, die Gravitation und Quantenmechanik vereint, unbestimmte kausale Strukturen beinhaltet, die durch die quantenmechanische Unschärfe der Metrik hervorgerufen wird. Das gegenwärtige Verständnis solcher unbestimmter kausaler Strukturen ist jedoch noch sehr unvollständig. Als Werkzeug zu ihrer näheren Untersuchung verwenden wir die sogenannte "process matrix", eine Matrix die die allgemeinste Möglichkeit der Signalübertragung zwischen Parteien enthält, die nicht zu logischen Paradoxien (wie etwa dem Großvaterparadoxon) führt. Diese Allgemeinheit erlaubt es, sowohl bestimmte als auch unbestimmte kausale Strukturen zu beschreiben, ohne a priori ihre physikalische Plausibilität zu beurteilen. Der erste Aspekt der Doktorarbeit ist die Entwicklung eines theoretischen Instrumentariums zur Untersuchung von kausalen Beziehungen im "process matrix"-Formalismus. Mithilfe von Semidefiniter Programmierung können wir Zeugenoperatoren definieren -- analog zu Zeugenoperatoren für Verschränkung -- die zwischen "process matrices" bestimmter und unbestimmter kausaler Ordnung unterscheiden können. Wir verwenden auch Semidefiniter Programmierung und polyhedrale Programmierung um systematisch kausale Ungleichungen zu untersuchen, die, wie Bell-Ungleichungen für Verschränkung, die unbestimmte kausale Struktur nur aufgrund der statistischen Korrelationen nachzuweisen erlaubt. Diese Herangehensweise erlaubt es uns, die einfachsten kausalen Ungleichungen herzuleiten und Algorithmen zu entwickeln, um "process matrices" und quantenmechanische Operationen zu finden, welche diese verletzen. Der zweite Aspekt der Dissertation betrifft die Unterscheidung derjenigen "process matrices", die physikalisch relevant sind von denen, die vielleicht nur mathematische Artefakte sind. Dafür haben wir zwei Ansätze entwickelt. Der erste Ansatz identifiziert kausale Strukturen, die mit der Reversibilität von physikalischen Gesetzen vereinbar sind. Unter der Annahme, dass alle physikalischen Gesetze prinzipiell reversibel sind, können grundlegend irreversible kausale Strukturen als unphysikalisch betrachtet werden. Der zweite Ansatz betrachtet kausale Strukturen aus der Sicht der Theorie der Quantencomputer: Wenn jene zu mächtig wären, hätte man Grund, ihre physikalische Plausibilität in Zweifel zu ziehen. Obwohl einige "process matrices", für ein spezifisches Problem, eine asymptotische Reduktion der Anzahl der Queries erlauben, sind sie doch weniger mächtig als andere Modelle von Quantencomputern, die auf geschlossenen zeitartigen Weltlinien beruhen und deshalb physikalisch plausibler.This thesis explores which causal relations are allowed by the laws of quantum information processing. It is motivated by the conundrum that although we expect any theory that unifies gravity and quantum mechanics to feature indefinite causal structures due to quantum uncertainty in the metric, we currently have poor understanding of the notion of an indefinite causal structure. The tool we use to approach this problem is the process matrix, which encodes the most general way that some parties that respect quantum mechanics can signal to each other without creating logical contradictions such as the grandfather paradox. This generality allows process matrices to encode both definite and indefinite causal orders, without passing judgement on their physical plausibility. One aspect of the thesis is to develop technical tools to study types of causal relations within the process matrix formalism. Using semidefinite programming we define witnesses -- analogous to entanglement witnesses -- that can distinguish between process matrices that encode definite and indefinite causal orders. We also use semidefinite programming and polyhedral computation to systematize the study of causal inequalities which, analogously to Bell inequalities, allow one to certify in a device-independent way that a given causal structure is indefinite. These tools allows us to find the simplest possible causal inequalities and to develop algorithms to find process matrices and quantum operations that violate them. Another aspect of the thesis is to investigate which process matrices encode physical causal structures and which might turn out to be mathematical artefacts. We do this in two ways: the first is to identify which causal structures are compatible with the reversibility of physical laws and which are not. Taking the consensus view that all physical laws are ultimately reversible allows us to identify as unphysical the causal structures that are fundamentally irreversible. The other way we investigate their physicality is from the point of view of quantum computation: if they turn out to be too powerful, it is a reason to be suspicious of their plausibility. We find that even though process matrices do provide an asymptotic advantage in query complexity for a specific problem, we can prove that they are weaker than other models of quantum computation based on closed timelike curves, and thus more physically plausible