We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On the other hand, Say and Yakaryilmaz showed that computation with just 1 classical CTC bit gives the power of "postselection", thereby upgrading classical randomized computation (BPP) to the complexity class BPP_path and standard quantum computation (BQP) to the complexity class PP. It is natural to ask whether increasing the number of CTC bits from 1 to 2 (or 3, 4, etc.) leads to increased computational power. We show that the answer is no: randomized computation with logarithmically many CTC bits (i.e., polynomially many CTC states) is equivalent to BPP_path. (Similarly, quantum computation augmented with logarithmically many classical CTC bits is equivalent to PP.) Spoilsports with no interest in time travel may view our results as concerning the robustness of the class BPP_path and the computational complexity of sampling from an implicitly defined Markov chain.
We present results in structural complexity theory concerned with the following interrelated topics: computation with postselection/restarting, closed timelike curves (CTCs), and approximate counting. The first result is a new characterization of the lesser known complexity class BPP path in terms of more familiar concepts. Precisely, BPP path is the class of problems that can be efficiently solved with a nonadaptive oracle for the approximate counting problem. Similarly, PP equals the class of problems that can be solved efficiently with nonadaptive queries for the related approximate difference problem. Another result is concerned with the computational power conferred by CTCs, or equivalently, the computational complexity of finding stationary distributions for quantum channels. Using the preceding characterization of PP, we show that any poly( n )-time quantum computation using a CTC of O (log n ) qubits may as well just use a CTC of 1 classical bit. This result essentially amounts to showing that one can find a stationary distribution for a poly( n )-dimensional quantum channel in PP.
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.
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.
We study the question of what is computable by Turing machines equipped with time travel into the past; i.e., with Deutschian closed timelike curves (CTCs) having no bound on their width or length. An alternative viewpoint is that we study the complexity of finding approximate fixed points of computable Markov chains and quantum channels of countably infinite dimension. Our main result is that the complexity of these problems is precisely
Δ2, the class of languages Turing-reducible to the Halting problem. Establishing this as an upper bound for qubit-carrying CTCs requires recently developed results in the theory of quantum Markov maps.
There is now a significant body of results on quantum interactions with closed timelike curves (CTCs) in the quantum information literature, for both the Deutsch model of CTC interactions (D-CTCs) and the projective model (P-CTCs). As a consequence, there is a prima facie argument exploiting entanglement that CTC interactions would enable superluminal and, indeed, effectively instantaneous signaling. In cases of spacelike separation between the sender of a signal and the receiver, whether a receiver measures the local part of an entangled state or a disentangled state to access the signal can depend on the reference frame. We propose a consistency condition that gives priority to either an entangled perspective or a disentangled perspective in spacelike-separated scenarios. For D-CTC interactions, the consistency condition gives priority to frames of reference in which the state is disentangled, while for P-CTC interactions the condition selects the entangled state. Using the consistency condition, we show that there is a procedure that allows Alice to signal to Bob in the past via relayed superluminal communications between spacelike-separated Alice and Clio, and spacelike-separated Clio and Bob. This opens the door to time travel paradoxes in the classical domain. Ralph [T. C. Ralph, arXiv:1107.4675 [quant-ph].] first pointed this out for P-CTCs, but we show that Ralph's procedure for a ``radio to the past'' is flawed. Since both D-CTCs and P-CTCs allow classical information to be sent around a spacetime loop, it follows from a result by Aaronson and Watrous [S. Aaronson and J. Watrous, Proc. R. Soc. A 465, 631 (2009)] for CTC-enhanced classical computation that a quantum computer with access to P-CTCs would have the power of PSPACE, equivalent to a D-CTC-enhanced quantum computer.
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.