Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.27065

Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Photon Loss

Byeongseon Go, Hyunseok Jeong

quant-phSubmitted Oct 19, 2026• Announced Oct 21, 2026• 2 citations
arXivHTMLPDF

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.

Little sign of AI-generated textStrong assumptions

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

Related papers

BosonSampling with lost photons

Scott Aaronson, Daniel J. Brod

BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-correction techniques can be applied to them, and thus it is important to investigate how robust the model is under natural experimental imperfections, such as losses and imperfect control of parameters. Here, we investigate the complexity of BosonSampling under photon losses, more specifically, the case where an unknown subset of the photons is randomly lost at the sources. We show that if $k$ out of $n$ photons are lost, then we cannot sample classically from a distribution that is $1/{n}^{\mathrm{\ensuremath{\Theta}}(k)}$ close (in total variation distance) to the ideal distribution, unless a ${\text{BPP}}^{\text{NP}}$ machine can estimate the permanents of Gaussian matrices in ${n}^{O(k)}$ time. In particular, if $k$ is constant, this implies that simulating lossy BosonSampling is hard for a classical computer, under exactly the same complexity assumption used for the original lossless case.

arXiv:1510.05245•Physical Review A•Jan 21, 2016•88 citations

Classical Simulation of Lossy Gaussian Boson Sampling beyond Square-Root Regime

Youngrong Lim

Photon loss makes Gaussian boson sampling easier to simulate classically. A standard approach replaces the lossy input by classical light, and it stays accurate while the mean number of surviving photons grows no faster than the square root of the number $N$ of squeezed inputs at fixed squeezing and accuracy. We prove that this scale is a limit of replacement by classical light. For explicit interferometers, no state with a nonnegative Glauber--Sudarshan $P$ representation, Gaussian or not and however correlated, keeps the error in the photon count distribution small beyond this scale. We then surpass this limit by approximating the detection instead of the input. The sampler evolves the state exactly between detections and, after each detection, replaces the conditional state by a Gaussian with the same covariance. For every interferometer its total variation error is $O(Nη^3)$ at polynomial expected cost, where $η$ is the photon survival probability. The mean surviving photon number can therefore grow as $N^{2/3}$ at fixed accuracy. A separate pair construction reaches $N^{3/4}$ when every input mode is equally squeezed.

quant-pharXiv:2610.06526•Oct 6, 2026•2 citations

Polynomial-time classical simulation of boson and fermion sampling under thermal loss

Armando Angrisani, Hela Mhiri

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.

arXiv:2611.08444•Nov 5, 2026•0 citations

Boson sampling is fragile to loss

Youngrong Lim

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.

quant-pharXiv:2611.01434•Nov 3, 2026•1 citation

Classically simulating near-term partially-distinguishable and lossy boson sampling

Alexandra E. Moylett, Raúl García−Patrón, Jelmer J Renema +1 more

Abstract Boson sampling is the problem of sampling from the same distribution as indistinguishable single photons at the output of a linear optical interferometer. It is an example of a non-universal quantum computation which is believed to be feasible in the near term and cannot be simulated on a classical machine. Like all purported demonstrations of ‘quantum computational supremacy’, this motivates optimising classical simulation schemes for a realistic model of the problem, in this case boson sampling when the implementations experience lost or distinguishable photons. Although current simulation schemes for sufficiently imperfect boson sampling are classically efficient, in principle the polynomial runtime can be infeasibly large. In this work, we develop a scheme for classical simulation of boson sampling under uniform distinguishability and loss, based on the idea of sampling from distributions where at most k photons are indistinguishable. We show that asymptotically this scheme can provide a polynomial improvement in the runtime compared to classically simulating idealised boson sampling. More significantly, we show that in the regime considered experimentally relevant, our approach gives an substantial improvement in runtime over other classical simulation approaches.

arXiv:1907.00022•Quantum Science and Technology•Nov 7, 2019•40 citations

Sufficient conditions for hardness of lossy Gaussian boson sampling

Byeongseon Go, Changhun Oh, Hyunseok Jeong

Gaussian boson sampling (GBS) is a prominent candidate for the experimental demonstration of quantum advantage. However, while the current implementations of GBS are unavoidably subject to noise, the robustness of the classical intractability of GBS against noise remains largely unexplored. In this work, we establish the complexity-theoretic foundations for the classical intractability of noisy GBS under photon loss, which is a dominant source of imperfection in current implementations. We identify the loss threshold below which lossy GBS maintains the same complexity-theoretic level as ideal GBS, and show that this holds when at most a logarithmic fraction of photons is lost. We additionally derive an intractability criterion for the loss rate through a direct quantification of the statistical distance between ideal and lossy GBS. This work presents the first rigorous characterization of classically intractable regimes of lossy GBS, thereby serving as a crucial step toward demonstrating quantum advantage with near-term implementations.

