Quantum computation with indefinite causal structures

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. (author)