arXiv:2611.01434
Boson sampling is fragile to loss
Youngrong Lim
Abstract
Boson sampling experiments aim to demonstrate quantum computational advantage with increasing numbers of interfering photons. A central question is whether their computational hardness survives under photon loss. We show that even an arbitrarily small nonzero uniform loss rate permits efficient classical sampling in the average case when the rate remains fixed as the system grows. We exploit how loss suppresses correlations involving many photons to approximate the full output distribution using low correlation orders. The resulting samplers run in time polynomial in system size and inverse total variation error, with the error averaged over Haar random interferometers. The results apply to Fock state boson sampling with single-photon states in distinct input modes and arbitrary additional vacuum inputs, and to Gaussian boson sampling with equal squeezing of bounded strength in every input mode. Classical sampling is efficient even when the mean detected photon number grows linearly with system size, showing that large photon counts alone do not ensure computational hardness.
AI Summary
The paper asks whether boson-sampling hardness survives a fixed nonzero photon-loss rate when approximation error can decrease inverse-polynomially with system size. It constructs classical samplers with $\mathbb E_{U\sim\mathrm{Haar}}\operatorname{TV}(P_U,Q_U)\le\epsilon$ and worst-case runtime polynomial in mode count and $1/\epsilon$, for every fixed transmission $0<\eta<1$. The results cover single photons in $n$ distinct inputs for every $M\ge n$, including collisions, and Gaussian boson sampling with equal, bounded squeezing in all $M$ inputs. Mean detected photon numbers may grow linearly with system size. The construction decomposes rescaled output probabilities into orthogonal photon-correlation orders. For Fock inputs, the Haar- and photon-count-averaged weight at order $h$ is at most $\eta^h$, giving squared truncation error at most $\eta^{L+1}/(1-\eta)$. Gaussian inputs admit analogous geometric bounds on typical photon-number sectors. Two-sided projection, randomized grouping of mode labels, and determinant generating functions evaluate retained orders at cost exponential rather than system-size-to-the-power-$L$. Consequently, $L=O(1+\log(1/\epsilon))$ suffices. Clipped, bounded-trial rejection sampling converts these estimates into samples. Accuracy is Haar-averaged, not guaranteed for a specified structured interferometer. Polynomial degrees and constants depend on loss and squeezing; no practical spoofing runtime is established. General internal path-dependent loss and unequal squeezing are not covered. With vacuum inputs, the Gaussian extension requires $\eta\cosh(2r)<1$. The intermediate Fock loss regime $\log n\ll(1-\eta)n\ll n$ remains unresolved.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 9+30 pages, 1 figure. Identical to the version posted on Zenodo on 21 October 2026 (doi:10.5281/zenodo.23528696)