Polynomial-time classical simulation of boson and fermion sampling under thermal loss
Abstract
Sampling experiments are a leading approach to demonstrating quantum computational advantage, yet their robustness to experimental noise is not completely understood. We develop a common framework for classical simulation of boson and fermion sampling under thermal loss, including pure loss. For Fock-state boson sampling, Gaussian boson sampling with fixed uniform squeezing, and fermion sampling with magic inputs, we obtain polynomial-time sampling at inverse-polynomial total variation error, for any fixed nonzero overall loss rate, and with high probability over Haar-random interferometers. A milder flatness assumption on the ideal output distribution suffices for quasipolynomial-time simulation without Haar randomness. With constant thermal loss per layer, the same flatness assumption gives polynomial-time simulation at logarithmic depth. Our bounds for Fock-state boson sampling cover both dilute and saturated regimes and become stronger near full input filling: when only a bounded number of input modes are empty, the noisy output for Haar-random interferometers converges, as the number of modes grows, to a distribution independent of the interferometer.
Related
- Integrable Generators of Polynomial Vector Fields for Complex Classical Lie Groups
- Shifted Pell–Lucas Polynomial-Based Algorithms for Fractional and Classical Rosenau–Hyman Models
- Polynomial-time classical algorithms for mean-field models up to the glass transition
- Finite-Data Error Bounds for Approximating the Koopman Operator: Sampling Measures, Super-Polynomial Convergence and Regularization
- Quantum estimates for classical polynomial optimization
BibTeX
@misc{angrisani2026polynomialtime,
title = {{Polynomial-time classical simulation of boson and fermion sampling under thermal loss}},
author = {Armando Angrisani and Hela Mhiri},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.08444},
eprint = {2611.08444},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.08444},
}
RIS
TY - UNPB
TI - Polynomial-time classical simulation of boson and fermion sampling under thermal loss
AU - Armando Angrisani
AU - Hela Mhiri
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.08444
UR - https://arxiv.org/abs/2611.08444
AB - Sampling experiments are a leading approach to demonstrating quantum computational advantage, yet their robustness to experimental noise is not completely understood. We develop a common framework for classical simulation of boson and fermion sampling under thermal loss, including pure loss. For Fock-state boson sampling, Gaussian boson sampling with fixed uniform squeezing, and fermion sampling with magic inputs, we obtain polynomial-time sampling at inverse-polynomial total variation error, for any fixed nonzero overall loss rate, and with high probability over Haar-random interferometers. A milder flatness assumption on the ideal output distribution suffices for quasipolynomial-time simulation without Haar randomness. With constant thermal loss per layer, the same flatness assumption gives polynomial-time simulation at logarithmic depth. Our bounds for Fock-state boson sampling cover both dilute and saturated regimes and become stronger near full input filling: when only a bounded number of input modes are empty, the noisy output for Haar-random interferometers converges, as the number of modes grows, to a distribution independent of the interferometer.
ER -