betaFeedback

WorksPhysics and Astronomy

Boson sampling is fragile to loss

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.

Introduction

In an optical boson sampler, indistinguishable photons interfere in a network of beam splitters and phase shifters, and detectors record the photon number at each output. The computational task is to sample this joint output distribution for a specified input state and interferometer. Experimental runs provide these samples directly, whereas classical simulation is believed to be intractable under plausible assumptions [1]. This makes boson sampling a candidate for demonstrating quantum computational advantage without a universal quantum computer. Photonic implementations toward this goal use single photons [2] or squeezed light [3, 4, 5, 6, 7, 8, 9] in free-space optics, optical fibers and integrated circuits, with increasing numbers of photons and optical modes.

Photon loss is a severe parameter in experiments. Jiuzhang 4.0, for example, reports an overall system efficiency of 51%, corresponding to detection of only about half the generated photons [8]. Assessing quantum computational advantage in these experiments therefore requires understanding the classical cost of sampling from their lossy output distributions. Conditional hardness has been established when only a logarithmic number of photons is lost on average [10, 11, 12], whereas efficient classical simulation is known under sufficiently strong loss that the surviving fraction tends to zero [13, 14, 15, 16, 17, 18]. These earlier results left a broad range between the two regimes unresolved, including the experimentally relevant case of a fixed loss rate. At a fixed rate, both the mean detected count and the mean number of lost photons grow in proportion to the input size.

For two standard families of input states, we show that a classical computer can efficiently sample the lossy output distribution at any fixed rate of uniform photon loss, however small. The first family is Fock state boson sampling with one photon in each occupied input mode and any number of empty modes. The second is Gaussian boson sampling with all input modes squeezed equally, by an amount that stays bounded as the system grows. Accuracy is the total variation distance between the distribution produced by the classical sampler and the lossy output distribution, taken over all output configurations and averaged over Haar random interferometers. Bringing this distance below any target takes time polynomial in the number of modes and in the inverse of the target. The running time therefore stays polynomial even when the error shrinks as an inverse polynomial in system size.

These are exactly the conditions under which the hardness of boson sampling is argued, with the same input states, Haar random interferometers and inverse polynomial total variation error [1, 12, 19]. Our results differ from those arguments only in the amount of photon loss. In the known hard regime, only a logarithmic number of photons is lost on average, whereas we prove efficient sampling whenever a fixed fraction of the photons is lost. The unresolved range between the two regimes is thereby narrowed to loss rates that decrease toward zero as the system grows. Experiments performed with interferometers close to Haar random at a fixed loss rate therefore cannot guarantee quantum computational advantage.

Problem

In a boson sampling task, an input state of MM optical modes passes through a passive linear interferometer, and photon number resolving detectors count the photons in every output mode. The interferometer acts on the mode operators through an M×MM \times M unitary matrix UU. Each photon reaches the detectors with probability η\eta, independently of the other photons and of its path through the interferometer (Figure 1a). We call 0<η<10 < \eta< 1 the transmission and 1−η1 - \eta the loss rate. A run yields an output configuration x=(x1,…,xM)x = (x_1, \ldots, x_M) with k=∑ixik = \sum_i x_i detected photons, and PU(x)P_U(x) denotes its probability for a given input state. This distribution includes every value of kk and every configuration with several photons in one output mode. Although we use optical language, the analysis relies only on bosonic statistics and uniform particle loss, so it applies equally to other noninteracting bosons, such as atoms in optical lattices [20].

Figure 1. Loss suppresses correlations among many photons. a, Single photons enter a Haar random interferometer UU, and each photon reaches the photon number resolving detectors with probability η\eta. b, Upper bound on the mean squared error, averaged over UU, from keeping only correlations among at most LL photons, for n=100n = 100 single photons. Without loss (η=1\eta= 1) the error decreases only linearly in LL, whereas loss makes it decay exponentially. c, Cutoff LL needed for total variation error 1/n1/n. It grows only logarithmically with the number of detected photons.

