All Abstracts | Poster Abstracts | Talk Abstracts | Tutorial Abstracts

New Evidence that Quantum Mechanics is Hard to Simulate on Classical Computers

Scott Aaronson, Massachusetts Institute of Technology

(Session 3 : Friday from 1:15-2:00)

Abstract. I'll discuss new types of evidence that quantum mechanics is hard to simulate classically -- evidence that is more complexity-theoretic in character than (say) Shor's factoring algorithm, and that also corresponds to experiments that seem easier than building a universal quantum computer. Specifically: (1) I'll show that linear-optics (that is, systems of non-interacting bosons) produce probability distributions that cannot be efficiently sampled by a classical computer, unless P^#P = BPP^NP and hence the polynomial hierarchy collapses. I'll also discuss an extension of this result to samplers that only approximate the boson distribution. (Based on recent joint work with Alex Arkhipov) (2) Time permitting, I'll also discuss new oracle evidence that BQP has capabilities outside the entire polynomial hierarchy. (arXiv:0910.4698)