Exact simulation of Gaussian boson sampling in polynomial space and exponential time

This work introduces a classical algorithm that can simulate the output of a Gaussian Boson Sampling device in time exponential in the number of photons detected and in only polynomial space in the number of modes/photons. The algorithm takes advantage of the fact that the marginal Wigner functions of Gaussian states can be easily calculated.