Gaussian building blocks are essential for photonic quantum information processing, and universality can be practically achieved by equipping Gaussian circuits with adaptive measurement and feedforward. The number of adaptive steps then provides a natural parameter for computational power. Rather than assessing power only through sampling problems—the usual benchmark—we follow the ongoing shift toward tasks of practical relevance and study the quantum mean-value problem, i.e., estimating observable expectation values that underpin simulation and variational algorithms. More specifically, we analyze bosonic circuits with adaptivity and prove that when the number of adaptive measurements is small, the mean-value problem admits efficient classical algorithms even if a large amount of non-Gaussian resources are present in the input state, whereas less constrained regimes are computationally hard. This yields a task-level contrast with sampling, where non-Gaussian ingredients alone often induce hardness, and provides a clean complexity boundary parameterized by the number of adaptive measurement-and-feedforward steps between classical simulability and quantum advantage. Beyond the main result, we introduce classical techniques—including a generalization of Gurvits’ second algorithm to arbitrary product inputs and Gaussian circuits—for computing the marginal quantities needed by our estimators, which may be of independent interest.
Gaussian building blocks are essential for photonic quantum information processing, and universality can be practically achieved by equipping Gaussian circuits with adaptive measurement and feedforward. The number of adaptive steps then provides a natural parameter for computational power. Rather than assessing power only through sampling problems—the usual benchmark—we follow the ongoing shift toward tasks of practical relevance and study the quantum mean-value problem, i.e., estimating observable expectation values that underpin simulation and variational algorithms. More specifically, we analyze bosonic circuits with adaptivity and prove that when the number of adaptive measurements is small, the mean-value problem admits efficient classical algorithms even if a large amount of non-Gaussian resources are present in the input state, whereas less constrained regimes are computationally hard. This yields a task-level contrast with sampling, where non-Gaussian ingredients alone often induce hardness, and provides a clean complexity boundary parameterized by the number of adaptive measurement-and-feedforward steps between classical simulability and quantum advantage. Beyond the main result, we introduce classical techniques—including a generalization of Gurvits’ second algorithm to arbitrary product inputs and Gaussian circuits—for computing the marginal quantities needed by our estimators, which may be of independent interest.
We present a classical algorithm for approximating the expectation values of observables in linear optical circuits with arbitrary product input states, achieving additive-error accuracy. This result indicates that current applications of photonic systems aimed at demonstrating practical quantum advantage through expectation value estimation, such as photonic variational algorithms, may face challenges in attaining the computational advantage. It also implies the output probabilities of boson sampling with arbitrary product input states can be efficiently approximated by our method, so that boson sampling becomes efficiently simulable when its output probability distribution is polynomially sparse. We also develop an efficient classical algorithm for estimating transition amplitudes of arbitrary product states in linear optical circuits. This provides additive-error approximation algorithms for matrix functions associated with linear optical circuits, such as the (loop-)Hafnian, which are of independent interest. As an application, it solves the generalized molecular vibronic spectra problem [C. Oh et al., Nat. Phys. 20, 225 (2024)10.1038/s41567-023-02308-9], previously suggested as a candidate for practical quantum advantage. Finally, we extend our framework to near-Clifford circuits, enabling classical approximation of their expectation values.
Quantum generative modeling has emerged as a promising application of quantum computers, aiming to model complex probability distributions beyond the reach of classical methods. In practice, however, training such models often requires costly gradient estimation performed directly on the quantum hardware. Crucially, for certain structured quantum circuits, expectation values of local observables can be efficiently evaluated on a classical computer, enabling classical training without calls to the quantum hardware in the optimization loop. In these models, sampling from the resulting circuits can still be classically hard, so inference must be performed on a quantum device, yielding a potential computational advantage. In this work, we introduce a photonic quantum generative model built on parametrized Gaussian Boson Sampling circuits. The training is based on the efficient classical evaluation of expectation values enabled by the Gaussian structure of the state, allowing scalable optimization of the model parameters through the maximum mean discrepancy loss function. We demonstrate the effectiveness of the approach through numerical experiments on photonic systems with up to 805 modes and over a million trainable parameters, highlighting its scalability and suitability for near-term photonic quantum devices.
If classical algorithms have been successful in reproducing the estimation of expectation values of observables of some quantum circuits using off-the-shelf computing resources, matching the performance of the most advanced quantum devices on sampling problems usually requires extreme cost in terms of memory and computing operations, making them accessible to only a handful of supercomputers around the world. In this work, we demonstrate for the first time a classical simulation outperforming Gaussian boson sampling experiments of one hundred modes on established benchmark tests using a single CPU or GPU. Being embarrassingly parallelizable, a small number of CPUs or GPUs allows us to match previous sampling rates that required more than one hundred GPUs. We believe algorithmic and implementation improvements will generalize our tools to photo-counting, single-photon inputs, and pseudo-photon-number-resolving scenarios beyond one thousand modes. Finally, most of the innovations in our tools remain valid for generic probability distributions over binary variables, rendering it potentially applicable to the simulation of qubit-based sampling problems and creating classical surrogates for classical-quantum algorithms.
Quantum computers solve intractable problems which classically require an exponentially long time to compute. With the development of large-scale experiments that claim quantum advantage, a vital issue has now emerged. What are the errors, and how do they affect the complexity of the problem solved? Large-scale Gaussian boson sampling (GBS) experiments give an example in which random numbers are generated. Despite classical hardness, these have computable benchmarks for checking data validity. While there are other quantum computing architectures, Gaussian boson sampling is uniquely testable at all scales. Several large, pioneering quantum computing (QC) experiments have been carried out to investigate quantum advantage. Here, we introduce a highly scalable but classical algorithm that can solve GBS approximately. Our numerical simulation of the output count data is closer to the exact solution than current experiments up to 1152 modes. This algorithm outperforms all previous classical, approximate algorithms and scales efficiently to larger experiments. Our results show that effects beyond losses can cause the errors that allow classical simulability. This work will lead to more precise algorithms and is a step towards understanding how QC quantum advantage is affected by the underlying physics.
Boson Sampling is a prominent candidate for the demonstration of quantum computational advantage but it remains unclear whether a large-scale boson sampler can find useful computational applications. The challenge is that to use a boson sampler to estimate, for example, a physical observable, it is necessary to coarse grain the outcome distribution, owing to the exponential size of the outcome space and the anti-concentration properties of the Boson Sampling distribution. In this work, we analyse the complexity of a specific type of coarse-graining of Boson Sampling distributions based on linear functions of the output photon occupation numbers, which we refer to as linear statistics. We present an efficient classical algorithm for approximating linear statistics of boson samplers within additive error for different kinds of input states, such as Fock states and squeezed states. This allows us to unify in the same framework recent results on efficient quantum-inspired classical algorithms for simulating molecular vibronic spectra, or efficient classical approximations of coarse-grained distributions based on detector binning. Additionally, we show how our algorithm can be used to classically evaluate a proposed one-way function based on Boson Sampling, while other proposals for cryptographic applications escape our classical simulation techniques. We leave open the question of classical simulability of non-linear statistics and connect it to the problem of computing transition amplitudes of linear-optical circuits with one layer of interactions.
Classical simulability of quantum circuits plays a central role in characterizing and quantifying quantum computational advantage. Typically, the presence of non-Clifford gates introduces an exponential runtime overhead for classically estimating expectation values of observables. In this work, we introduce an efficient simulation framework that integrates the sum-over-Clifford method with quasi-probability-based stabilizer simulation to directly estimate expectation values. To optimize efficiency, we incorporate a circuit-adaptive reduction via variance estimation protocol, which terminates simulations once an empirical confidence bound is sufficient to guarantee the prescribed error tolerance. Our method circumvents overly conservative Hoeffding's inequality, thereby reducing the dependence on the gate-wise stabilizer extent from quadratic to linear in the low-variance regime, while maintaining the same space complexity as previous approaches. We explicitly prove the sample-complexity reduction for random quantum circuits and T-doped Clifford circuits and also empirically validate these advantages in the quantum approximate optimization algorithm and quantum kernel method.