⚛️ quantum physics

Efficient classical algorithm for estimating linear statistics of Boson Sampling

This paper presents an efficient classical algorithm for approximating linear statistics of Boson Sampling distributions across various input states, thereby unifying recent quantum-inspired simulation results and demonstrating the classical evaluability of certain proposed one-way functions while leaving non-linear statistics as an open challenge.

Original authors: Benoit Seron, Hugo Thomas, Eduardo Araujo, Alex Arkhipov, Changhun Oh, Leonardo Novo

Published 2026-09-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Benoit Seron, Hugo Thomas, Eduardo Araujo, Alex Arkhipov, Changhun Oh, Leonardo Novo

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 quest to prove that quantum computers can do things impossible for classical machines, scientists have turned to a specific type of experiment involving light. Imagine a complex maze made of mirrors and beam splitters, where individual particles of light, called photons, are sent in one end and emerge from the other. The path each photon takes is not fixed; instead, the laws of quantum mechanics dictate that the photons explore all possible routes simultaneously, interfering with one another like ripples on a pond. When the photons hit detectors at the exit, they land in specific patterns. The challenge is that the number of possible patterns is so vast that it grows exponentially with the number of photons and paths. For a large enough system, calculating the exact probability of any single pattern would take a supercomputer longer than the age of the universe. This difficulty is the foundation of a task known as Boson Sampling, a leading candidate for demonstrating "quantum advantage," where a quantum device outperforms any classical computer.

However, a major hurdle remains: while these quantum devices can produce these complex patterns, it is often unclear what useful work they are actually doing. To make the results meaningful, researchers often group the countless possible outcomes into broader categories, a process called coarse-graining. For instance, instead of tracking exactly which detector clicked, one might only care about the total number of photons landing in a specific group of detectors. The question has been whether a classical computer, running on standard silicon chips, could predict these grouped results just as well as the quantum machine, effectively stealing the thunder of the quantum advantage. If a classical computer can easily predict the grouped outcomes, the quantum device might not be doing anything truly unique.

A team of researchers has now developed a new method that allows classical computers to efficiently predict a specific and very common type of these grouped results. They focused on what they call linear statistics, which involves adding up the number of photons in different detectors, each multiplied by a specific weight. Think of it as tallying a score where some detectors count for one point, others for two, and so on, and then asking how likely it is to get a certain total score. The researchers proved that for this type of calculation, a classical algorithm can estimate the probabilities just as accurately as running the actual quantum experiment many times. This finding unifies several recent discoveries, showing that tasks like simulating the light absorption spectra of molecules or validating that a quantum device is working correctly can be done efficiently on a classical computer, provided the data is processed in this linear way.

The researchers demonstrated their algorithm by simulating the behavior of photons moving through a network of optical paths. They showed that by using a mathematical technique involving the analysis of patterns in the data rather than calculating every single possibility, a classical computer could estimate the likelihood of different score totals. This method works for various types of light inputs, including standard single photons and more complex states of light used in advanced experiments. In their tests, the algorithm successfully identified the most probable outcomes in a matter of seconds on a standard laptop, even for systems with a number of photons that current experimental hardware struggles to handle due to signal loss. This suggests that for many practical applications, the "hard" part of the quantum calculation is not as hard as once thought, as long as the question being asked is a linear one.

The study also clarified the limits of this classical power. While the new algorithm can handle linear statistics efficiently, it cannot yet solve problems that involve more complex, non-linear ways of grouping the data. For example, some proposed cryptographic applications rely on shuffling the order of outcomes or treating collisions between photons differently from non-collisions. These non-linear strategies appear to escape the reach of the new classical method, leaving open the possibility that they could still offer a genuine quantum advantage. The researchers connected these harder problems to a different area of physics involving interactions between photons, suggesting that solving them might require a deeper understanding of how light particles can influence each other.

Ultimately, this work provides a clearer map of where the boundary lies between what classical computers can do and what requires a quantum machine. It shows that for a wide range of useful tasks, such as analyzing molecular vibrations or checking the performance of quantum devices, we do not need a quantum computer to get the answer; a clever classical algorithm will suffice. However, for the more intricate, non-linear puzzles proposed for cryptography and other advanced tasks, the door remains open for quantum devices to prove their superiority. The researchers leave the community with a challenge: to find new types of questions that are easy for a quantum machine to answer but remain stubbornly difficult for any classical approach, ensuring that the promise of quantum computing remains alive and well.

