How does the BosonSampling paper avoid easy classes of complex matrices?

Question

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

BosonSampling
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?

Answer 1

Thanks for your question! There are two answers, depending on whether you're interested in the hardness results for exact or approximate BosonSampling.

In the exact case, we prove that given any n-by-n complex matrix A, you can construct an optical experiment that produces a particular output with probability proportional to |Per(A)|². This, in turn, implies that no classical polynomial-time algorithm can sample from exactly the same distribution as the optical experiment (given a description of the experiment as input), unless P^#P = BPP^NP. In fact we can strengthen that, to give a single distribution D_n (depending only on the input length n) that can be sampled using an optical experiment of poly(n) size, but that can't be sampled classically in poly(n) time unless P^#P = BPP^NP.

In the approximate case, the situation is more complicated. Our main result says that, if there's a classical polynomial-time algorithm that simulates the optical experiment even approximately (in the sense of sampling from a probability distribution over outputs that's 1/poly(n)-close in variation distance), then in BPP^NP, you can approximate |Per(A)|², with high probability over an n-by-n matrix A of i.i.d. Gaussians with mean 0 and variance 1.

We conjecture that the above problem is #P-hard (at the very least, not in BPP^NP), and pages 57-82 of our paper are all about the evidence for that conjecture.

Of course, maybe our conjecture is false, and one can actually give a poly-time algorithm to approximate the permanents of i.i.d. Gaussian matrices. That would be a phenomenal result! However, the whole point of 85% of the work we did was to base everything on a hardness conjecture that was as clean, simple, and "quantum-free" as possible. In other words, instead of the assumption

"approximating the permanents of some weird, special matrices that happen to arise in our experiment is #P-hard,"

we show that it suffices to make the assumption

"approximating the permanents of i.i.d. Gaussian matrices is #P-hard."