Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Photon Loss

Abstract

Understanding how photon loss changes the classical complexity of BosonSampling is central to assessing the robustness of near-term photonic quantum advantage. In this work, we present a polynomial-time classical simulation algorithm for lossy BosonSampling that applies whenever a constant fraction of the input photons survives. We consider the standard fixed-loss model, where $N$ input photons propagate through an $M$-mode interferometer and exactly $N-n$ photons are lost uniformly at random, leaving $n$ surviving photons at the output. For any constant surviving fraction $n/N\in (0,1)$, the algorithm samples from a distribution within total variation distance $\epsilon$ of the fixed-loss BosonSampling distribution with probability at least $1-\delta$ over Haar-random interferometers, in time $\mathrm{poly}(M,N,{\epsilon }^{-1},{\delta }^{-1})$. We further extend the fixed-loss analysis to the uniform-transmission-loss model and obtain analogous polynomial-time simulability for any fixed transmission rate $\eta \in (0,1)$. These results substantially extend the known provably simulable regime of $n=O(\sqrt{\epsilon N})$ surviving photons or $\eta =O(\sqrt{\epsilon /N})$ transmission rate, and demonstrate that even the experimentally relevant linear-survival regime can admit efficient classical simulation under the conditions considered here.

arXiv comment33 pages, 3 figures