Computers with closed timelike curves can solve hard problems
arXiv:gr-qc/0209061 · doi:10.1023/A:1025967225931
Abstract
A computer which has access to a closed timelike curve, and can thereby send the results of calculations into its own past, can exploit this to solve difficult computational problems efficiently. I give a specific demonstration of this for the problem of factoring large numbers, and argue that a similar approach can solve NP-complete and PSPACE-complete problems. I discuss the potential impact of quantum effects on this result.
9 pages LaTeX; submitted to Foundations of Physics Letters
References in corpus (1)
Cited by in corpus (29)
- Closed timelike curves via post-selection: theory and experimental demonstration
- 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?
- Localized closed timelike curves can perfectly distinguish quantum states
- Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
- Design and Construction of a Brain-Like Computer: A New Class of Frequency-Fractal Computing Using Wireless Communication in a Supramolecular Organic, Inorganic System
- Quantum state cloning using Deutschian closed timelike curves
- Perfect state distinguishability and computational speedups with postselected closed timelike curves
- Grover search and the no-signaling principle
- Quantum Interactions with Closed Timelike Curves and Superluminal Signaling
- 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
- Nonclassical advantage in metrology established via quantum simulations of hypothetical closed timelike curves
- Purification of Mixed State with Closed Timelike Curve is not Possible
- Faster than light motion does not imply time travel
- Discontinuous quantum evolutions in the presence of closed timelike curves
- A note on superposition of two unknown states using Deutsch CTC model
- Closed timelike curves and the second law of thermodynamics
- Closed Timelike Curves in Relativistic Computation
- Quantum no-go theorems in causality respecting systems in presence of closed timelike curves: Tweaking the Deutsch condition
- Revisiting Integer Factorization using Closed Timelike Curves
- The Computational Power of Minkowski Spacetime
- Whether a quantum computation employs nonlocal resources is operationally undecidable
- Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order
- Modular quantum computing and quantum-like devices
- Quantum state tomography on closed timelike curves using weak measurements
- Dirac four-potential tunings-based quantum transistor utilizing the Lorentz force
- Computation and Spacetime Structure