pdf files of
Programme Booklet >>
and
Abstracts of all Talks >>

You will receive a hard copy of these files at the registration desk.

Sponsors

Pauli Center for Theoretical Studies

The Swiss National Science Foundation

ETH Zurich (Computer Science and Physics Department)

Quantum Science and Technology

CQT Singapore

QAP European Project

Sandia National Laboratories

Institute for Quantum Computing

id Quantique

New evidence that quantum mechanics is hard to simulate on classical computers

Scott Aaronson, MIT

joint work with Alex Arkhipov

I'll discuss new types of evidence that quantum mechanics is intractable 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 much easier than building a universal quantum computer. Specifically:

(1) I'll discuss recent oracle evidence that BQP has capabilities outside the polynomial hierarchy---namely, that there exists a black-box relational problem in BQP but not in BPP^PH, and that a decision problem separating BQP from PH (that is, an oracle relative to which BQP is not in PH) would follow from the "Generalized Linial-Nisan Conjecture."  The original Linial-Nisan Conjecture (about pseudorandomness against constant-depth circuits) was recently proved by Mark Braverman, after being open for 20 years. (Preprint at arXiv:0910.4698)

(2) I'll show that, using only nonadaptive linear optics, one can generate probability distributions that can't 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 photon distribution in variation distance. The extension relies on an unproved conjecture in classical complexity theory: namely, that approximating the permanent of a matrix of i.i.d. Gaussians is a random-self-reducible #P-complete problem.