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∈(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,ε−1,δ−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 η∈(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.
Related
- Polynomial-time classical simulation of boson and fermion sampling under thermal loss
- Polynomial-time classical and quantum simulation of quantum impurity models
- Design and Monte Carlo simulation of a phase grating moiré neutron interferometer to measure the gravitational constant
- Hyperbolic color codes with constant rate and polynomial distance
- A polynomial-time classical sampler for noisy quantum circuits from statistical mechanics
BibTeX
@misc{go2026polynomialtime,
title = {{Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Photon Loss}},
author = {Byeongseon Go and Hyunseok Jeong},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27065},
eprint = {2610.27065},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27065},
}
RIS
TY - UNPB
TI - Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Photon Loss
AU - Byeongseon Go
AU - Hyunseok Jeong
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.27065
UR - https://arxiv.org/abs/2610.27065
AB - 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,ε^−1,δ^−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 η∈(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.
ER -