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.
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.
The possibility of performing quantum cloning in the presence of closed time like curves is considered. We analyze a model of the quantum cloning process involving a source qubit, a target qubit, and a quantum copy machine which is itself a composite quantum system. A subsystem of the copy machine is allowed to traverse a closed time like curve. Under these circumstances the evolution of the chronology respecting parts of the system is nonlinear. This suggests (Deutsch, 1991) that quantum cloning might be possible. We prove that, if only one subsystem of the copy machine is allowed to traverse a closed time like curve and the copy machine’s Hilbert space is of finite dimension, universal quantum cloning is impossible.
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.
We study the power of closed timelike curves (CTCs) and other nonlinear extensions of quantum mechanics for distinguishing nonorthogonal states and speeding up hard computations. If a CTC-assisted computer is presented with a labeled mixture of states to be distinguished--the most natural formulation--we show that the CTC is of no use. The apparent contradiction with recent claims that CTC-assisted computers can perfectly distinguish nonorthogonal states is resolved by noting that CTC-assisted evolution is nonlinear, so the output of such a computer on a mixture of inputs is not a convex combination of its output on the mixture's pure components. Similarly, it is not clear that CTC assistance or nonlinear evolution help solve hard problems if computation is defined as we recommend, as correctly evaluating a function on a labeled mixture of orthogonal inputs.
The causal self-consistency condition for closed timelike curves can give rise to nonlinear interactions on chronology-respecting qubits. We demonstrate that particular unitary interactions between closed timelike curve qubits and chronology-respecting qubits allow perfect distinguishability of nonorthogonal states, and provide a constructive proof for an arbitrary number of nonorthogonal states. This has a number of highly significant consequences. For example, an adversary with access to closed timelike curves can break the B92, BB84, and SARG04 quantum key distribution protocols, or any prepare-and-measure quantum key distribution scheme. Our result also implies that a party with access to closed timelike curves can violate the Holevo bound by accessing more than log(N) bits of information from an N-dimensional quantum state. In principle, he can transmit an arbitrarily large amount of classical information with a quantum system of fixed size. We discuss the implications of this for quantum cloning.