Physics – Quantum Physics
Scientific paper
2003-09-25
Phys.Rev.A70:032309,2004
Physics
Quantum Physics
8 pages, 2 figures. Minor changes and typos fixed. Reference added
Scientific paper
10.1103/PhysRevA.70.032309
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.
No associations
LandOfFree
Quantum Computational Complexity in the Presence of Closed Timelike Curves does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Quantum Computational Complexity in the Presence of Closed Timelike Curves, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Computational Complexity in the Presence of Closed Timelike Curves will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-651277