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