arXiv:2609.38882
Classical Algorithms for Function Computation in Gaussian Boson Sampling
Ruoting Dou, Hao Zhan, Shengjun Wu, Lijian Zhang, Penghui Yao
Abstract
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.
AI Summary
The paper asks whether hardness of Gaussian boson sampling (GBS) implies hardness of estimating averages of efficiently computable functions of photon-count outcomes. It studies $\mu_f(U)=\mathbb E_{P_U}[f(\mathbf s)]$ for ideal, lossless GBS with squeezing bounded by a constant $r_{\max}$ independent of mode number $m$. For functions independent of $U$, with known polynomial variance bounds and suitably bounded means, the main theorem gives a randomized classical polynomial-time estimator achieving additive error $m^{-c}$ with probability at least $1-m^{-\kappa}$, for any fixed $c,\kappa>0$. Probability is joint over Haar-random interferometers and algorithmic randomness. Function values need not be bounded, although the main-text derivation treats $|f|\le1$ and delegates the extension to supplemental material. The method decomposes fixed-photon-number operator spaces into irreducible correlation-order sectors. Schur orthogonality relates Haar-averaged truncation error to input-state weights in these sectors. For bounded functions, retaining at most $O(m)$ photon pairs and correlation orders through fixed $K$ yields root-mean-square error $O(m^{-K/2-1/4})+m^{-B}$. Low-order reduced density matrices and Monte Carlo over uniformly sampled photon patterns provide an efficient estimator. The guarantee concerns each prescribed function, not simultaneous approximation of all functions or classical sampling: the estimator uses signed weights. Haar randomness and independence of $f$ from $U$ are essential assumptions. Structured worst-case networks, network-dependent postprocessing, altered input preparation, and optimization over repeated samples are outside the stated result.
Error found: The abstract omits the essential restriction that the outcome function be independent of the interferometer U, so it can be read as covering network-dependent scoring functions that the theorem explicitly excludes. The abstract's universal wording does not state the efficient-evaluation and known variance/mean-bound assumptions imposed by the theorem.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 35 pages, Includes Supplemental Material