Problem Statement
Boson Sampling is a leading candidate for demonstrating quantum computational advantage; however, its practical utility is hindered by the exponential size of the outcome space and the anti-concentration properties of the distribution. To utilize Boson Sampling for estimating physical observables or performing computational tasks, one must "coarse grain" the outcome distribution. While individual outcome probabilities are #P-hard to compute exactly, many proposed applications require only the estimation of specific physical observables or grouped probabilities within an additive error. A critical open question remains: which types of coarse-grained distributions can be efficiently simulated classically, and which retain quantum hardness? Specifically, the paper addresses the complexity of estimating linear statistics—probability distributions derived from linear functions of output photon occupation numbers—and investigates whether these can be efficiently approximated classically, potentially undermining certain cryptographic proposals or unifying existing quantum-inspired algorithms.

Methodology
The authors develop an efficient classical algorithm based on the Fourier decomposition of group probabilities. The core methodology involves the following steps:

Definition of Linear Statistics: The paper defines a linear statistic as the probability distribution of values $k = \omega \cdot s$ , where $s$ is the output photon occupation vector and $\omega$ is a non-negative integer weight vector. The outcomes are grouped into bins $B_j$ based on contiguous intervals of these values.
Characteristic Function Connection: The authors relate the characteristic function of the linear statistics distribution, $\chi_\omega(\theta) = \mathbb{E}[e^{i\theta f_\omega(s)}]$ , to the transition amplitude of a linear-optical circuit. Specifically, $\chi_\omega(\theta)$ is shown to be equal to the expectation value $\langle t | \hat{V}_{\Omega, \theta} | t \rangle$ , where $\hat{V}_{\Omega, \theta}$ is a linear interferometer operator associated with the unitary $V_{\Omega, \theta} = U^\dagger e^{i\theta \Omega} U$ .
Fourier Estimation: Using the discrete Fourier transform, the cumulative distribution function (CDF) $S(x) = \Pr[f_\omega(s) \leq x]$ is expressed as an expectation over a discrete set of characteristic function values.
Importance Sampling: To estimate the CDF efficiently, the authors employ an importance sampling distribution $q(k)$ that scales as $1/k$ . This ensures that the estimator's range remains polynomially bounded ( $O(\log N)$ ), allowing for efficient classical estimation of the CDF to inverse-polynomial additive error.
Extension to General Inputs: The framework relies on the ability to efficiently compute or approximate the characteristic function. The authors demonstrate that this is possible for various input states, including Fock states, Gaussian states (displaced squeezed vacua), and partially distinguishable photons, by leveraging existing algorithms for transition amplitudes (e.g., those based on matrix permanents or Hafnians).

Key Contributions and Results

Efficient Classical Algorithm: The paper presents a randomized classical algorithm that estimates the cumulative distribution of linear statistics for Boson Sampling with $n$ photons and $m$ modes in expected time polynomial in $m$ , $\epsilon^{-1}$ , and $\log(1/\delta)$ . This holds for a broad class of input states, including Fock and squeezed states.
Unification of Existing Results: The algorithm unifies recent results on efficient quantum-inspired classical simulations of molecular vibronic spectra and efficient approximations of coarse-grained distributions based on detector binning under a single framework of linear statistics.
Cryptographic Implications: The authors apply their algorithm to the "most probable bin" problem, a core component of a proposed Boson Sampling-based one-way function. They demonstrate that this specific problem can be evaluated classically with the same efficiency as running the experiment, thereby showing that this specific cryptographic proposal does not offer a quantum advantage over classical simulation.
Robustness to Noise: The framework naturally incorporates experimental imperfections, such as photon loss and partial distinguishability, by modifying the characteristic function without increasing the computational complexity of the simulation.
Limitations and Open Questions: The paper explicitly states that their techniques do not apply to non-linear statistics or binning strategies that involve permutations or non-linear post-processing (e.g., treating collision-free events differently). They connect the simulation of non-linear statistics (specifically quadratic functions) to the open problem of computing transition amplitudes in linear-optical circuits with a single layer of photon-photon interactions (Kerr interactions).

Significance
The paper establishes a clear boundary for the classical simulability of Boson Sampling applications. It demonstrates that a wide class of coarse-grained problems, defined by linear functions of the output, do not provide a quantum advantage, as they can be efficiently approximated classically. This result challenges the viability of certain cryptographic proposals based on Boson Sampling while simultaneously validating the efficiency of quantum-inspired algorithms for molecular spectroscopy and device validation. The work leaves open the question of classical simulability for non-linear statistics, suggesting that the hardness of these problems may be intrinsically linked to the complexity of simulating single-layer non-linear optical interactions. The authors emphasize that while their method requires asymptotically more samples than an ideal experiment for certain parameters, the classical runtime for finite-size experiments can be significantly shorter than the time required to obtain sufficient samples from current noisy quantum hardware.

More like this