Revisiting Integer Factorization using Closed Timelike Curves
arXiv:1708.03508 · doi:10.1007/s11128-018-2130-4
Abstract
Closed Timelike Curves are relativistically valid objects allowing time travel to the past. Treating them as computational objects opens the door to a wide range of results which cannot be achieved using non relativistic quantum mechanics. Recently, research in classical and quantum computation has focused on effectively harnessing the power of these curves. In particular, Brun (Found. Phys. Lett., 2003) has shown that CTCs can be utilized to efficiently solve problems like factoring and QSAT (Quantified Satisfiability Problem). In this paper, we find a flaw in Brun's algorithm and propose a modified algorithm to circumvent the flaw.
arXiv comment6 pages
References in corpus (26)
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Closed timelike curves via post-selection: theory and experimental demonstration
- NP-complete Problems and Physical Reality
- 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 Computational Complexity in the Presence of Closed Timelike Curves
- Unitarity and Causality in Generalized Quantum Mechanics for Non-Chronal Spacetimes
- Localized closed timelike curves can perfectly distinguish quantum states
- Computers with closed timelike curves can solve hard problems
- Experimental Simulation of Closed Timelike Curves
- Information Flow of quantum states interacting with closed timelike curves
- Quantum state cloning in the presence of a closed timelike curve
- Perfect state distinguishability and computational speedups with postselected closed timelike curves
- Treating Time Travel Quantum Mechanically
- Nonlinearity in Quantum Theory and Closed Timelike Curves
- Replicating the benefits of closed timelike curves without breaking causality
- Non-causal computation
- Closed Timelike Curves Make Quantum and Classical Computing Equivalent
- Purification of Mixed State with Closed Timelike Curve is not Possible
- Verifiable nonlinear quantum evolution implies failure of density matrices to represent proper mixtures
- Simulations of closed timelike curves
- 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
- Computability Theory of Closed Timelike Curves
- Eigenvalue Formulation of Quantum Mechanics Near Closed Timelike Curves