What about BosonSampling can be publicly verified?

Question

Boson Sampling, sometimes stylized as BosonSampling, is an attractive candidate problem to establish quantum supremacy; the engineering problems appear more surmountable than those associated with a Turing-complete quantum computer.

However, Boson Sampling has a downside, in that the output of a photonic quantum computer capable of executing Boson Sampling with only a handful ($\le 100$ or so) of qubits may not even be able to be clasically simulated. This is, of course, unlike $\mathsf{NP}$ problems such as factoring, the engineering aspects of which are significantly harder.

Thus, we may establish the results of Boson Sampling on $100$ or so photons, but in order to verify the results, we need to calculate the permanent of a $100\times100$ matrix. This is famously computationally hard to verify.

Maybe a supercomputer powerful enough to calculate the permanent can do the trick. But then everyone would have to believe both the supercomputer's results and the Boson Sampling results.

Is there anything about Boson Sampling that can be easily verified?

I've had a flight of fancy to maybe put the resources of a cryptocurrency mining network to use to calculate such a permanent, and relying on some $\mathsf{\#P}$ / $\mathsf{IP}$ tricks for public verification, but I haven't gotten very far.

EDIT

I like @gIS's answer.

Compare Boson Sampling with Appel and Franken's computer-assisted proof of the Four Color Theorem. The original proof of the 4CT was allegedly controversial, precisely because the proof was too long to be publicly verified by a human reader. We've moved so far from the '70's with our trust of computers, wherein I think now most people accept the proof of the 4CT without much controversy. But thinking about how to make things like a proof of the 4CT human-verifiable may lead to interesting ideas like the $\mathsf{PCP}$ theorem.

Answer 1

About the need of boson sampling verification

First of all, let me point out that it is not a strict necessity to verify the output of a boson sampler. By this, I don't mean to say that it is not useful or interesting to try and do so, but rather that it is in some sense more of a practical than a fundamental necessity.

I think you yourself put up a good argument for this when you write

Maybe a supercomputer powerful enough to calculate the permanent can do the trick. But then everyone would have to believe both the supercomputer's results and the Boson Sampling results.

Indeed, there are many instances in which one solves a problem and trusts a solution which cannot really be fully verified. I mean, forget quantum mechanics, just use your computer to multiply two huge numbers. You probably have high confidence that the result you get is correct, but how do you verify it without using another computer?

More generally, trust in a device's results comes from a variety of things, such as knowledge of the inner working of the device, and unit testing of the device itself (that is, testing that it works correctly for the special instances that you can verify with some other method).

The problem of boson sampling certification is no different. We know that, at some point, we will not be able to fully verify the output of a boson sampler, but that does not mean that we will not be able to trust it. If the device is built with due thoroughness, and its output is verified for a variety of small instances, and other tests that one is able to carry out are all successful, then at some point one builds up enough trust in the device to make a quantum supremacy claim (or whatever else one wants to use the boson sampler for) meaningful.

Is there anything about BosonSampling that can be easily verified?

Yes, there are properties that can be verified. Due to the sampling nature of the problem, what people typically do is to rule out alternative models that might have generated the observed samples. For example, Aaronson and Arkhipov (1309.7460) showed that the BosonSampling distribution is far from the uniform distribution in total variation distance (with high probability over the Haar-random matrices inducing the distribution), and gave a protocol to efficiently distinguish the two distributions. A more recent work showing how statistical signatures can be used to certify the boson sampling distribution against alternative hypotheses is (Walschaers et al. 2014).

The other papers that I am aware of focus on certifying specific aspects of a boson sampler, rather than directly tackling the problem of finding alternative distributions which are far from the BosonSampling one for random interferometers.

More specifically, one can isolate two major possible sources of error in a boson sampling apparatus: those arising from incorrectly implementing the interferometer, and those arising from the input photons not being what they should be (that is, totally indistinguishable).

The first case is (relatively) easy to handle because one can efficiently characterise an interferometer using single photons. However, certifying the indistinguishability of input photons is trickier. One idea to do this is to change the interferometer to a non-random one, such as the QFT interferometer, and see whether something can be efficiently verified in this simpler case. I won't try to add all the relevant references here, but this direction started with (Tichy et al. 2010, 2013).

Regarding the public verification aspect, there isn't anything done in this direction that I've heard of. I am also not sure whether it is even a particularly meaningful direction to explore: why should we require such a "high standard" of verification for a boson sampler, when for virtually any other kind of experiment we are satisfied with trusting the people doing the experiment to be good at what they are doing?

Answer 2

Just a small complement to @gIS excellent answer: I know of several people (including myself) interested on the public verification aspect. As far as I know, all attempts have failed, hence the lack of literature on the subject: as soon as one can prove the Boson sampler acted correctly, it is indeed a regime where the Boson sampler can be efficiently simulated classically.

Note that such a verification is not totally hopeless, as it exists in the related $IQP$ non-universal computation model introduced by Shepherd and Brenner in (arXiv:0809.0847 / Proc. R. Soc. A 465, 1413). $IQP$ stands for Instantaneous Quantum computing in Polynomial time. In this model, one only applies commuting gates, but they do not commute with the computational basis. This leads to quantum superiority through a model widely thought to be less powerful as BQP, like boson sampling. In this model, there are ways to embed computation with known results (the paper speaks about matroids, but I honestly do not understand this part) inside larger computations showing quantum advantage and use them to verify the computation. Attempts have been made to hide submatrices with known determinants inside larger matrices for boson sampling, but, as far as I know, all such submatrix family tried for such role have some telltale signs (usually too big coefficients) allowing them to be detected in $P$, thus defeating their very purpose.