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

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.

• I think #2 as stated is not quite correct. Exact boson sampling classically may entail computing permanents, which is #P-complete, but that’s not what boson samplers actually do; one backcalculates the matrix from which the boson sampler samples. The boson sampler samples according to the probabilities given by the permanent. Jan 21 at 4:14
• Can't Grover's algorithm solve the travelling salesman problem or other such NP-complete problems ? Jan 21 at 14:34
• Yes but not in polynomial time. Jan 21 at 16:34

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).

• 1. Some years ago, there was a result that shows an oracle separation between BQP and PH, they show that there exists a problem in BQP but not in PH relative to some oracle. Doesn't tell that BQP should be greater than class PH? 2. If I compare $BPP^{NP}$ with NP-complete, then which is harder? Jan 26 at 10:53
• This only suggests that BQP is not inside PH. Jan 26 at 13:22
• If this suggests that BQP is not inside PH, then this imply that NP-complete problems lies in BQP since all NP problems lies in PH. Then, why people conjectures (very likely) that quantum computer cannot solve NP-complete problems efficiently? Jan 27 at 4:10
• @user777 You are aware that for two sets, there's possibilities which lie beyond one being inside the other - like they intersect? Jan 27 at 10:31

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.

• Thank you so much Mark for your answer. I just have some points to clarify my understanding. 1. So Boson Sampler is a #P-complete, do you mean that #P-complete is not harder than NP-complete problems? Is #P-complete outside PH? 2. Is BQP and NP are incomparable? because factoring are in NP and also are in BQP (i.e. they have the same kind of problems). Incomparable comes with classes that have different kind of problems such as XP and NP. So, we still don't know relationship between NP and BQP. Jan 22 at 10:25
• #1. #P is harder than NP (in all likelihood) but a Boson Sampler does not solve a #P-complete problem. Nonetheless calculating the probabilities associated with output strings of the Boson Sampler is likely #P-hard. This is very subtle, and understandable that it's confusing. The Boson Sampler merely samples an output string with a probability given by the permanent of a submatrix, but one has no way to control the specific submatrix from which the Boson Sampler samples. . Jan 22 at 14:49
• #2. Although most think that factoring is not in P, factoring is both in BQP and in NP. However there are problems that are in BQP but not even likely in NP (or anywhere in the polynomial hierarchy). If you think of a Venn diagram of NP and BQP, NP and BQP form two intersecting circles. Factoring is inside the common intersection; TSP is in NP but (likely) outside of BQP; forrelation is in BQP but (likely) outside of NP. This is what I mean by "incomparable". And yes, we do not know the relationship between NP and BQP other than we think they are two intersecting circles in the Venn diagram. Jan 22 at 14:56