arXiv:2610.27065
Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Photon Loss
Byeongseon Go, Hyunseok Jeong
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\in(0,1)$, the algorithm samples from a distribution within total variation distance $\varepsilon$ of the fixed-loss BosonSampling distribution with probability at least $1-δ$ over Haar-random interferometers, in time $\operatorname{poly}(M,N,\varepsilon^{-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 $η\in(0,1)$. These results substantially extend the known provably simulable regime of $n=O(\sqrt{\varepsilon N})$ surviving photons or $η=O(\sqrt{\varepsilon/N})$ transmission rate, and demonstrate that even the experimentally relevant linear-survival regime can admit efficient classical simulation under the conditions considered here.
AI Summary
The paper asks whether photon loss permits provably efficient classical sampling from BosonSampling when an extensive number of photons survives. It studies $N$ single-photon inputs, a Haar-random $M$-mode interferometer, and a uniformly random surviving subset of exactly $n<N$ photons. For $M\ge C_0n^2N$, it constructs a sampler for the collision-collapsed distribution, retaining individual collision-free outcomes but merging all collisions. For at least a $1-\delta$ fraction of interferometers, the output has total variation error at most $\varepsilon$. The arithmetic runtime per sample is $MnN^3\varepsilon^{-2}\delta^{-1}2^{O(d)}$, where the truncation degree satisfies $(n/N)^{d+1}/(1-n/N)\le\varepsilon^2\delta/C$, with an exact-degree fallback. Thus every fixed surviving fraction in $(0,1)$ gives polynomial runtime, including for inverse-polynomial error and failure probability; the polynomial degree can depend on that fraction. The construction uses a Hoeffding decomposition of averaged squared permanents. Gaussian orthogonality gives normalized mean-square truncation error $\sum_{j>d}\binom nj/\binom Nj$. Haar–Gaussian density domination transfers this bound to collision-free outputs. Randomized color coding reduces marginal evaluation from subset enumeration exponential in $d\log N$ to $2^{O(d)}$ overhead, enabling signed-marginal sequential sampling. An additional condition $M=\Omega(n^2/(\varepsilon\delta))$ yields full Fock-output approximation by absorbing collision probability into the error. Conditioning on binomial survivor-number sectors extends polynomial simulability to every fixed uniform transmission rate $\eta\in(0,1)$. The guarantees are Haar-average-case and dilute-mode, not arbitrary-interferometer results. Collision-rich regimes, partial distinguishability, and nonideal detection remain outside the established scope.
Central claim may not hold: The abstract omits the dilute-mode hypothesis M ≥ C₀n²N for fixed loss and M ≥ C₀N³ in the uniform-transmission corollary, so the proved guarantees do not follow from constant survival or transmission alone. The abstract presents an unqualified output-distribution approximation, whereas the main theorem resolves only collision-free outcomes and aggregates collisions, with full Fock-output approximation requiring an additional collision-suppression bound that matters for sufficiently small εδ.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 33 pages, 3 figures