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

arXiv:2610.27065v1 Announce Type: new 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 $\varepsilon$ of the fixed-loss BosonSampling distribution with probability at least $1-\delta$ over Haar-random interferometers, in time $\operatorname{poly}(M,N,\varepsilon^{-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{\varepsilon N})$ surviving photons or $\eta=O(\sqrt{\varepsilon/N})$ transmission rate, and demonstrate that even the experimentally relevant linear-survival regime can admit efficient classical simulation under the conditions considered here.