Classical algorithms for measurement-adaptive Gaussian circuits

Abstract

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.

36 pages, 2 figures

References in corpus (54)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Gaussian Quantum Information
• Quantum computational advantage using photons
• Improved Simulation of Stabilizer Circuits
• Strong quantum computational advantage using a superconducting quantum processor
• Quantum circuits with many photons on a programmable nanophotonic chip
• Gaussian Boson Sampling
• Positive Wigner functions render classical simulation of quantum computation efficient
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Negative Quasi-Probability as a Resource for Quantum Computation
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Blueprint for a Scalable Photonic Fault-Tolerant Quantum Computer
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• No imminent quantum supremacy by boson sampling
• All-Gaussian universality and fault tolerance with the Gottesman-Kitaev-Preskill code
• Computational advantage of quantum random sampling
• Gaussian Boson Sampling with Pseudo-Photon-Number Resolving Detectors and Quantum Computational Advantage
• Sufficient Conditions for Efficient Classical Simulation of Quantum Optics
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Stellar representation of non-Gaussian quantum states
• Phase transition in Random Circuit Sampling
• Simulating boson sampling in lossy architectures
• The Boundary for Quantum Advantage in Gaussian Boson Sampling
• Regimes of classical simulability for noisy Gaussian boson sampling
• Classical simulation of photonic linear optics with lost particles
• Resources for bosonic quantum computational advantage
• Classical algorithms for quantum mean values
• Classical algorithm for simulating experimental Gaussian boson sampling
• Boson sampling with Gaussian measurements
• From estimation of quantum probabilities to simulation of quantum circuits
• Classical simulation of lossy boson sampling using matrix product operators
• Franck-Condon factors by counting perfect matchings of graphs with loops
• Classical simulation of boson sampling based on graph structure
• An atomic boson sampler
• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Quantum machine learning with Adaptive Boson Sampling via post-selection
• Quantum machine learning with adaptive linear optics
• Simulating lossy Gaussian boson sampling with matrix product operators
• Non-linear Boson Sampling
• Typical entanglement for Gaussian states
• Quantum-inspired classical algorithm for molecular vibronic spectra
• Simulation of quantum optics by coherent state decomposition
• Page curves and typical entanglement in linear optics
• Classical simulation of non-Gaussian bosonic circuits
• Complexity of full counting statistics of free quantum particles in product states
• A Photonic Parameter-shift Rule: Enabling Gradient Computation for Photonic Quantum Computers
• Sufficient condition for universal quantum computation using bosonic circuits
• Variational approach to photonic quantum circuits via the parameter shift rule
• Phase-space negativity as a computational resource for quantum kernel methods
• Classical simulation and quantum resource theory of non-Gaussian optics
• Classical simulability of constant-depth linear-optical circuits with noise
• Approximating outcome probabilities of linear optical circuits