Classical Algorithms for Function Computation in Gaussian Boson Sampling
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.
Related
- Encoding universal quantum computation into quantized Berry phases: Hardness results and classical algorithms
- Classical Simulation of Lossy Gaussian Boson Sampling beyond Square-Root Regime
- A Topology-Aware Quantum-Classical Framework for Multi-Target Active Debris Removal using Gaussian Boson Sampling
- Efficient quantum Gibbs sampling of stabilizer codes using hybrid computation
- HTM: A Hybrid Classical-Quantum Computation Model
BibTeX
@misc{dou2026classical,
title = {{Classical Algorithms for Function Computation in Gaussian Boson Sampling}},
author = {Ruoting Dou and Hao Zhan and Shengjun Wu and Lijian Zhang and Penghui Yao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.38882},
eprint = {2609.38882},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38882},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Classical Algorithms for Function Computation in Gaussian Boson Sampling
AU - Ruoting Dou
AU - Hao Zhan
AU - Shengjun Wu
AU - Lijian Zhang
AU - Penghui Yao
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.38882
UR - https://arxiv.org/abs/2609.38882
AB - 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.
ER -