This is a quick and preliminary post about a very recent announcement in a Science Magazine paper: Quantum computational advantage using photons by a group of researchers leaded by Jianwei Pan and Chao-Yang Lu. (Most of the researchers are from USTC in Hefei, China.)
The paper announces achieving quantum advantage (aka “quantum supremacy”) using photonic implementation of BosonSampling. (I heard about it from a SO post that contains further links.) The claimed advantage is huge and clearly I will have to look carefully at the results, the data, and the interpretation. The idea that this could be done was raised ten years ago by Aaronson and Arkhipov and we discussed it in here and in several other posts along with the idea that it cannot be done.
Boson Sampling was studied in a 2014 paper by Guy Kindler and me Gaussian Noise Sensitivity and BosonSampling. Our paper and the connection with noise sensitivity and the Fourier description is the basis for my argument against quantum computers. Of course, a demonstration of a huge quantum advantage, as claimed in the new paper, if valid, would refute my theory.
The crux of the matter is if the statistical performance of the photonic samples produced in the experiment could be achieved by classical sampling. (This is referred to as “spoofing.”) My paper with Guy proposes a very simple way to try to do it based on the low degree Hermite-Fourier truncation of the Boson Sampling distribution.
The easiest way to implement it is as follows: Given an n by m matrix you draw (with the appropriate weights based on repeated columns) at random n by n minor M (with repeated columns), then compute the degree k approximation X to the |permanent(M)|^2, (based on formula (8) from our paper) and then take the sample with probability according to the value of X and toss it away otherwise. This may work even for degree-2 truncation. (Rather than the straight truncation we can also try the “Beckner-noise” version but I don’t think this will make much difference.)
Since my paper with Guy Kindler offers “off the shelf” classic algorithm that may “spoof” the claims I propose to test it. (And I am a little surprised that this was not tried already.)