Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
arXiv:quant-ph/0408119
Abstract
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.
14 pages. Together with Part I (quant-ph/0408035), subsumes the earlier paper quant-ph/0205059. Can be read independently of Part I
References in corpus (7)
- Strengths and Weaknesses of Quantum Computing
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum Computational Complexity in the Presence of Closed Timelike Curves
- Subquantum Information and Computation
- Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
- Is Quantum Mechanics An Island In Theoryspace?