Efficient approximation of experimental Gaussian boson sampling

Recent landmark experiments have performed Gaussian boson sampling (GBS) with a non-programmable linear interferometer and threshold detectors on up to 144 output modes. We introduce a family of classical algorithms that approximately sample from the output of a GBS experiment at a cost polynomial in the number of modes. The quality of our mockup samplers increases with k, the “order” of the sampler, albeit at a cost exponential in k. Our numerical findings provide evidence that already at order k=2 (with cost quadratic in the number of modes) these algorithms approximate the ideal GBS distribution with lower statistical distance than current experiments, which suffer from experimental imperfections. This is a 2nd order approximation, with the uniform and thermal approximations corresponding to 0th and 1st order, respectively. The kth order approximation reproduces Ursell functions up to order k with a cost exponential in k and high precision, while experiments exhibit higher order Ursell functions with lower precision. Our approximations provide a family of strong classical contenders that experiments should be benchmarked against, as well as insight on the nature of the hardness of noisy GBS. Interestingly, the strategy we exploit does not apply to random circuit sampling.