arXiv · Oct 19, 2026
Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Photon Loss
By Byeongseon Go, Hyunseok Jeong
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∈(0,1), the algorithm samples from a distribution within total variation distance ε of the fixed-loss BosonSampling distribution with probability at least 1-δ over Haar-random interferometers, in time poly(M,N,ε⁻¹,δ⁻¹). We further extend the fixed-loss analysis to the uniform-transmission-loss model and obtain analogous polynomial-time simulability for any fixed transmission rate η∈(0,1). These results substantially extend the known provably simulable regime of n=O(√ε N) surviving photons or η=O(√ε/N) transmission rate, and demonstrate that even the experimentally relevant linear-survival regime can admit efficient classical simulation under the conditions considered here.