In The computational complexity of linear optics (ECCC TR10-170), Scott Aaronson and Alex Arkhipov argue that if quantum computers can be efficiently simulated by classical computers then the polynomial hierarchy collapses to the third level. The motivating problem is sampling from a distribution defined by a linear-optical network; this distribution can be expressed as the permanent of a particular matrix. In the classical case all entries of the matrix are non-negative, and so a probabilistic polynomial-time algorithm exists, as shown by Mark Jerrum, Alistair Sinclair, and Eric Vigoda (JACM 2004, doi: 10.1145/1008731.1008738). In the quantum case the entries are complex numbers. Note that in the general case (when the entries are not required to be non-negative) the permanent cannot be approximated even within a constant factor, by Valiant's classic 1979 result.
The paper defines a distribution $D_A$ defined by a matrix $A$, and a sampling problem
Input: matrix $A$
Sample: from distribution $D_A$
Using a hardness result seems to be weak evidence for a separation between the classical and quantum worlds, since it is possible that the class of matrices in the specific quantum setup will all be of special form. They might have complex entries, but may still possess a lot of structure. There could therefore exist an efficient sampling procedure for such matrices, even though the general problem is #P-hard.
How does the use of BosonSampling in the paper avoid easy classes?
The paper uses a lot of background I don't have in quantum complexity. Given all the quantum people on this site, I'd really appreciate a pointer in the right direction. How would the arguments hold up if one were to discover that the class of complex-valued matrices seen in a specific experimental setup actually corresponded to a class of distributions that was easy to sample from? Or is there something inherent in the quantum system that guarantees this cannot happen?