  We present a classical algorithm that approximately samples from the output
distribution of certain noisy Boson Sampling experiments. This algorithm is
inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and
makes use of an observation originally due to Kalai and Kindler that the output
probability of Boson Sampling experiments with a Gaussian noise model can be
approximated by sparse low-degree polynomials. This observation alone does not
suffice for classical sampling, because its marginal probabilities might not be
approximated by sparse low-degree polynomials, and furthermore, the
approximated probabilities might be negative. We solve this problem by
employing the first quantization representation to give an algorithm for
computing the marginal probabilities of these experiments. We prove that when
the overall noise rate is constant, the algorithm runs in time quasi-polynomial
in the number of input photons $N$ and accuracy. When the overall noise rate
scales as $1-x_1^\gamma$ for constant $x_1$ and $\gamma=\Omega(\log N)$, the
running time becomes polynomial. Furthermore, we study noisy Boson Sampling
with practically relevant noise models such as partial distinguishability and
photon loss. We show that the same technique does not immediately apply in
these settings, leaving open the possibility of a scalable demonstration of
noisy quantum advantage for these noise models in certain parameter regimes.
