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:2609.35447

Efficient classical algorithm for estimating linear statistics of Boson Sampling

Benoit Seron, Hugo Thomas, Eduardo Araujo, Alex Arkhipov, Changhun Oh, Leonardo Novo

quant-phSubmitted Sep 28, 2026• Announced Sep 29, 2026• 3 citations
arXivHTMLPDF

Abstract

Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.

AI Summary

The paper asks which experimentally accessible coarse-grainings of Boson Sampling distributions admit efficient classical estimation. It studies linear statistics $f_{\boldsymbol\omega}(\boldsymbol s)=\boldsymbol\omega\cdot\boldsymbol s$, including probabilities that this weighted occupation sum lies in a specified interval. For Fock inputs, a randomized classical algorithm estimates the cumulative probability $\Pr[f_{\boldsymbol\omega}(\boldsymbol s)\leq x]$ to additive error $\varepsilon$, with failure probability at most $\delta$, in expected time $\operatorname{poly}(m,\log N,\varepsilon^{-1},\log\delta^{-1})$, where $N>n\max_i\omega_i$. Thus exponentially large weights remain tractable when their bit lengths are polynomial. The construction expresses the characteristic function as a linear-optical return amplitude for $U^\dagger e^{i\theta\Omega}U$, uses existing additive-amplitude estimators, and applies Fourier importance sampling with estimator magnitude $O(\log N)$. The outer estimator requires $O(\varepsilon^{-2}\log^2N\log\delta^{-1})$ samples. Applications include classical estimation of lexicographically binned probabilities underlying a proposed Boson Sampling one-way function, and estimation of a specified mode-group occupation probability in $O(m^2/\varepsilon^4)$ time, suppressing confidence factors. The framework also covers suitable Gaussian and other product inputs, photon loss, and partial distinguishability. The guarantees concern additive estimation for specified statistics, not full-distribution sampling or a sampler passing tests chosen afterward. Shuffled or collision-dependent binning lies outside the method. Quadratic statistics are related to amplitudes of circuits with one layer of Kerr/cross-Kerr interactions; efficient inverse-polynomial additive estimation in that setting remains open.

No sign of AI-generated text

Error found: The explicit runtime at the end of the main proof is missing two powers of log N under its stated nested-estimation procedure, although the polynomial-time conclusion remains correct. The printed Gaussian Boson Sampling characteristic-function formula uses the wrong Fourier phase and must be corrected before it can supply the coefficients required by the estimator. Efficient additive estimation of bin probabilities does not guarantee efficient identification of the exact most-probable bin without a suitable probability-gap promise, so the paper's unqualified evaluation language needs narrowing.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
10 pages, 3 figures, 8 pages of appendix

Related papers

Classical Algorithms for Function Computation in Gaussian Boson Sampling

Ruoting Dou, Hao Zhan, Shengjun Wu +2 more

Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics. Many proposed GBS applications instead target function computation by applying functions to mode-resolved photon-number outcomes---a natural form of experimental postprocessing that produces classical outputs. Sampling hardness alone, however, does not determine the complexity of these tasks. By analyzing the irreducible decomposition of fixed-photon-number operator spaces, we prove that the expectation value of every such function in the average case over passive linear-optical networks can be classically evaluated for inputs with finite squeezing strength. We also provide a classical algorithm that estimates this value to inverse-polynomial additive error. The result provides new theoretical tools for analyzing linear-optical quantum systems, helps clarify the origin of current GBS hardness evidence, and inspires new applications of GBS with genuine quantum advantages.

quant-pharXiv:2609.38882•Oct 1, 2026•1 citation

Classical Algorithms for Estimating Expectation Values in Linear Optical Circuits

Anonymous, Changhun Oh

We present a classical algorithm for approximating the expectation values of observables in linear optical circuits with arbitrary product input states, achieving additive-error accuracy. This result indicates that current applications of photonic systems aimed at demonstrating practical quantum advantage through expectation value estimation, such as photonic variational algorithms, may face challenges in attaining the computational advantage. It also implies the output probabilities of boson sampling with arbitrary product input states can be efficiently approximated by our method, so that boson sampling becomes efficiently simulable when its output probability distribution is polynomially sparse. We also develop an efficient classical algorithm for estimating transition amplitudes of arbitrary product states in linear optical circuits. This provides additive-error approximation algorithms for matrix functions associated with linear optical circuits, such as the (loop-)Hafnian, which are of independent interest. As an application, it solves the generalized molecular vibronic spectra problem [C. Oh et al., Nat. Phys. 20, 225 (2024)10.1038/s41567-023-02308-9], previously suggested as a candidate for practical quantum advantage. Finally, we extend our framework to near-Clifford circuits, enabling classical approximation of their expectation values.

arXiv:2502.12882•Physical Review Letters•Aug 13, 2026•18 citations

Non-linear Boson Sampling

