arXiv · Sep 30, 2026
Classical Algorithms for Function Computation in Gaussian Boson Sampling
By Ruoting Dou, Hao Zhan, Shengjun Wu et al.
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.