# Techniques: Classical simulability of noisy boson sampling

## What the paper contributes (one paragraph)
The paper gives a classical algorithm that simulates boson sampling in the presence of the two dominant photonic imperfections, linear photon loss (per-photon transmission eta) and partial distinguishability (internal-state overlap x). The probability of an output is expanded into terms describing interference of j bosons; imperfections exponentially suppress the high-j terms, so the sum can be truncated at a level k that depends only on the noise parameters and not on the total photon number n. The truncated approximate distribution is fed to a Metropolis Markov-chain Monte Carlo sampler, giving an efficient classical sampler whose trace-distance error is bounded. Because k is finite for any eta, x less than 1, noisy boson sampling is asymptotically non-scalable, and k upper-bounds the size of a hard sampler buildable from given components. Evaluating the bound for state-of-the-art photonic sources shows current technology cannot demonstrate quantum advantage beyond about 21 bosons.

## Techniques offered
- **Classical simulation of lossy and partially distinguishable boson sampling** - truncates the few-boson interference expansion at order k set by the noise and samples the resulting approximate distribution with a Metropolis MCMC, yielding an efficient classical sampler for a noisy photonic sampling device.
  - guarantee: statistical bound on the expected L1 (trace) distance between the approximate and exact output distributions, E[d] <= sqrt(alpha^(k+1)/(1-alpha)) with alpha = eta x^2, lifted to a per-instance failure probability via Markov's inequality.
  - quote: "To use our results for sampling, we use our approximation as the input for a Metropolis sampler that samples efficiently from our approximate probability distribution, which results in a classical simulator of boson sampling with losses."
- **Noise-threshold estimate for photonic quantum advantage** - solves the error bound for the maximum classically hard sampler size k as a function of measured transmission and distinguishability, mapping out the region of component quality where a boson sampling advantage is still possible and benchmarking real photon sources against it.
  - guarantee: a scale-invariant figure of merit alpha = eta x^2 and an explicit upper bound k on the number of coherently interfering bosons admissible at a given noise level and accuracy.
  - quote: "We can use our results to estimate the quality of experimental components required to demonstrate a quantum advantage."

## Where it could apply
- Target primitive(s): sampling (boson sampling and, as suggested for future work, Gaussian boson sampling)
- Target application group(s): platforms_tooling

## Caveats
The bounds are derived for uniform (path-independent) loss, uniform pairwise distinguishability, and the collisionless regime over Haar-random interferometers; the failure bound is probabilistic, so the simulator fails for a fraction of unitaries, and the authors note the Markov bound grossly overestimates this fraction. Non-uniform losses, more general distinguishability models, and a direct (non-Metropolis) sampler are left to future work.