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 non-intuitive theoretical solutions of general relativity field equations. The main paradox associated with the physical existence of CTCs, the so-called grandfather paradox, can be satisfactorily solved by a quantum model named Deutsch-CTC. An outstanding theoretical result that has been demonstrated in the Deutsch-CTC model is the computational equivalence of a classical and a quantum computer in the presence of a CTC. In this article, in order to explore the possible implications for the foundations of quantum mechanics of that equivalence, a fundamental particle is modelled as a classical-like system supplemented with an information space in which a randomizer and a classical Turing machine are stored. The particle could then generate quantum behavior in real time in case it was controlled by a classical algorithm coding the rules of quantum mechanics and, in addition, a logical circuit simulating a CTC was present on its information space. The conditions that, through the action of evolution under natural selection, might produce a population of such particles with both elements on their information spaces from initial sheer random behavior are analyzed.
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.
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.
Abstract This study examines closed timelike curves (CTCs) in quantum mechanics, focusing on the Deutsch model, one of the most widely studied frameworks for describing quantum systems in the presence of time loops. In this model, a quantum state ∣ψ⟩|\psi\rangle∣ψ⟩ interacts unitarily with its past version, effectively forming a two-qubit system where the chronologically consistent qubit interacts with a qubit ρCTC\rho_{\text{CTC}}ρCTC trapped in a closed timelike curve. The state ρCTC\rho_{\text{CTC}}ρCTC is determined by the Deutsch consistency condition, ensuring self-consistent evolution along the CTC. This approach allows for rigorous modeling of quantum systems under non-classical temporal structures, providing insights into temporal correlations, causality violations, and the potential computational advantages offered by CTC-assisted quantum operations. While alternative CTC models based on postselection have been proposed, the Deutsch model remains a foundational reference for studying quantum evolution in non-linear temporal frameworks. Its analysis informs research in quantum information, retrocausality, and the theoretical limits of computation in exotic spacetime geometries.
Quantum computation with quantum data that can traverse closed timelike curves represents a new physical model of computation. We argue that a model of quantum computation in the presence of closed timelike curves can be formulated which represents a valid quantification of resources given the ability to construct compact regions of closed timelike curves. The notion of self-consistent evolution for quantum computers whose components follow closed timelike curves, as pointed out by Deutsch [Phys. Rev. D 44, 3197 (1991)], implies that the evolution of the chronology respecting components which interact with the closed timelike curve components is nonlinear. We demonstrate that this nonlinearity can be used to efficiently solve computational problems which are generally thought to be intractable. In particular we demonstrate that a quantum computer which has access to closed timelike curve qubits can solve
NP-complete problems with only a polynomial number of quantum gates.
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.