⚛️ quantum physics

Classical Algorithms for Function Computation in Gaussian Boson Sampling

This paper proves that the expectation values of functions applied to photon-number outcomes in Gaussian boson sampling can be classically evaluated for finite squeezing strengths by analyzing the irreducible decomposition of fixed-photon-number operator spaces, thereby providing a classical algorithm and new theoretical insights into the complexity of such tasks.

Original authors: Ruoting Dou, Hao Zhan, Shengjun Wu, Lijian Zhang, Penghui Yao

Published 2026-10-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ruoting Dou, Hao Zhan, Shengjun Wu, Lijian Zhang, Penghui Yao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the current era of quantum computing, researchers are racing to build machines that can solve problems beyond the reach of even the most powerful supercomputers. One promising path involves using light to perform calculations. Instead of electrons moving through silicon chips, these machines use streams of photons, or particles of light, traveling through a network of mirrors and beam splitters. A specific type of experiment called Gaussian boson sampling has emerged as a leading candidate for demonstrating this advantage. In these experiments, researchers squeeze light into a special state and send it through a complex optical circuit. The machine then counts how many photons arrive at each exit. The pattern of these counts is incredibly difficult to predict or reproduce using classical computers, which is why it is seen as a potential proof of quantum supremacy.

However, the ultimate goal of quantum computing is not just to generate random numbers that are hard to predict, but to perform useful tasks. Many proposed applications for these light-based machines involve taking the random photon counts and using them to calculate specific values, such as chemical properties of molecules or features of complex networks. This process is known as function computation. A critical question has remained unanswered: if the goal is to calculate a specific average value from these random outcomes, rather than just sampling the full distribution of possibilities, does the quantum machine still hold an advantage? Or can a classical computer, running on standard silicon, do the same job just as well?

A team of researchers from Nanjing University and the Hefei National Laboratory has now answered this question with a definitive theoretical result. They have developed a new classical algorithm that can efficiently estimate the average value of almost any function applied to the outcomes of a Gaussian boson sampling experiment. Their work shows that for the standard setup used in current experiments, where the light is squeezed to a finite strength and the network of mirrors is chosen randomly, a classical computer can calculate the expected result with high precision. This finding does not mean that quantum computers are useless for these tasks, but rather that the specific advantage of quantum mechanics in this context is more limited than previously hoped. The quantum speedup relies heavily on the difficulty of sampling the entire distribution of outcomes; once the goal shifts to calculating a specific average, the barrier to classical simulation collapses.

The researchers arrived at this conclusion by breaking down the complex mathematics of the light interactions into simpler layers. They analyzed the system by looking at how many photons are present in total and how those photons are correlated with one another. They discovered that in a randomly arranged network, the complex, high-order correlations between many photons become so weak that they can be safely ignored for the purpose of calculating averages. The significant information is contained in the lower-order interactions, which are much easier to compute. By focusing only on these manageable parts and mathematically proving that the ignored parts contribute negligibly to the final average, they constructed a method that runs in polynomial time. This means the time required for the calculation grows at a manageable rate as the system gets larger, rather than exploding exponentially as it would for a full simulation.

The study also clarifies exactly where the quantum advantage lies. The authors identified a specific boundary of resources required for a task to remain hard for classical computers. To maintain the difficulty, an experiment needs three things simultaneously: squeezed light inputs, detectors that can count individual photons, and the requirement to sample the full distribution of outcomes. If any one of these is removed—for instance, if the goal is only to estimate an average value rather than generate the full set of random patterns—the task becomes easy for a classical computer. This distinction is crucial for the future of the field. It suggests that while Gaussian boson sampling is a powerful tool for proving that quantum machines can do things classical ones cannot, its utility for practical applications like drug discovery or graph analysis may require new approaches that go beyond simple function averaging.

The researchers' work provides a new set of theoretical tools for understanding linear-optical quantum systems. By proving that the average-case behavior of these systems can be simulated classically, they have helped clarify the origin of the current evidence for quantum hardness. This evidence was previously based on the difficulty of sampling the full output, but this new analysis shows that the hardness does not automatically extend to computing specific functions derived from those outputs. The result does not rule out the possibility of quantum advantage in all scenarios; for example, if the function being calculated depends on the specific arrangement of the optical network in a complex way, or if the squeezing strength is allowed to grow without limit, the classical algorithm might not apply. However, for the standard, finite-strength setups used in today's experiments, the path to a classical solution is now clear.

This finding serves as a guide for future research and application development. It encourages scientists to look for new types of problems where the quantum nature of the light can provide a genuine advantage that cannot be replicated by classical post-processing. The paper suggests that the most promising applications will likely involve tasks that require the full complexity of the quantum distribution, rather than just a summary statistic. By drawing a clear line between what is hard and what is easy, the researchers have helped the community focus its efforts on the areas where quantum machines are most likely to deliver on their promise. The work stands as a rigorous proof that, under the conditions of current experiments, the dream of using these light-based systems to simply calculate averages is within the reach of classical computers, reshaping the roadmap for the next generation of quantum applications.

Technical Summary: Classical Algorithms for Function Computation in Gaussian Boson Sampling

