Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0908.3023 · Physical Review Letters

Can Closed Timelike Curves or Nonlinear Quantum Mechanics Improve Quantum State Discrimination or Help Solve Hard Problems?

Charles H. Bennett, Debbie Leung, Graeme Smith, John A. Smolin

Published Oct 21, 2009• 85 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevlett.103.170502

Related papers

Would the Existence of CTCs Allow for Nonlocal Signaling?

Lucas Dunlap

A recent paper from Brun et al. has argued that access to a closed timelike curve (CTC) would allow for the possibility of perfectly distinguishing nonorthogonal quantum states. This result can be used to develop a protocol for instantaneous nonlocal signaling. Several commenters have argued that nonlocal signaling must fail in this and in similar cases, often citing consistency with relativity as the justification. I argue that this objection fails to rule out nonlocal signaling in the presence of a CTC. I argue that the reason these authors are motivated to exclude the prediction of nonlocal signaling is because the No Signaling principle is considered to a fundamental part of the formulation of the quantum information approach. I draw out the relationship between nonlocal signaling, quantum information, and relativity, and argue that the principle theory formulation of quantum mechanics, which is at the foundation of the quantum information approach, is in tension with foundational assumptions of Deutsch's D-CTC model, on which this protocol is based.

arXiv:1601.04668•Jan 18, 2016•0 citations

Quantum computational complexity in the presence of closed timelike curves

Dave Bacon

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 $\mathit{NP}$-complete problems with only a polynomial number of quantum gates.

arXiv:quant-ph/0309189•Physical Review A•Sep 13, 2004•73 citations

Timelike curves can increase entanglement with LOCC

Subhayan Roy Moulick, Prasanta Kumar Panigrahi

We study the nature of entanglement in presence of Deutschian closed timelike curves (D-CTCs) and open timelike curves (OTCs) and find that existence of such physical systems in nature would allow us to increase entanglement using local operations and classical communication (LOCC). This is otherwise in direct contradiction with the fundamental definition of entanglement. We study this problem from the perspective of Bell state discrimination, and show how D-CTCs and OTCs can unambiguously distinguish between four Bell states with LOCC, that is otherwise known to be impossible.

arXiv:1511.00538•Scientific Reports•Nov 29, 2016•7 citations

Closed timelike curves make quantum and classical computing equivalent

Scott Aaronson, John Watrous

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.

arXiv:0808.2669•Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences•Nov 11, 2008•99 citations

Treating time travel quantum mechanically

John-Mark A. Allen

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.

arXiv:1401.4933•Physical Review A•Oct 9, 2014•25 citations

Entanglement in a World with Closed Timelike Curves

Subhayan Roy Moulick, Prasanta Kumar Panigrahi

We study the nature of entanglement in presence of closed timelike curves (CTCs) and we observe that qubits traveling along a CTC allow unambiguous discrimination of Bell states with Local Operations and Classical Communications (LOCC), and can be further generalized to allow unambiguous discrimination of any finite set of bipartite entangled states using just LOCC, that is otherwise known to be impossible. This enables one to create entanglement using just LOCC. Furthermore, we point out how the existence of CTCs would imply entanglement can be polygamous, and thus contradicting the prior known notions of monogamy of entanglement.

•Nov 2, 2015•1 citation
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.
A recent paper from Brun et al. has argued that access to a closed timelike curve (CTC) would allow for the possibility of perfectly distinguishing nonorthogonal quantum states. This result can be used to develop a protocol for instantaneous nonlocal signaling. Several commenters have argued that nonlocal signaling must fail in this and in similar cases, often citing consistency with relativity as the justification. I argue that this objection fails to rule out nonlocal signaling in the presence of a CTC. I argue that the reason these authors are motivated to exclude the prediction of nonlocal signaling is because the No Signaling principle is considered to a fundamental part of the formulation of the quantum information approach. I draw out the relationship between nonlocal signaling, quantum information, and relativity, and argue that the principle theory formulation of quantum mechanics, which is at the foundation of the quantum information approach, is in tension with foundational assumptions of Deutsch's D-CTC model, on which this protocol is based.
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\mathit{NP}NP-complete problems with only a polynomial number of quantum gates.
We study the nature of entanglement in presence of Deutschian closed timelike curves (D-CTCs) and open timelike curves (OTCs) and find that existence of such physical systems in nature would allow us to increase entanglement using local operations and classical communication (LOCC). This is otherwise in direct contradiction with the fundamental definition of entanglement. We study this problem from the perspective of Bell state discrimination, and show how D-CTCs and OTCs can unambiguously distinguish between four Bell states with LOCC, that is otherwise known to be impossible.
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.
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.
We study the nature of entanglement in presence of closed timelike curves (CTCs) and we observe that qubits traveling along a CTC allow unambiguous discrimination of Bell states with Local Operations and Classical Communications (LOCC), and can be further generalized to allow unambiguous discrimination of any finite set of bipartite entangled states using just LOCC, that is otherwise known to be impossible. This enables one to create entanglement using just LOCC. Furthermore, we point out how the existence of CTCs would imply entanglement can be polygamous, and thus contradicting the prior known notions of monogamy of entanglement.