Testing boson sampling with classical algorithms

Based on the laws of quantum mechanics, future quantum computers will perform dramatically better than their conventional classical counterparts. However, large-scale universal quantum computers have yet to be built. Boson sampling, which is designed based on a linear optical network, has been considered as a fast way to demonstrate quantum superiority. While it is difficult to efficiently simulate boson sampling without noise using a classical computer, current boson sampling experiments are accompanied by loss and noise. Classical algorithms are presented for simulating Gaussian boson sampling experiments, where the sampling complexity can be significantly reduced by increasing the photon loss rate, and by simulating the true-basis distribution, they challenge claims of experimental quantum superiority.