Revisiting Integer Factorization using Closed Timelike Curves

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.

6 pages

References in corpus (10)

• 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?
• Experimental Simulation of Closed Timelike Curves
• Closed Timelike Curves Make Quantum and Classical Computing Equivalent
• Verifiable nonlinear quantum evolution implies failure of density matrices to represent proper mixtures
• 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