Quantum Computational Complexity in the Presence of Closed Timelike Curves

Abstract

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 {\bf 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.

8 pages, 2 figures. Minor changes and typos fixed. Reference added

Cited by in corpus (50)

• The quantum mechanics of time travel through post-selected teleportation
• Can closed timelike curves or nonlinear quantum mechanics improve quantum state discrimination or help solve hard problems?
• Quantum Connectivity of Space-Time and Gravitationally Induced Decorrelation of Entanglement
• Localized closed timelike curves can perfectly distinguish quantum states
• Fast quantum state discrimination with nonlinear PTP channels
• Experimental Simulation of Closed Timelike Curves
• Information Flow of quantum states interacting with closed timelike curves
• Computation in generalised probabilistic theories
• Relativistic quantum information and time machines
• Quantum state cloning using Deutschian closed timelike curves
• Open timelike curves violate Heisenberg's uncertainty principle
• Quantum state cloning in the presence of a closed timelike curve
• Perfect state distinguishability and computational speedups with postselected closed timelike curves
• Quantum causal histories in the light of quantum information
• Treating Time Travel Quantum Mechanically
• Unitary Solution to a Quantum Gravity Information Paradox
• Reversible time travel with freedom of choice
• Quantum Interactions with Closed Timelike Curves and Superluminal Signaling
• Closed timelike curves in measurement-based quantum computation
• Reversible dynamics with closed time-like curves and freedom of choice
• Computational tameness of classical non-causal models
• Replicating the benefits of closed timelike curves without breaking causality
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent
• Purification of Mixed State with Closed Timelike Curve is not Possible
• Quantum fields on closed time-like curves
• Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
• Revisiting consistency conditions for quantum states of systems on closed timelike curves: an epistemic perspective
• A note on superposition of two unknown states using Deutsch CTC model
• Discontinuous quantum evolutions in the presence of closed timelike curves
• Closed timelike curves and the second law of thermodynamics
• Computation with narrow CTCs
• Spinning up a Time Machine
• Nonlinear and non-CP gates for Bloch vector amplification
• Computability Theory of Closed Timelike Curves
• Reply to comment on "Information Flow of quantum states interacting with closed timelike curves"
• Bell Correlations and the Common Future
• Analogue time machine in a photonic system
• Causality Violation and Nonlinear Quantum Mechanics
• Computational Complexity and the Nature of Quantum Mechanics
• Lorentz Quantum Computer
• Revisiting Integer Factorization using Closed Timelike Curves
• Quantum no-go theorems in causality respecting systems in presence of closed timelike curves: Tweaking the Deutsch condition
• Computational Complexity and the Nature of Quantum Mechanics (Extended version)
• Mixedness and Entanglement in the presence of Localized Closed Timelike Curves
• Whether a quantum computation employs nonlocal resources is operationally undecidable
• The Computational Power of Minkowski Spacetime
• The universe as a nonlinear quantum simulation: Large $n$ limit of the central spin model
• Quantum state tomography on closed timelike curves using weak measurements
• Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
• Dirac four-potential tunings-based quantum transistor utilizing the Lorentz force