Nicolò Spagnolo, Daniel J. Brod, Ernesto F. Galvão +1 more

Abstract Boson Sampling is a task that is conjectured to be computationally hard for a classical computer, but which can be efficiently solved by linear-optical interferometers with Fock state inputs. Significant advances have been reported in the last few years, with demonstrations of small- and medium-scale devices, as well as implementations of variants such as Gaussian Boson Sampling. Besides the relevance of this class of computational models in the quest for unambiguous experimental demonstrations of quantum advantage, recent results have also proposed the first applications for hybrid quantum computing. Here, we introduce the adoption of non-linear photon–photon interactions in the Boson Sampling framework, and analyze the enhancement in complexity via an explicit linear-optical simulation scheme. By extending the computational expressivity of Boson Sampling, the introduction of non-linearities promises to disclose novel functionalities for this class of quantum devices. Hence, our results are expected to lead to new applications of near-term, restricted photonic quantum computers.

arXiv:2110.13788•npj Quantum Information•Jan 9, 2023•33 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

Approximating outcome probabilities of linear optical circuits

Youngrong Lim, Changhun Oh

Abstract Quasiprobability representations are important tools for analyzing a quantum system, such as a quantum state or a quantum circuit. In this work, we propose classical algorithms specialized for approximating outcome probabilities of a linear optical circuit using quasiprobability distributions. Notably, we can reduce the negativity bound of a circuit from exponential to at most polynomial for specific cases by modulating the shapes of quasiprobability distributions thanks to the symmetry of the linear optical transformation in the phase space. Consequently, our scheme provides an efficient estimation of outcome probabilities within an additive-error whose precision depends on the classicality of the input state. When the classicality is high enough, we reach a polynomial-time estimation algorithm of a probability within a multiplicative-error by an efficient sampling from a log-concave function. By choosing appropriate input states and measurements, our results provide plenty of quantum-inspired classical algorithms for approximating various matrix functions beating best-known results. Moreover, we give sufficient conditions for the classical simulability of Gaussian Boson sampling using our approximating algorithm for any (marginal) outcome probability under the poly-sparse condition.

arXiv:2211.07184•npj Quantum Information•Dec 16, 2023•8 citations

Distinguishing noisy boson sampling from classical simulations

V. S. Shchesnovich

Giving a convincing experimental evidence of the quantum supremacy over classical simulations is a challenging goal. Noise is considered to be the main problem in such a demonstration, hence it is urgent to understand the effect of noise. Recently found classical algorithms can efficiently approximate, to any small error, the output of boson sampling with finite-amplitude noise. In this work it is shown analytically and confirmed by numerical simulations that one can efficiently distinguish the output distribution of such a noisy boson sampling from the approximations accounting for low-order quantum multiboson interferences, what includes the mentioned classical algorithms. The number of samples required to tell apart the quantum and classical output distributions is strongly affected by the previously unexplored parameter: density of bosons, i.e., the ratio of total number of interfering bosons to number of input ports of interferometer. Such critical dependence is strikingly reminiscent of the quantum-to-classical transition in systems of identical particles, which sets in when the system size scales up while density of particles vanishes.

