Quantum Computation and Information Seminar 

13/01/2006, 15:00 — 16:00 — Room P4.35, Mathematics Building
Scott Aaronson, U Waterloo

Quantum Versus Classical Proofs And Advice

Quantum computing skeptics have claimed that any theory involving exponentially-long vectors is inherently unreasonable. But if someone hands you a quantum state, is that really like being handed an exponential amount of classical information? I will describe recent results suggesting that the answer, at least for complexity-theoretic purposes, is "no". These results include simulations of quantum advice using classical advice, and a conditional "dequantization" of John Watrous' quantum proof protocol for the Group Non-Membership problem. Based partly on joint work with Greg Kuperberg.