Cracking the Quantum Advantage threshold for Gaussian Boson Sampling

Quantum advantage, defined as a computational result unattainable with classical computers, is a major goal of scientists currently developing quantum technologies. Recently, quantum advantage was claimed for a Gaussian boson sampling setup in which $N=50$ squeezed states of light pass through a linear optical network. The emulation of many-body statistics of identical photons in this system is seen as a computationally hard problem: the number of elementary operations grows exponentially with $N$. Thus, reproducing the experimentally observed counting statistics of the output detectors is believed to be far beyond capabilities of any classical computer. Here we challenge this statement by introducing a series of approximations for the probability of any specific measurement outcome, obeying a polynomial complexity. Our fourth order approximation gives an accuracy comparable with that of the experimental set-up and can be calculated using a laptop computer.