arXiv:1905.11458•Quantum•Mar 29, 2021•22 citations
Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.
The paper asks which experimentally accessible coarse-grainings of Boson Sampling distributions admit efficient classical estimation. It studies linear statistics fω(s)=ω⋅sf_{\boldsymbol\omega}(\boldsymbol s)=\boldsymbol\omega\cdot\boldsymbol sfω​(s)=ω⋅s, including probabilities that this weighted occupation sum lies in a specified interval.
For Fock inputs, a randomized classical algorithm estimates the cumulative probability Pr⁡[fω(s)≤x]\Pr[f_{\boldsymbol\omega}(\boldsymbol s)\leq x]Pr[fω​(s)≤x] to additive error ε\varepsilonε, with failure probability at most δ\deltaδ, in expected time poly⁡(m,log⁡N,ε−1,log⁡δ−1)\operatorname{poly}(m,\log N,\varepsilon^{-1},\log\delta^{-1})poly(m,logN,ε−1,logδ−1), where N>nmax⁡iωiN>n\max_i\omega_iN>nmaxi​ωi​. Thus exponentially large weights remain tractable when their bit lengths are polynomial. The construction expresses the characteristic function as a linear-optical return amplitude for U†eiθΩUU^\dagger e^{i\theta\Omega}UU†eiθΩU, uses existing additive-amplitude estimators, and applies Fourier importance sampling with estimator magnitude O(log⁡N)O(\log N)O(logN). The outer estimator requires O(ε−2log⁡2Nlog⁡δ−1)O(\varepsilon^{-2}\log^2N\log\delta^{-1})O(ε−2log2Nlogδ−1) samples.
Applications include classical estimation of lexicographically binned probabilities underlying a proposed Boson Sampling one-way function, and estimation of a specified mode-group occupation probability in O(m2/ε4)O(m^2/\varepsilon^4)O(m2/ε4) time, suppressing confidence factors. The framework also covers suitable Gaussian and other product inputs, photon loss, and partial distinguishability.
The guarantees concern additive estimation for specified statistics, not full-distribution sampling or a sampler passing tests chosen afterward. Shuffled or collision-dependent binning lies outside the method. Quadratic statistics are related to amplitudes of circuits with one layer of Kerr/cross-Kerr interactions; efficient inverse-polynomial additive estimation in that setting remains open.
Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics. Many proposed GBS applications instead target function computation by applying functions to mode-resolved photon-number outcomes---a natural form of experimental postprocessing that produces classical outputs. Sampling hardness alone, however, does not determine the complexity of these tasks. By analyzing the irreducible decomposition of fixed-photon-number operator spaces, we prove that the expectation value of every such function in the average case over passive linear-optical networks can be classically evaluated for inputs with finite squeezing strength. We also provide a classical algorithm that estimates this value to inverse-polynomial additive error. The result provides new theoretical tools for analyzing linear-optical quantum systems, helps clarify the origin of current GBS hardness evidence, and inspires new applications of GBS with genuine quantum advantages.
We present a classical algorithm for approximating the expectation values of observables in linear optical circuits with arbitrary product input states, achieving additive-error accuracy. This result indicates that current applications of photonic systems aimed at demonstrating practical quantum advantage through expectation value estimation, such as photonic variational algorithms, may face challenges in attaining the computational advantage. It also implies the output probabilities of boson sampling with arbitrary product input states can be efficiently approximated by our method, so that boson sampling becomes efficiently simulable when its output probability distribution is polynomially sparse. We also develop an efficient classical algorithm for estimating transition amplitudes of arbitrary product states in linear optical circuits. This provides additive-error approximation algorithms for matrix functions associated with linear optical circuits, such as the (loop-)Hafnian, which are of independent interest. As an application, it solves the generalized molecular vibronic spectra problem [C. Oh et al., Nat. Phys. 20, 225 (2024)10.1038/s41567-023-02308-9], previously suggested as a candidate for practical quantum advantage. Finally, we extend our framework to near-Clifford circuits, enabling classical approximation of their expectation values.
Abstract Boson Sampling is a task that is conjectured to be computationally hard for a classical computer, but which can be efficiently solved by linear-optical interferometers with Fock state inputs. Significant advances have been reported in the last few years, with demonstrations of small- and medium-scale devices, as well as implementations of variants such as Gaussian Boson Sampling. Besides the relevance of this class of computational models in the quest for unambiguous experimental demonstrations of quantum advantage, recent results have also proposed the first applications for hybrid quantum computing. Here, we introduce the adoption of non-linear photon–photon interactions in the Boson Sampling framework, and analyze the enhancement in complexity via an explicit linear-optical simulation scheme. By extending the computational expressivity of Boson Sampling, the introduction of non-linearities promises to disclose novel functionalities for this class of quantum devices. Hence, our results are expected to lead to new applications of near-term, restricted photonic quantum computers.
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 Quasiprobability representations are important tools for analyzing a quantum system, such as a quantum state or a quantum circuit. In this work, we propose classical algorithms specialized for approximating outcome probabilities of a linear optical circuit using quasiprobability distributions. Notably, we can reduce the negativity bound of a circuit from exponential to at most polynomial for specific cases by modulating the shapes of quasiprobability distributions thanks to the symmetry of the linear optical transformation in the phase space. Consequently, our scheme provides an efficient estimation of outcome probabilities within an additive-error whose precision depends on the classicality of the input state. When the classicality is high enough, we reach a polynomial-time estimation algorithm of a probability within a multiplicative-error by an efficient sampling from a log-concave function. By choosing appropriate input states and measurements, our results provide plenty of quantum-inspired classical algorithms for approximating various matrix functions beating best-known results. Moreover, we give sufficient conditions for the classical simulability of Gaussian Boson sampling using our approximating algorithm for any (marginal) outcome probability under the poly-sparse condition.
Giving a convincing experimental evidence of the quantum supremacy over classical simulations is a challenging goal. Noise is considered to be the main problem in such a demonstration, hence it is urgent to understand the effect of noise. Recently found classical algorithms can efficiently approximate, to any small error, the output of boson sampling with finite-amplitude noise. In this work it is shown analytically and confirmed by numerical simulations that one can efficiently distinguish the output distribution of such a noisy boson sampling from the approximations accounting for low-order quantum multiboson interferences, what includes the mentioned classical algorithms. The number of samples required to tell apart the quantum and classical output distributions is strongly affected by the previously unexplored parameter: density of bosons, i.e., the ratio of total number of interfering bosons to number of input ports of interferometer. Such critical dependence is strikingly reminiscent of the quantum-to-classical transition in systems of identical particles, which sets in when the system size scales up while density of particles vanishes.