[QIP-Sem] QIP seminar, Mon 4/26, 4:30, 36-428, Aaronson,Scott

[Peter Shor]

MIT Quantum Information Processing seminar
Monday 4/26 at 4:30 in 36-428
-------------------------------------------------

 Aaronson,Scott (M.I.T)

 The Computational Complexity of Linear Optics

Abstract:

We propose a linear-optics experiment that might be feasible with current technology, and argue that, if the experiment succeeded, it would provide evidence that at least some nontrivial quantum computation is possible in nature.  The experiment involves generating reliable single-photon states, sending the photons through a random linear-optical network, and then reliably measuring the photon number in each mode.  The resources that we consider are not known or believed to be universal for quantum computation; nevertheless, we show that they would allow the solution of certain sampling and relational problems that appear to be intractable for classical computers.  Our first result says that, if there exists a polynomial-time classical algorithm that samples from the same probability distribution as our optical experiment, then P^P=BPP^NP, and hence the polynomial hierarchy collapses to the third level.  Unfortunately, the above result assumes an extremely reliable experiment
 .  While that could in principle be arranged using quantum error correction, the question arises of whether a noisy experiment would already have interesting complexity consequences.  To address this question, we formulate a so-called "Permanent-of-Gaussians Conjecture" (PGC), which says that it is #P-hard to approximate the permanent of a matrix A of independent N(0,1) Gaussian entries, with high probability over A; as well as a "Permanent Concentration Conjecture" (PCC), which says that |Per(A)|>=sqrt(n!)/poly(n) with high probability over A.  We then show that, assuming both the PGC and the PCC, polynomial-time classical simulation even of noisy linear-optics experiments would imply a collapse of the polynomial hierarchy. Joint work with Alex Arkhipov.

-------------------------------------------------
http://qis.mit.edu
http://mailman.mit.edu/mailman/listinfo/qip-sem