Cracking the Quantum Advantage threshold for Gaussian Boson Sampling

Scientists in quantum technology aspire to quantum advantage: a computational result unattainable with classical computers. Gaussian boson sampling experiment has been already claimed to achieve this goal. In this setup squeezed light states interfere in a mid-sized linear optical network, where multi-photon collisions take place. The exact simulation of the counting statistics of $n$ threshold detectors is far beyond the possibilities of modern supercomputers once $n$ exceeds $100$. Here we challenge quantum advantage for a mid-sized Gaussian boson sampling setup and propose the approximate algorithm to obtain the probability of any specific measurement outcome. For an 70-mode device on a laptop, our approximation achieves accuracy competitive with the experimental one.Comment: The supplementary material is uploaded as a separate fil