Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories

2004/08/19 by Scott Aaronson, Aaronson, Scott
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0408119

14 pages. Together with Part I (quant-ph/0408035), subsumes the earlier paper quant-ph/0205059. Can be read independently of Part I

arxiv created 2004/08/19 · arxiv updated 2009/12/01

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.

Related

• Improved separation between quantum and classical computers for sampling and functional tasks
• The space "just above" BQP
• The power of quantum circuits in sampling
• Strengths and Weaknesses of Quantum Computing
• Quantum Computing, Postselection, and Probabilistic Polynomial-Time