CS conjecture that Quantum Computer cannot solve NP-complete problems, but Boson Samplers do a #P-hard problem. How is it?

Question

There is something very strange and absurd for me about the power of a quantum computer. Let me briefly states the following facts:

Fact 1: theoretical computer scientists believe (very likely to happen) that quantum computer cannot solve NP-complete problems.

Fact 2: In BQP, there are problems that is harder than NP, such as Boson sampling distribution which is known to be $\#P$$-hard$.

Fact 3: If Boson sampling distribution (and other problems such as Quantum Sampling) belong to $PH$, then the polynomial time hierarchy collapsed. So, it is unlikely that these problems belongs to $PH$.

Now, by these facts it is said that BQP is greater class than $PH$. I.e. since all NP problems lies in PH, then BQP contains all NP problems including the NP-complete problems. But, at the same time, theoretical computer scientists (such as Scott Aaronson) conjectured that quantum computer cannot solve NP-complete problems efficiently, i.e. they are trying to say the following: BQP should be smaller than class PH.

Can someone explain to me whether I'm wrong about something or not.

Answer 1

Boson sampling samples from a distribution, but does not compute the full distribution. While computing the distribution is linked to computing permanents, which is #P-hard, we would expect that sampling from such a distribution is considerably less powerful. Even if such sampling a number $N$ of times would allow us to estimate the permanent of a specific matrix - which it doesn't here - such as estimate would only be accurate to a relative error of $1/\mathrm{poly(N)}$, which is much weaker than #P (in fact, such approximations of #P-problems lie inside BPP^NP).

Answer 2

This is a well-framed question that highlights subtleties about what is known and unknown on the strengths and limitations of quantum computers.

Initially, it is completely consistent with what we know, and indeed what we expect, for both NP and BQP to be incomparable. That is, there are problems such as the TSP that are known to be in NP that are not expected to be solvable efficiently on a quantum computer, and perhaps more interestingly problems that are efficiently solvable with a BQP machine that are not even expected to be efficiently verifiable with a classical computer. Accordingly I would lightly revise Fact 1 to state:

In BQP, theoretical computer scientists believe (very likely to happen) that quantum computers cannot efficiently solve NP-complete problems.

However, Fact 2 is not entirely correct as stated. Although it is true that BQP likely includes problems such as forrelation that are outside of the polynomial hierarchy and in a sense "harder" than NP, and although in order to verify the output of a Boson Sampler one has to solve the (likely) very hard problem of calculating permanents of various matrices with entries in $\mathbb{C}$, it is not the case that the specific sampling task performed by a Boson Sampler is #P-hard.

That is, the Boson Sampler does not calculate the permanents of an a-priori given matrix. Rather, given $n$ photons on $m\gg n$ modes, the Boson Sampler outputs the $n$ photons in the various output modes in a way corresponding to a $n\times n$ submatrix. One does not have control over the submatrix of input and output modes sampled by the Boson Sampler, and all one can say is that the submatrix has a large permanent.

I like to think of BosonSampling as a bit like the Texas sharpshooter who shoots a gun onto the side of a barn, and then later on paints a bullseye on the barn. Here one shoots bosons (photons) through a bunch of beam-splitters and phase-shifters, and then based on the output one calculates the permanent of the corresponding submatrix.