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• 0 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.

Comments
33 pages, 3 figures

Related papers

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•0 citations

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•32 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.

•Oct 21, 2026•0 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•0 citations

Classical simulation of photonic linear optics with lost particles

Michał Oszmaniec, Daniel J. Brod

We explore the possibility of efficient classical simulation of linear optics experiments under the effect of particle losses.Specifically, we investigate the canonical boson sampling scenario in which an nparticle Fock input state propagates through a linear-optical network and is subsequently measured by particle-number detectors in the m output modes.We examine two models of losses.In the first model a fixed number of particles is lost.We prove that in this scenario the output statistics can be well approximated by an efficient classical simulation, provided that the number of photons that is left grows slower than n .In the second loss model, every time a photon passes through a beamsplitter in the network, it has some probability of being lost.For this model the relevant parameter is s, the smallest number of beamsplitters that any photon traverses as it propagates through the network.We prove that it is possible to approximately simulate the output statistics already if s grows logarithmically with m, regardless of the geometry of the network.The latter result is obtained by proving that it is always possible to commute s layers of uniform losses to the input of the network regardless of its geometry, which could be a result of independent interest.We believe that our findings put strong limitations on future experimental realizations of quantum computational supremacy proposals based on boson sampling.

arXiv:1801.06166•New Journal of Physics•Sep 7, 2018•97 citations

On classical simulation algorithms for noisy Boson Sampling

Changhun Oh, Liang Jiang, Bill Fefferman

We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments. This algorithm is inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and makes use of an observation originally due to Kalai and Kindler that the output probability of Boson Sampling experiments with a Gaussian noise model can be approximated by sparse low-degree polynomials. This observation alone does not suffice for classical sampling, because its marginal probabilities might not be approximated by sparse low-degree polynomials, and furthermore, the approximated probabilities might be negative. We solve this problem by employing the first quantization representation to give an algorithm for computing the marginal probabilities of these experiments. We prove that when the overall noise rate is constant, the algorithm runs in time quasi-polynomial in the number of input photons $N$ and accuracy. When the overall noise rate scales as $1-x_1^γ$ for constant $x_1$ and $γ=Ω(\log N)$, the running time becomes polynomial. Furthermore, we study noisy Boson Sampling with practically relevant noise models such as partial distinguishability and photon loss. We show that the same technique does not immediately apply in these settings, leaving open the possibility of a scalable demonstration of noisy quantum advantage for these noise models in certain parameter regimes.

arXiv:2301.11532•Jan 27, 2023•3 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.
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.
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.
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.
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.
We explore the possibility of efficient classical simulation of linear optics experiments under the effect of particle losses.Specifically, we investigate the canonical boson sampling scenario in which an nparticle Fock input state propagates through a linear-optical network and is subsequently measured by particle-number detectors in the m output modes.We examine two models of losses.In the first model a fixed number of particles is lost.We prove that in this scenario the output statistics can be well approximated by an efficient classical simulation, provided that the number of photons that is left grows slower than n .In the second loss model, every time a photon passes through a beamsplitter in the network, it has some probability of being lost.For this model the relevant parameter is s, the smallest number of beamsplitters that any photon traverses as it propagates through the network.We prove that it is possible to approximately simulate the output statistics already if s grows logarithmically with m, regardless of the geometry of the network.The latter result is obtained by proving that it is always possible to commute s layers of uniform losses to the input of the network regardless of its geometry, which could be a result of independent interest.We believe that our findings put strong limitations on future experimental realizations of quantum computational supremacy proposals based on boson sampling.
We present a classical algorithm that approximately samples from the output distribution of certain noisy Boson Sampling experiments. This algorithm is inspired by a recent result of Aharonov, Gao, Landau, Liu and Vazirani and makes use of an observation originally due to Kalai and Kindler that the output probability of Boson Sampling experiments with a Gaussian noise model can be approximated by sparse low-degree polynomials. This observation alone does not suffice for classical sampling, because its marginal probabilities might not be approximated by sparse low-degree polynomials, and furthermore, the approximated probabilities might be negative. We solve this problem by employing the first quantization representation to give an algorithm for computing the marginal probabilities of these experiments. We prove that when the overall noise rate is constant, the algorithm runs in time quasi-polynomial in the number of input photons NNN and accuracy. When the overall noise rate scales as 1−x1γ1-x_1^γ1−x1γ​ for constant x1x_1x1​ and γ=Ω(log⁡N)γ=Ω(\log N)γ=Ω(logN), the running time becomes polynomial. Furthermore, we study noisy Boson Sampling with practically relevant noise models such as partial distinguishability and photon loss. We show that the same technique does not immediately apply in these settings, leaving open the possibility of a scalable demonstration of noisy quantum advantage for these noise models in certain parameter regimes.