Physics – Quantum Physics
Scientific paper
2004-08-19
Physics
Quantum Physics
14 pages. Together with Part I (quant-ph/0408035), subsumes the earlier paper quant-ph/0205059. Can be read independently of P
Scientific paper
This paper shows that, if we could examine the entire history of a hidden variable, then we could efficiently solve problems that are believed to be intractable even for quantum computers. In particular, under any hidden-variable theory satisfying a reasonable axiom called "indifference to the identity," we could solve the Graph Isomorphism and Approximate Shortest Vector problems in polynomial time, as well as an oracle problem that is known to require quantum exponential time. We could also search an N-item database using O(N^{1/3}) queries, as opposed to O(N^{1/2}) queries with Grover's search algorithm. On the other hand, the N^{1/3} bound is optimal, meaning that we could probably not solve NP-complete problems in polynomial time. We thus obtain the first good example of a model of computation that appears slightly more powerful than the quantum computing model.
No associations
LandOfFree
Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories 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 Computing and Hidden Variables II: The Complexity of Sampling Histories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-84334