quant-pharXiv:2511.07853•Nov 12, 2025•8 citations
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 NNN input photons propagate through an MMM-mode interferometer and exactly N−nN-nN−n photons are lost uniformly at random, leaving nnn surviving photons at the output. For any constant surviving fraction n/N∈(0,1)n/N\in(0,1)n/N∈(0,1), the algorithm samples from a distribution within total variation distance ε\varepsilonε of the fixed-loss BosonSampling distribution with probability at least 1−δ1-δ1−δ over Haar-random interferometers, in time poly⁡(M,N,ε−1,δ−1)\operatorname{poly}(M,N,\varepsilon^{-1},δ^{-1})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)η\in(0,1)η∈(0,1). These results substantially extend the known provably simulable regime of n=O(εN)n=O(\sqrt{\varepsilon N})n=O(εN​) surviving photons or η=O(ε/N)η=O(\sqrt{\varepsilon/N})η=O(ε/N​) transmission rate, and demonstrate that even the experimentally relevant linear-survival regime can admit efficient classical simulation under the conditions considered here.
The paper asks whether photon loss permits provably efficient classical sampling from BosonSampling when an extensive number of photons survives. It studies NNN single-photon inputs, a Haar-random MMM-mode interferometer, and a uniformly random surviving subset of exactly n<Nn<Nn<N photons.
For M≥C0n2NM\ge C_0n^2NM≥C0​n2N, it constructs a sampler for the collision-collapsed distribution, retaining individual collision-free outcomes but merging all collisions. For at least a 1−δ1-\delta1−δ fraction of interferometers, the output has total variation error at most ε\varepsilonε. The arithmetic runtime per sample is MnN3ε−2δ−12O(d)MnN^3\varepsilon^{-2}\delta^{-1}2^{O(d)}MnN3ε−2δ−12O(d), where the truncation degree satisfies (n/N)d+1/(1−n/N)≤ε2δ/C(n/N)^{d+1}/(1-n/N)\le\varepsilon^2\delta/C(n/N)d+1/(1−n/N)≤ε2δ/C, with an exact-degree fallback. Thus every fixed surviving fraction in (0,1)(0,1)(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 ∑j>d(nj)/(Nj)\sum_{j>d}\binom nj/\binom Nj∑j>d​(jn​)/(jN​). Haar–Gaussian density domination transfers this bound to collision-free outputs. Randomized color coding reduces marginal evaluation from subset enumeration exponential in dlog⁡Nd\log NdlogN to 2O(d)2^{O(d)}2O(d) overhead, enabling signed-marginal sequential sampling.
An additional condition M=Ω(n2/(εδ))M=\Omega(n^2/(\varepsilon\delta))M=Ω(n2/(εδ)) 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 η∈(0,1)\eta\in(0,1)η∈(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.
BosonSampling is an intermediate model of quantum computation where linear-optical networks are used to solve sampling problems expected to be hard for classical computers. Since these devices are not expected to be universal for quantum computation, it remains an open question of whether any error-correction techniques can be applied to them, and thus it is important to investigate how robust the model is under natural experimental imperfections, such as losses and imperfect control of parameters. Here, we investigate the complexity of BosonSampling under photon losses, more specifically, the case where an unknown subset of the photons is randomly lost at the sources. We show that if kkk out of nnn photons are lost, then we cannot sample classically from a distribution that is $1/{n}^{\mathrm{\ensuremath{\Theta}}(k)}$ close (in total variation distance) to the ideal distribution, unless a BPPNP{\text{BPP}}^{\text{NP}}BPPNP machine can estimate the permanents of Gaussian matrices in nO(k){n}^{O(k)}nO(k) time. In particular, if kkk is constant, this implies that simulating lossy BosonSampling is hard for a classical computer, under exactly the same complexity assumption used for the original lossless case.
Photon loss makes Gaussian boson sampling easier to simulate classically. A standard approach replaces the lossy input by classical light, and it stays accurate while the mean number of surviving photons grows no faster than the square root of the number NNN of squeezed inputs at fixed squeezing and accuracy. We prove that this scale is a limit of replacement by classical light. For explicit interferometers, no state with a nonnegative Glauber--Sudarshan PPP representation, Gaussian or not and however correlated, keeps the error in the photon count distribution small beyond this scale. We then surpass this limit by approximating the detection instead of the input. The sampler evolves the state exactly between detections and, after each detection, replaces the conditional state by a Gaussian with the same covariance. For every interferometer its total variation error is O(Nη3)O(Nη^3)O(Nη3) at polynomial expected cost, where ηηη is the photon survival probability. The mean surviving photon number can therefore grow as N2/3N^{2/3}N2/3 at fixed accuracy. A separate pair construction reaches N3/4N^{3/4}N3/4 when every input mode is equally squeezed.
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.
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.
Abstract Boson sampling is the problem of sampling from the same distribution as indistinguishable single photons at the output of a linear optical interferometer. It is an example of a non-universal quantum computation which is believed to be feasible in the near term and cannot be simulated on a classical machine. Like all purported demonstrations of ‘quantum computational supremacy’, this motivates optimising classical simulation schemes for a realistic model of the problem, in this case boson sampling when the implementations experience lost or distinguishable photons. Although current simulation schemes for sufficiently imperfect boson sampling are classically efficient, in principle the polynomial runtime can be infeasibly large. In this work, we develop a scheme for classical simulation of boson sampling under uniform distinguishability and loss, based on the idea of sampling from distributions where at most k photons are indistinguishable. We show that asymptotically this scheme can provide a polynomial improvement in the runtime compared to classically simulating idealised boson sampling. More significantly, we show that in the regime considered experimentally relevant, our approach gives an substantial improvement in runtime over other classical simulation approaches.
Gaussian boson sampling (GBS) is a prominent candidate for the experimental demonstration of quantum advantage. However, while the current implementations of GBS are unavoidably subject to noise, the robustness of the classical intractability of GBS against noise remains largely unexplored. In this work, we establish the complexity-theoretic foundations for the classical intractability of noisy GBS under photon loss, which is a dominant source of imperfection in current implementations. We identify the loss threshold below which lossy GBS maintains the same complexity-theoretic level as ideal GBS, and show that this holds when at most a logarithmic fraction of photons is lost. We additionally derive an intractability criterion for the loss rate through a direct quantification of the statistical distance between ideal and lossy GBS. This work presents the first rigorous characterization of classically intractable regimes of lossy GBS, thereby serving as a crucial step toward demonstrating quantum advantage with near-term implementations.