Classical simulation of noisy boson and fermion sampling runs in polynomial time
Polynomial-time classical simulation of boson and fermion sampling under thermal loss
Computational Complexity
Summary
Quantum experiments using bosons and fermions aim to show computers doing tasks faster than classical ones, but noise can make these experiments less reliable. The authors found ways to simulate these noisy experiments efficiently on classical computers when there is some loss of particles or thermal noise. Their methods work under common conditions like random setups and varying amounts of noise, showing that noise can simplify the simulation challenge. This helps clarify when quantum advantage remains and when classical computers can keep up.
What this means in practice
- •For quantum algorithm developers: Optimize quantum sampling experiments by understanding which noise levels still allow classical simulation, guiding focus on setups harder to simulate.
- •For quantum hardware engineers: Design interferometers and control loss rates to minimize classical simulability, preserving quantum advantage in real devices.
Authors
Armando Angrisani, Hela Mhiri
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.