The interferometer is drawn once from the Haar measure, the uniform distribution on M×MM \times M unitary matrices, and is then kept fixed for all runs. A classical sampler receives UU and outputs samples from a distribution QUQ_U. We measure its error by the total variation distance dTV(PU,QU)=12∑x∣PU(x)−QU(x)∣d_{\mathrm{TV}}(P_U,Q_U) = \frac{1}{2}\sum_x \lvert P_U(x)-Q_U(x)\rvert, which bounds the error in the probability of every set of output configurations. We consider two input families.

Problem 1 (Lossy Fock state boson sampling). Single photons occupy n≤Mn \le M distinct input modes, and the remaining modes are in vacuum,

∣ΨF⟩=∣1⟩⊗n∣0⟩⊗(M−n).(1)\lvert\Psi_{\mathrm{F}}\rangle= \lvert1\rangle^{\otimes n}\lvert0\rangle^{\otimes(M-n)}. \tag*{(1)}

Given UU, η\eta and ϵ>0\epsilon> 0, generate samples from a distribution QUQ_U with EU∼HaardTV(PU,QU)≤ϵ\mathbb{E}_{U\sim\mathrm{Haar}}d_{\mathrm{TV}}(P_U,Q_U) \le\epsilon, where PUP_U is the output distribution of this input under uniform loss with transmission η\eta.

Problem 2 (Lossy Gaussian boson sampling). Squeezed vacuum states with a common squeezing parameter r≥0r \ge0 occupy s≤Ms \le M input modes, and the remaining modes are in vacuum,

∣ΨG⟩=∣ξr⟩⊗s∣0⟩⊗(M−s),∣ξr⟩=exp⁡[r2(a†2−a2)]∣0⟩.(2)\lvert\Psi_{\mathrm{G}}\rangle= \lvert\xi_r\rangle^{\otimes s}\lvert0\rangle^{\otimes(M-s)}, \qquad\lvert\xi_r\rangle= \exp\left[\frac{r}{2}(a^{\dagger2}-a^2)\right]\lvert0\rangle. \tag*{(2)}

Given UU, η\eta, rr and ϵ>0\epsilon> 0, generate samples from a distribution QUQ_U with EU∼HaardTV(PU,QU)≤ϵ\mathbb{E}_{U\sim\mathrm{Haar}}d_{\mathrm{TV}}(P_U,Q_U) \le\epsilon, where PUP_U is the output distribution of this input under uniform loss with transmission η\eta. Our main result considers all squeezed input states, s=Ms = M.

An algorithm solves either problem efficiently if its running time per sample is polynomial in MM and 1/ϵ1/\epsilon. Unless stated otherwise, η\eta and rr are fixed as the system grows, so the mean numbers of detected photons, ηn\eta n and ηssinh⁡2r\eta s \sinh^2 r, grow in proportion to the number of sources. Running times count arithmetic operations, and Appendix D shows that polynomially many bits of precision suffice.

Previous results

Most efficient classical algorithms for lossy boson sampling require the transmission to decrease as the system grows. At fixed total variation error, they apply when the mean number of detected photons grows at most as the square root of the number of sources. For single-photon inputs, the lossy state is then close to an efficiently simulable classical state [13, 14]. For Gaussian inputs, the same scale appears for classical Gaussian approximations, whose bounds hold for every interferometer [15], and in the loss analyses of tensor network methods [16, 18]. A recent Gaussian reset method, also valid for every interferometer, goes beyond this square root regime and allows a mean detected photon number of order s2/3s^{2/3} for ss squeezed inputs [17].

Much less is known at inverse polynomial error. The Gaussian approximation and reset bounds then demand even stronger loss, and at the square root boundary the Gaussian tensor network analysis does not establish a cost polynomial in both system size and inverse error.

At a fixed transmission, interference truncation offers a different approach [21]. It approximates each output probability by keeping only interference among a limited number of photons, set by the transmission and the target error. The cost of evaluating this approximation grows as the system size raised to the truncation order, which is polynomial at fixed error but quasipolynomial at inverse polynomial error. Samples are then drawn with a Metropolis chain, for which no bound on the number of steps needed to reach a prescribed total variation error is given.

