Classically estimating observables of noiseless quantum circuits

Abstract

We present a classical algorithm based on Pauli propagation for estimating expectation values of arbitrary observables on random unstructured quantum circuits across all circuit architectures and depths, including those with all-to-all connectivity. We prove that for any architecture where each circuit layer is randomly sampled from a distribution invariant under single-qubit rotations, our algorithm achieves a small error $\epsilon$ on all circuits except for a small fraction $\delta$. The computational time is polynomial in qubit count and circuit depth for any small constant $\epsilon ,\delta$, and quasi-polynomial for inverse-polynomially small $\epsilon ,\delta$. Our results show that estimating observables of quantum circuits exhibiting chaotic and locally scrambling behavior is classically tractable across all geometries. We further conduct numerical experiments beyond our average-case assumptions, demonstrating the potential utility of Pauli propagation methods for simulating real-time dynamics and finding low-energy states of physical Hamiltonians.

arXiv commentMain text: 9 pages, 2 figures. Appendices: 29 pages, 3 figures. Revised version with improved presentation and additional numerical experiments

References in corpus (43)

• Variational Quantum Algorithms
• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Improved Simulation of Stabilizer Circuits
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Classical simulation of quantum many-body systems with a tree tensor network
• Simulating quantum computation by contracting tensor networks
• Chaos and complexity by design
• Efficient numerical simulations with Tensor Networks: Tensor Network Python (TeNPy)
• The randomized measurement toolbox
• Improved classical simulation of quantum circuits dominated by Clifford gates
• Tensor network decompositions in the presence of a global symmetry
• Provably efficient machine learning for quantum many-body problems
• Barren Plateaus in Variational Quantum Computing
• Efficient classical simulation of random shallow 2D quantum circuits
• Introduction to Haar Measure Tools in Quantum Information: A Beginner's Tutorial
• Approximate unitary $t$-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Decoupling with random quantum circuits
• Classical Shadow Tomography with Locally Scrambled Quantum Dynamics
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• A polynomial-time classical algorithm for noisy random circuit sampling
• Does provable absence of barren plateaus imply classical simulability?
• Understanding quantum machine learning also requires rethinking generalization
• Out-of-distribution generalization for learning quantum dynamics
• Minimal Model for Fast Scrambling
• Efficient tensor network simulation of IBM's largest quantum processors
• Classical algorithms for quantum mean values
• Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage
• Quantum-to-Classical Correspondence and Hubbard-Stratonovich Dynamical Systems, a Lie-Algebraic Approach
• Operator backflow and the classical simulation of quantum transport
• Markovian Entanglement Dynamics under Locally Scrambled Quantum Evolution
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Efficient solvability of Hamiltonians and limits on the power of some quantum computational models
• Dynamical simulation via quantum machine learning with provable generalization
• Noisy intermediate-scale quantum algorithm for semidefinite programming
• Efficient classical algorithms for simulating symmetric quantum systems
• Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach
• Fourier expansion in variational quantum algorithms
• Tight and Efficient Gradient Bounds for Parameterized Quantum Circuits
• Optimal sampling of dynamical large deviations in two dimensions via tensor networks
• Magic Resources of the Heisenberg Picture
• Computing exact moments of local random quantum circuits via tensor networks
• Pauli path simulations of noisy quantum circuits beyond average case
• Quantum simulation of operator spreading in the chaotic Ising model

Cited by in corpus (17)

• Quantum Convolutional Neural Networks are Effectively Classically Simulable
• Noise-induced shallow circuits and absence of barren plateaus
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation
• Efficient quantum-enhanced classical simulation for patches of quantum landscapes
• Double-bracket algorithm for quantum signal processing without post-selection
• Optimal quantum reservoir learning in proximity to universality
• The Dual Role of Low-Weight Pauli Propagation: A Flawed Simulator but a Powerful Initializer for Variational Quantum Algorithms
• Feasibility of performing quantum chemistry calculations on quantum computers
• A graph-theoretic approach to chaos and complexity in quantum systems
• Quantum phase classification via partial tomography-based quantum hypothesis testing
• Utility-Scale Quantum State Preparation: Classical Training using Pauli Path Simulation
• Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings
• Efficient classical computation of the neural tangent kernel of quantum neural networks
• Gradient Scalability and Taylor Surrogation of Quantum Cost Landscapes
• Sampling (noisy) quantum circuits through randomized rounding
• Emulation of large-scale qubit registers with a phase-space approach
• Benchmarking quantum devices beyond classical capabilities