Problem Statement
Gaussian Boson Sampling (GBS) has emerged as a leading candidate for demonstrating quantum computational advantage, primarily through the hardness of sampling from the full output distribution of photon-number patterns generated by squeezed-vacuum inputs passing through passive linear-optical networks. While the sampling problem itself is believed to be classically hard, many proposed applications of GBS do not aim to reproduce the full distribution but rather to compute specific functions of the measurement outcomes (e.g., vibronic spectra, graph kernels, or clique weights). These tasks involve classical postprocessing of mode-resolved photon-number resolving (PNR) outcomes to estimate expectation values of specific observables.

The central question addressed is whether the classical hardness of sampling GBS distributions necessarily implies a quantum advantage for these function-computation tasks. Specifically, can a classical algorithm efficiently estimate the expectation value of a function $f(s)$ over the GBS output distribution, even if sampling the distribution itself remains hard? Previous work established classical simulability for specific cases (e.g., zero-temperature harmonic instances or circuits with adaptive measurements), but a general result for arbitrary polynomial-time evaluable functions over Haar-random networks was lacking.

Methodology
The authors develop an operational framework for analyzing GBS function computation by decomposing the problem into fixed-photon-number sectors and further into correlation orders. The core technical approach involves:

Operator-Space Decomposition: The space of operators on the $n$ -photon sector, $\mathcal{B}(\mathcal{H}_{m,n})$ , is decomposed into irreducible submodules $V_{n,k}$ under the action of the unitary group $U(m)$ . The index $k$ represents the "correlation order," corresponding to normally ordered monomials containing $k$ creation-annihilation pairs.
Hahn Polynomial Correspondence: For observables diagonal in the Fock basis (which correspond to outcome functions), the components in the operator space decomposition map directly to orthogonal projections onto multivariate Hahn polynomial subspaces. This allows the expectation value $\mu_f(U)$ to be expressed as a sum of contributions from different correlation orders.
Haar-Average Analysis: By assuming the linear-optical network $U$ is drawn from the Haar measure, the authors utilize Schur orthogonality to show that contributions from different correlation orders are uncorrelated. Crucially, they prove that for inputs with finite squeezing strength (where the squeezing parameter $r_j$ is bounded independently of the number of modes $m$ ), the weight of high-order correlation components decays polynomially with $m$ .
Truncation and Estimation: The expectation value can be approximated by truncating the sum to a constant correlation order $K$ $K$ . The error introduced by this truncation is shown to be inverse-polynomial in $m$ $m$ with high probability. The authors construct a classical algorithm that:
- Truncates the photon-pair number $N$ and the correlation order $k$ .
- Computes the reduced density matrices for the retained sectors.
- Uses Monte Carlo sampling over the uniform measure of photon-number patterns to estimate the truncated mean, leveraging the fact that the diagonal weights can be reconstructed from low-order reduced states and permanents of small matrices.

Key Contributions and Results
The paper establishes the following main results:

Theorem 1 (Main Result): For the GBS model with $m$ modes, finite squeezing strength, and any outcome function $f$ that is polynomial-time evaluable provided that known polynomial bounds on its mean and variance (independent of $U$ ) are supplied, there exists a randomized classical polynomial-time algorithm. This algorithm estimates the expectation value $\mu_f(U)$ to within an inverse-polynomial additive error ( $m^{-c}$ ) with high probability ( $1 - m^{-\kappa}$ ) over the choice of a Haar-random network $U$ . For general functions lacking these explicit bounds, the authors provide a phase-reconstruction extension that estimates the mean by evaluating a polynomial-size family of bounded characteristic functions.
Resource Boundary Identification: The work delineates the precise resources required for classical hardness in GBS. As summarized in Table I of the paper, the evidence for classical hardness relies jointly on three ingredients:
1. Squeezed inputs.
2. Mode-resolved photon detection (PNR or threshold).
3. Sampling from the full output distribution.
  The paper demonstrates that if the goal is merely function computation (estimating an average) rather than full distribution sampling, the task becomes classically efficient, provided the squeezing is finite and the function satisfies the required bounds (or the phase-reconstruction extension is applicable).
Algorithm Construction: The authors provide a concrete classical algorithm that estimates the truncated mean. The algorithm avoids the exponential cost of calculating full Hafnians by working with reduced density operators and low-order permanents, combined with Monte Carlo sampling over the pattern space.

Significance and Claims
The paper claims to provide new theoretical tools for analyzing linear-optical quantum systems by clarifying the origin of current GBS hardness evidence. Specifically, it argues that the classical hardness of GBS is tied to the difficulty of reproducing the entire probability distribution, not necessarily to the difficulty of computing specific statistical averages of the outcomes.

The authors state that their result helps clarify the boundary between tasks that offer genuine quantum advantages and those that can be efficiently simulated classically. They emphasize that their findings do not invalidate the sampling hardness of GBS but rather refine the understanding of where quantum advantage lies: in the full distribution sampling task, not necessarily in the function-computation tasks currently proposed for GBS applications (such as molecular spectroscopy or graph problems), unless those specific applications rely on features outside the scope of the theorem (e.g., $U$ -dependent postprocessing, worst-case networks, or functions lacking the required polynomial bounds on their moments).

The work suggests that future applications of GBS seeking genuine quantum advantages must either target the full distribution sampling problem or identify function-computation tasks that violate the assumptions of the theorem (e.g., by using unbounded squeezing, networks that are not Haar-random, or functions without known polynomial bounds on their moments). The authors note that their results extend to other sampling algorithms with different inputs (e.g., single-photon inputs) in separate work, but within this paper, the focus remains strictly on the GBS function-computation model.

Technical Summary: Classical Algorithms for Function Computation in Gaussian Boson Sampling

More like this