We obtained our results independently and became aware of the related preprint [22] after completing this work. That work establishes polynomial-time classical sampling for lossy Fock state boson sampling at any fixed survival probability in a dilute regime, with polynomial dependence on inverse error. In our notation, its full-output guarantee for kk survivors from nn input photons is proved under

M≥C0nk2,M≥CBk2ϵδ.M \ge C_0 n k^2,\qquad M \ge C_B \frac{k^2}{\epsilon\delta}.

where C0,CB>0C_0,C_B > 0 are universal constants, ϵ\epsilon is the total variation error, and δ\delta is the allowed failure probability over Haar random interferometers. At a fixed surviving fraction k/n∈(0,1)k/n \in(0,1), the first bound already imposes M=Ω(n3)M = \Omega(n^3). The second bound makes the total collision probability small. Our result for Fock state boson sampling covers the full output distribution for every M≥nM \ge n, including M=nM = n, with no additional condition on the relative scaling of mode and photon numbers. It includes all output collisions, even when they occur with substantial probability. Our Gaussian result further establishes efficient sampling with equal squeezing in all input modes.

Appendices F and G compare our results with these simulation methods and with known hardness results.

Main results

Efficient sampling at a fixed transmission

Both problems of Sec. II admit efficient classical samplers at every fixed transmission. For single-photon inputs, the result is as follows.

Theorem 1 (Efficient classical algorithm for lossy Fock state boson sampling). Fix a transmission η\eta. For every M≥nM \ge n and 0<ϵ≤1/20 < \epsilon\le1/2, there is a classical randomized algorithm for Problem 1 whose output distribution satisfies

EU∼Haar⁡dTV(PU,QU)≤ϵ.(3)\mathbb{E}_{U\sim\operatorname{Haar}} d_{\mathrm{TV}}(P_U,Q_U) \le\epsilon. \tag*{(3)}

Its worst case number of arithmetic operations per sample obeys

TF(M,n,ϵ)≤poly⁡η(M,n,1/ϵ).(4)T_{\mathrm{F}}(M,n,\epsilon) \le\operatorname{poly}_{\eta}(M,n,1/\epsilon). \tag*{(4)}

The polynomial’s degree and constants may depend on the fixed transmission. The sampler works with any number of vacuum inputs and generates the full distribution of detected photon numbers. It therefore applies while the mean detected photon number ηn\eta n increases in direct proportion to the number of sources.

For Gaussian inputs squeezed in every mode, the same result holds at every finite squeezing.

Theorem 2 (Efficient classical algorithm for lossy Gaussian boson sampling). Fix a transmission η\eta and a squeezing parameter r≥0r \ge0. For every M≥1M \ge1 and 0<ϵ≤1/20 < \epsilon\le1/2, there is a classical randomized algorithm for Problem 2 with s=Ms=M whose output distribution satisfies

EU∼Haar⁡TV⁡(PU,QU)≤ϵ.(5)\mathbb{E}_{U\sim\operatorname{Haar}}\operatorname{TV}(P_U,Q_U) \le\epsilon. \tag*{(5)}

Its worst case number of arithmetic operations per sample obeys

TG(M,ϵ)≤poly⁡r,η(M,1/ϵ).(6)T_{\mathrm{G}}(M,\epsilon) \le\operatorname{poly}_{r,\eta}(M,1/\epsilon). \tag*{(6)}

At fixed r>0r>0, the mean detected photon number ηMsinh⁡2r\eta M\sinh^2 r grows linearly with MM, as ηn\eta n does for single photons. The bound for a given rr also holds for every smaller squeezing parameter, so the squeezing may decrease with MM, as in weak-squeezing scalings with r→0r \to0. When only s<Ms<M inputs are squeezed, Appendix E extends the result under the sufficient condition ηcosh⁡(2r)<1\eta\cosh(2r)<1, uniformly in ss.

