One way to study the physical plausibility of closed timelike curves (CTCs) is to examine their computational power. This has been done for Deutschian CTCs (D-CTCs) and postselection CTCs (P-CTCs), with the result that they allow for the efficient solution of problems in PSPACE and PP, respectively. Since these are extremely powerful complexity classes, which are not expected to be solvable in reality, this can be taken as evidence that these models for CTCs are pathological. This problem is closely related to the nonlinearity of this models, which also allows, for example, cloning quantum states, in the case of D-CTCs, or distinguishing nonorthogonal quantum states, in the case of P-CTCs. In contrast, the process matrix formalism allows one to model indefinite causal structures in a linear way, getting rid of these effects and raising the possibility that its computational power is rather tame. In this paper, we show that process matrices correspond to a linear particular case of P-CTCs, and therefore that its computational power is upperbounded by that of PP. We show, furthermore, a family of processes that can violate causal inequalities but nevertheless can be simulated by a causally ordered quantum circuit with only a constant overhead, showing that indefinite causality is not necessarily hard to simulate.
Born in the intersection between quantum mechanics and general relativity, indefinite causal structure is the idea that in the continuum of time, some sets of events do not have an inherent causal order between them. Process matrices, introduced by Oreshkov, Costa and Brukner (Nature Communications, 2012), define quantum information processing with indefinite causal structure -- a generalization of the operations allowed in standard quantum information processing, and to date, are the most studied such generalization.
Araujo et al. (Physical Review A, 2017) defined the computational complexity of process matrices, and showed that polynomial-time process matrix computation is equivalent to standard polynomial-time quantum computation with access to a weakening of post-selection Closed Timelike Curves (CTCs), that are restricted to be
linear. Araujo et al. accordingly defined the complexity class for efficient process matrix computation as
BQPℓCTC (which trivially contains
BQP), and posed the open question of whether
BQPℓCTC contains computational tasks that are outside
BQP.
In this work we solve this open question under a widely believed hardness assumption, by showing that
NP⊆BQPℓCTC. Our solution is captured by an even more restricted subset of process matrices that are purifiable (Araujo et al., Quantum, 2017), which (1) is conjectured more likely to be physical than arbitrary process matrices, and (2) is equivalent to polynomial-time quantum computation with access to
unitary (which are in particular linear) post-selection CTCs. Conceptually, our work shows that the previously held belief, that non-linearity is what enables CTCs to solve
NP, is false, and raises the importance of understanding whether purifiable process matrices are physical or not.
Can quantum computation become more powerful when operations do not need to follow a definite causal order? We study this question in the process matrix formalism of Oreshkov et al. (Nature Communications, 2012), which allows quantum operations to be connected without a fixed global order. In the computational model, a quantum circuit succinctly describes a process matrix, and the algorithm is given access to its generated channel, with computational cost measured by the size of the generating circuit.
We give polynomial-time algorithms in two settings. First, general process matrix computation suffices to solve every problem in
NP. The valid processes used by our algorithm satisfy the purification postulate of Araújo et al. (Quantum, 2017), and their generated channels are unitary, although their generating circuits are not. Second, requiring the process matrices themselves to be pure, we give a polynomial-time algorithm for unique-sink orientation, a general problem capturing several longstanding computational problems in optimization. Our unitary generators are constructed explicitly and efficiently. Assuming that unique-sink orientation has no quantum polynomial-time algorithm, our result shows that indefinite causal order can provide computational power beyond
BQP within the process matrix formalism, even while preserving unitarity.
While closed timelike curves (CTCs) are not known to exist, studying their consequences has led to non-trivial insights into general relativity, quantum information and other areas. In this paper, we show that, if CTCs existed, quantum computers would be no more powerful than classical computers: both would have the (extremely large) power of the complexity class polynomial space ( ), consisting of all problems solvable by a conventional computer using a polynomial amount of memory. This solves an open problem proposed by one of us in 2005, and gives an essentially complete understanding of computational complexity in the presence of CTCs. Following the work of Deutsch, we treat a CTC as simply a region of spacetime where a ‘causal consistency’ condition is imposed, meaning that nature has to produce a (probabilistic or quantum) fixed point of some evolution operator. Our conclusion is then a consequence of the following theorem: given any quantum circuit (not necessarily unitary), a fixed point of the circuit can be (implicitly) computed in . This theorem might have independent applications in quantum information.
Closed Timelike Curves (CTCs) are intriguing relativistic objects that allow for time travel to the past and can be used as computational resources. In Deutschian Closed Timelike Curves (D-CTCs), due to the monogamy of entanglement, non-local correlations between entangled states are destroyed. In contrast, for Postselected Closed Timelike Curves (P-CTCs), a second variant of CTCs, the non-local correlations are preserved. P-CTCs can be harnessed for the signaling of non-orthogonal states to the past without a disruption of causality. In this paper, we take up signaling to the past and show a method of sending four non-orthogonal states to the past using P-CTCs. After constructing our signaling protocol, we study the causality violations that our protocol results in and put forward two consistency relations to prevent them.
Many results have been recently obtained regarding the power of hypothetical closed timelike curves (CTCs) in quantum computation. Here we show that the one-way model of measurement-based quantum computation encompasses in a natural way the CTC model proposed by Bennett, Schumacher, and Svetlichny. We identify a class of CTCs in this model that can be simulated deterministically and point to a fundamental limitation of Deutsch's CTC model which leads to predictions conflicting with those of the one-way model.
The fact that closed timelike curves (CTCs) are permitted by general relativity raises the question as to how quantum systems behave when time travel to the past occurs. Research into answering this question by utilizing the quantum circuit formalism has given rise to two theories: Deutschian-CTCs (D-CTCs) and ``postselected'' CTCs (P-CTCs). In this paper the quantum circuit approach is thoroughly reviewed, and the strengths and shortcomings of D-CTCs and P-CTCs are presented in view of their nonlinearity and time-travel paradoxes. In particular, the ``equivalent circuit model''---which aims to make equivalent predictions to D-CTCs, while avoiding some of the difficulties of the original theory---is shown to contain errors. The discussion of D-CTCs and P-CTCs is used to motivate an analysis of the features one might require of a theory of quantum time travel, following which two overlapping classes of alternate theories are identified. One such theory, the theory of ``transition probability'' CTCs (T-CTCs), is fully developed. The theory of T-CTCs is shown not to have certain undesirable features---such as time-travel paradoxes, the ability to distinguish nonorthogonal states with certainty, and the ability to clone or delete arbitrary pure states---that are present with D-CTCs and P-CTCs. The problems with nonlinear extensions to quantum mechanics are discussed in relation to the interpretation of these theories, and the physical motivations of all three theories are discussed and compared.