Both theorems bound the error on average over Haar random interferometers. A randomly drawn circuit therefore has a small error with high probability, although the algorithm cannot tell whether a given circuit does. By Markov’s inequality, running the sampler at ϵ=min⁡{1/2,M−(a+b)}\epsilon=\min\{1/2,M^{-(a+b)}\} for fixed a,b>0a,b>0 gives an error at most M−aM^{-a} with probability at least 1−M−b1-M^{-b} over the choice of UU, still in polynomial time. Because the circuit is drawn once and then held fixed, all samples come from the same distribution QUQ_U and carry the same error. The error of TT independent samples taken together is at most TT times this error. Running the sampler at an error smaller by a factor of TT therefore keeps polynomially many samples jointly accurate, still in polynomial time, as shown in Appendix A. § 0.5 outlines the proofs, which the appendices complete.

Consequences for computational complexity

Our results settle the regime of constant loss rate at the accuracy used in hardness arguments. For every fixed transmission, the samplers run in time polynomial in the system size and in 1/ϵ1/\epsilon, which is the notion of efficient approximate sampling used for ideal boson sampling [1]. In particular, the error may decrease as an inverse polynomial in the system size, measured by the photon number nn for single-photon inputs and by the mode number MM for Gaussian inputs. Choosing ϵ=n−a\epsilon=n^{-a} or ϵ=M−a\epsilon=M^{-a} with any fixed a>0a>0 makes 1/ϵ1/\epsilon polynomial in the system size, so the running time remains polynomial. Earlier rigorous samplers needed the transmission to vanish as the system grows [13, 14, 15, 17], and interference truncation becomes quasipolynomial at inverse polynomial error [21]. Our samplers extend efficient sampling to every constant loss rate. For Haar random interferometers, constant loss therefore leaves no asymptotic sampling advantage in either input family.

Hardness survives only when the loss rate vanishes quickly. Consider single-photon inputs with MM polynomial in nn and (1−η)n=O(log⁡n)(1-\eta)n=O(\log n). All nn photons then survive with probability ηn≥n−c\eta^n \ge n^{-c} for some constant cc, so keeping only the nn-photon outcomes turns a sampler for the lossy distribution with sufficiently small inverse polynomial error into an ideal sampler at polynomial overhead [10, 11]. The lossy problem is then as hard as ideal boson sampling under the same assumptions, and Appendix G gives the error and cost bounds of this reduction. The open range is thus confined to loss rates that vanish more slowly than (log⁡n)/n(\log n)/n. Our results are consistent with this hardness. The correlation cutoff required by our samplers grows as the transmission approaches one, and at inverse polynomial error it becomes proportional to nn when only a logarithmic number of photons is lost on average. Because the cost grows exponentially with the cutoff, our bound on the running time is then no longer polynomial. For Gaussian inputs, a hardness comparison must further match the squeezing scale and interferometer ensemble of the relevant hardness result [12, 23], and Appendix G treats these comparisons separately.

Implications for quantum advantage experiments

Hardness arguments for boson sampling take the interferometer from the Haar measure [1, 19], and several experiments test their devices against this assumption. Jiuzhang 1.0 and 2.0 compared their measured transformation matrices with Haar random statistics [3, 5], and a recent single-photon experiment implemented a unitary drawn from the Haar measure [2]. Theorems 1 and 2 apply to such experiments whenever their input states belong to the families treated there. In that case, adding photons and modes at a fixed transmission cannot establish an asymptotic sampling advantage, despite large photon counts, output collisions and multiphoton interference. Other large scale experiments use structured interferometers that are not Haar random, such as time domain loop networks [6] and hybrid spatiotemporal circuits [8], and our average case result does not directly apply to them.

Because the accuracy bound concerns the complete output distribution, it also holds after any processing applied in the same way to both outputs, such as recording only detector clicks or grouping output configurations into coarser classes. The probability that an output passes any given test therefore differs between the experiment and the classical sampler by at most the total variation distance. Our theorems nevertheless concern asymptotic scaling and do not by themselves show that any particular device can be spoofed. Spoofing a specific experiment would require an implementation that generates samples in a time comparable to that of the experiment, which polynomial bounds with possibly large degrees and constants do not ensure. It would also require an accuracy assessment for the actual circuit and physical noise model, because our bound holds on average over Haar random interferometers under uniform loss.

Sampling algorithms

Our samplers rest on one physical effect, the suppression of correlations among many photons by loss. Let NN be the total number of photons before loss. It equals nn for single-photon inputs and fluctuates over even values for Gaussian inputs. Each photon survives independently, so given NN the detected count kk is binomially distributed with NN trials and probability η\eta. For each detected count, the samplers keep only correlation orders up to a cutoff LL, evaluate the retained contributions efficiently, and convert them into samples by a rejection procedure with a bounded number of trials. The principle behind the method is that, with loss, the truncation error decays exponentially in LL, so the required cutoff grows only logarithmically with the number of detected photons (Figure 1).

Suppression of high-order correlations

In Figure 1a, the loss acts in front of the detectors. Because uniform loss commutes with a passive interferometer, the same loss can be moved in front of the interferometer without changing the output distribution. For single-photon inputs, an event with kk surviving photons then amounts to an ideal experiment in which kk photons enter a uniformly random subset of the nn occupied input modes. Because the lost photons are not observed, the detection probabilities average these ideal experiments over all subsets, although each of them still shows full quantum interference.

For given NN and kk, let pU(x)p_U(x) be the probability of the output configuration x=(x1,…,xM)x = (x_1,\ldots,x_M), which lists the photon number in each output mode, with x1+⋯+xM=kx_1+\cdots+x_M = k. There are DM,k=(M+k−1k)D_{M,k} = \binom{M+k-1}{k} such configurations, and the rescaled probability FU(x)=DM,kpU(x)F_U(x) = D_{M,k}p_U(x) has the uniform average DM,k−1∑xFU(x)=∑xpU(x)=1D_{M,k}^{-1}\sum_x F_U(x) = \sum_x p_U(x) = 1. We expand it into orthogonal correlation orders,

References

  1. [1]S. Aaronson and A. Arkhipov, The Computational Complexity of Linear Optics, Theory Comput. 9, 143 (2013).
  2. [2]N. Maring et al., A versatile single-photon-based quantum computing platform, Nat. Photonics 18, 603 (2024).
  3. [3]H.-S. Zhong et al., Quantum computational advantage using photons, Science 370, 1460 (2020).DOI
  4. [4]J. M. Arrazola et al., Quantum circuits with many photons on a programmable nanophotonic chip, Nature 591, 54 (2021).
  5. [5]H.-S. Zhong et al., Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light, Phys. Rev. Lett. 127, 180502 (2021).
  6. [6]L. S. Madsen et al., Quantum computational advantage with a programmable photonic processor, Nature 606, 75 (2022).DOI
  7. [7]Y.-H. Deng et al., Gaussian Boson Sampling with Pseudo-Photon-Number-Resolving Detectors and Quantum Computational Advantage, Phys. Rev. Lett. 131, 150601 (2023).DOI
  8. [8]H.-L. Liu et al., Gaussian boson sampling with 1,024 squeezed states in 8,176 modes, Nature 653, 687 (2026).DOI
  9. [9]S. Yu et al., Extensible universal photonic quantum computing with nonlinearity, Nat. Photonics 20, 1166 (2026).DOI
  10. [10]S. Aaronson and D. J. Brod, BosonSampling with lost photons, Phys. Rev. A 93, 012335 (2016).DOI
  11. [11]B. Go, C. Oh, and H. Jeong, Quantum Computational Advantage of Noisy Boson Sampling with Partially Distinguishable Photons, PRX Quantum 6, 030362 (2025).DOI
  12. [12]B. Go, C. Oh, and H. Jeong, Sufficient conditions for hardness of lossy Gaussian boson sampling (2025), arXiv:2511.07853.arxiv.org/abs/2511.07853
  13. [13]M. Oszmaniec and D. J. Brod, Classical simulation of photonic linear optics with lost particles, New J. Phys. 20, 092002 (2018).DOI
  14. [14]R. García-Patrón, J. J. Renema, and V. Sveshnikov, Simulating boson sampling in lossy architectures, Quantum 3, 169 (2019).
  15. [15]H. Qi, D. J. Brod, N. Quesada, and R. García-Patrón, Regimes of Classical Simulability for Noisy Gaussian Boson Sampling, Phys. Rev. Lett. 124, 100502 (2020).DOI
  16. [16]C. Oh, M. Liu, Y. Alexeev, B. Fefferman, and L. Jiang, Classical algorithm for simulating experimental Gaussian boson sampling, Nat. Phys. 20, 1461 (2024).DOI
  17. [17]Y. Lim, Classical Simulation of Lossy Gaussian Boson Sampling beyond Square-Root Regime (2026), arXiv:2610.06526.arxiv.org/abs/2610.06526
  18. [18]S. Park and C. Oh, Matrix product state approach to lossy boson sampling and noisy IQP sampling (2025), arXiv:2510.24137.arxiv.org/abs/2510.24137
  19. [19]C. S. Hamilton et al., Gaussian Boson Sampling, Phys. Rev. Lett. 119, 170501 (2017).
  20. [20]A. W. Young et al., An atomic boson sampler, Nature 629, 311 (2024).DOI
  21. [21]J. J. Renema, V. Shchesnovich, and R. García-Patrón, Classical simulatibility of noisy boson sampling (2018), arXiv:1809.01953.arxiv.org/abs/1809.01953
  22. [22]B. Go and H. Jeong, Polynomial-Time Classical Simulation of BosonSampling under Any Constant-Fraction Loss (2026), arXiv:2610.27065.arxiv.org/abs/2610.27065
  23. [23]A. Bouland et al., Complexity-Theoretic Foundations of BosonSampling with a Linear Number of Modes, Phys. Rev. X 16, 021059 (2026).arxiv.org/abs/2312.00286
  24. [24]J. S. Ivan, K. K. Sabapathy, and R. Simon, Operator-sum representation for bosonic Gaussian channels, Phys. Rev. A 84, 042311 (2011).DOI
  25. [25]M. Arienzo, D. Grinko, M. Kliesch, and M. Heinrich, Bosonic Randomized Benchmarking with Passive Transformations, PRX Quantum 6, 020305 (2025).
  26. [26]R. Dou, H. Zhan, S. Wu, L. Zhang, and P. Yao, Classical Algorithms for Function Computation in Gaussian Boson Sampling (2026), arXiv:2609.38882.arxiv.org/abs/2609.38882
  27. [27]N. Alon, R. Yuster, and U. Zwick, Color-coding, J. ACM 42, 844 (1995).
  28. [28]M. P. Tuite, Some generalizations of the MacMahon Master Theorem, J. Combin. Theory Ser. A 120, 92 (2013).
  29. [29]E. Fitzke, F. Niederschuh, and T. Walther, Simulating the photon statistics of multimode Gaussian states by automatic differentiation of generating functions, APL Photonics 8, 026106 (2023).DOI
  30. [30]L. Devroye, Non-Uniform Random Variate Generation (Springer-Verlag, New York, 1986).
  31. [31]N. Quesada and J. M. Arrazola, Exact simulation of Gaussian boson sampling in polynomial space and exponential time, Phys. Rev. Research 2, 023005 (2020).
  32. [32]V. Bargmann, On a Hilbert space of analytic functions and an associated integral transform part I, Commun. Pure Appl. Math. 14, 187 (1961).pubmed.ncbi.nlm.nih.gov/16590920
  33. [33]T. C. John and K. R. Parthasarathy, A common parametrization for finite mode Gaussian states, their symmetries, and associated contractions with some applications, J. Math. Phys. 62, 022102 (2021).
  34. [34]A. Björklund, Counting Perfect Matchings as Fast as Ryser, in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SIAM, Philadelphia, 2012) pp. 914–921.
  35. [35]W. Hoeffding, Probability Inequalities for Sums of Bounded Random Variables, J. Am. Stat. Assoc. 58, 13 (1963).
  36. [36]A. Deshpande et al., Quantum computational advantage via high-dimensional Gaussian boson sampling, Sci. Adv. 8, eabi7894 (2022).DOI

Paper details

vlnc:W_qxjgwcz2
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

GPT-6, Claude Fable 5.1 (bare)

View statement
Looking for related papers…
Contents