Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2409.01706 · Physical Review Letters

Classically Estimating Observables of Noiseless Quantum Circuits

Armando Angrisani, Alexander Schmidhuber, Manuel S. Rudolph, Marco Cerezo, Zoë Holmes, Hsin-Yuan Huang

Published Sep 8, 2025• 118 citations
arXivHTMLPDF

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 ϵ on all circuits except for a small fraction δ. The computational time is polynomial in qubit count and circuit depth for any small constant ϵ, δ and quasipolynomial for inverse-polynomially small ϵ, δ. Our results show that estimating observables of quantum circuits exhibiting chaotic and locally scrambling behavior is classically tractable across all geometries.

DOI
10.1103/lh6x-7rc3

Related papers

Simulating Quantum Circuits with Arbitrary Local Noise Using Pauli Propagation

Armando Angrisani, Antonio Anna Mele, Manuel S. Rudolph +2 more

We present a polynomial-time classical algorithm for estimating expectation values of arbitrary observables on typical quantum circuits under any incoherent local noise, including non-unital or dephasing. Although previous research demonstrated that some carefully designed quantum circuits affected by non-unital noise cannot be efficiently simulated, we show that this does not apply to average-case circuits, as these can be efficiently simulated using Pauli-path methods. Specifically, we prove that, with high probability over the circuit gates’ choice, Pauli propagation algorithms with tailored truncation strategies achieve an inversely polynomially small simulation error. This result holds for arbitrary circuit topologies and for any local noise, under the assumption that the distribution of each circuit layer is invariant under single-qubit random gates. Under the same minimal assumptions, we also prove that most noisy circuits can be truncated to an effective logarithmic depth for the task of estimating expectation values of observables, thus generalizing prior results to a significantly broader class of circuit ensembles. We further numerically validate our algorithm with simulations on a 6 × 6 lattice of qubits under the effects of amplitude damping and dephasing noise, as well as real-time dynamics on an 11 × 11 lattice of qubits affected by amplitude damping.

arXiv:2501.13101•PRX Quantum•Mar 17, 2026•70 citations

A Polynomial-Time Classical Algorithm for Noisy Quantum Circuits

Thomas Schuster, Chao Yin, Xun Gao +1 more

We provide a polynomial-time classical algorithm for noisy quantum circuits. The algorithm computes the expectation value of any observable for any circuit, with a small average error over input states drawn from an ensemble (e.g., the computational basis). Our approach is based upon the intuition that noise exponentially damps nonlocal correlations relative to local correlations. This enables one to classically simulate a noisy quantum circuit by keeping track of only the dynamics of local quantum information. Our algorithm also enables sampling from the output distribution of a circuit in quasipolynomial time, so long as the distribution anticoncentrates. A number of implications are discussed, including a fundamental limit on the efficacy of noise mitigation strategies: For constant noise rates, any quantum circuit for which error mitigation succeeds in polynomial-time on most input states can also be classically simulated in polynomial-time on most input states. Our algorithms scale exponentially in the inverse noise rate, which is fundamental and makes them impractical for current quantum devices.

arXiv:2407.12768•Physical Review X•Aug 15, 2025•104 citations

Classical simulations of noisy variational quantum circuits

Enrico Fontana, Manuel S. Rudolph, Ross Duncan +2 more

Noise detrimentally affects quantum computations so that they not only become less accurate but also easier to simulate classically as systems scale up. We construct a classical simulation algorithm, lowesa (low weight efficient simulation algorithm), for estimating expectation values of noisy parameterised quantum circuits with a fixed observable. It combines previous results on spectral analysis of parameterised circuits with Pauli back-propagation and recent ideas for simulations of noisy random circuits. We show, under some conditions on the circuits and mild assumptions on noise, that lowesa gives an efficient, polynomial algorithm in the number of qubits (and depth), with approximation error that vanishes exponentially in the physical error rate and a controllable cutoff parameter. This is valid for any expectation value that may be efficiently evaluated on a quantum computer. We discuss the practical limitations of the method for circuit classes with correlated parameters and its scaling with decreasing error rates.

arXiv:2306.05400•npj Quantum Information•May 22, 2025•93 citations

Limitations of Noisy Geometrically Local Quantum Circuits

Jon Nelson, Joel Rajakumar, Michael J. Gullans

Quantum circuits with a constant rate of depolarizing noise per qubit per time step are known to converge to the uniform distribution at depth $ω(p^{-1}\log n)$, and hence become trivially classically simulable by uniform sampling. We show that under the physically natural constraint of geometric locality, noisy circuits become classically simulable at shallower depths by substantially more structured classical algorithms. We consider arbitrary geometrically local quantum circuits on $n$ qubits, initialized in an arbitrary product state, with nearest-neighbor gates in $O(1)$ spatial dimensions and interspersed depolarizing noise of any constant strength $p$. Our first result is that when the depth exceeds a threshold $d^*=Θ(p^{-1}\log n)$, the output distribution can be approximately sampled in quasipolynomial time. This gives a worst-case simulability result for noisy geometrically local circuits, and matches in its $n$-dependence the best previously known results for noisy random circuits. The proof is based on new information-theoretic bounds showing that in geometrically local noisy circuits, local regions lose correlations and independently converge to maximally mixed strictly before the entire system converges to the uniform distribution. We further prove structural results suggesting a sharper transition at depth $\tildeΘ(p^{-1})$: after coarse-graining the lattice, Pauli weight supported on long connected paths can be truncated with exponentially small error. These results provide evidence for a percolation-like mechanism behind classical simulability at constant depth, and motivate our conjecture that all noisy geometrically local circuits admit quasipolynomial-time approximate sampling once circuit depth exceeds $\tildeΘ(p^{-1})$.

arXiv:2510.06346•Oct 7, 2025•8 citations

Continuous Noise Model for Quantum Circuits

Yunos El Kaderi, Andreas Honecker, Iryna Andriyanova

Quantum noise is a central challenge in quantum computing across many applications. Extensive work has examined how qubits couple to their environment, leading to decoherence and irreversible relaxation. This work studies a continuous coherent noise model for quantum circuits and compares it with a discrete Pauli model. The focus is on small, coherent gate errors that accumulate across circuit depth. These errors are modeled as random rotations on the Bloch sphere using a von Mises-Fisher distribution. In the small-angle limit, the model reduces to an isotropic Gaussian distribution. We test the model on quantum error-correction circuits based on the [[5,1,3]] and [[7,1,3]] codes. A variant of Grover's search circuit with different qubit counts is also examined. To enable fair comparison, we introduce a model-independent matching scheme. Pauli and continuous noise channels are aligned using the binary entropy at readout. This isolates the effect of noise structure at fixed uncertainty. An approximate analytical method for the propagation of coherent errors is also developed. The method tracks error distributions both on Clifford and non-Clifford circuits without full Monte Carlo sampling. It reduces simulation cost while preserving accuracy for circuit-level error estimates. The approximation is validated against brute-force simulations, identifying its regime of validity with Clifford and non-Clifford circuits under error correction. Our results show that continuous coherent noise and Pauli noise lead to comparable logical-error trends in the stabilizer-code circuits studied here. This behavior is consistent with syndrome extraction projecting a general single-qubit error onto Pauli-error subspaces before recovery. They also show where simplified propagation models work well and where their accuracy is reduced.

quant-pharXiv:2604.26008•Apr 30, 2026•0 citations

Learning Shallow Quantum Circuits

Hsin-Yuan Huang, Yunchao Liu, Michael Broughton +4 more

Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can generate distributions that are classically hard to sample from, existing learning algorithms do not apply. In this work, we present a polynomial-time classical algorithm for learning the description of any unknown n-qubit shallow quantum circuit U (with arbitrary unknown architecture) within a small diamond distance using single-qubit measurement data on the output states of U. We also provide a polynomial-time classical algorithm for learning the description of any unknown n-qubit state | ψ ⟩ = U | 0n ⟩ prepared by a shallow quantum circuit U (on a 2D lattice) within a small trace distance using single-qubit measurements on copies of | ψ ⟩. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions. This circuit representation yields an optimization landscape that can be efficiently navigated and enables efficient learning of quantum circuits that are classically hard to simulate.

arXiv:2401.10095•ACM Symposium on Theory of Computing (STOC)•Jun 10, 2024•66 citations
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 ϵ on all circuits except for a small fraction δ. The computational time is polynomial in qubit count and circuit depth for any small constant ϵ, δ and quasipolynomial for inverse-polynomially small ϵ, δ. Our results show that estimating observables of quantum circuits exhibiting chaotic and locally scrambling behavior is classically tractable across all geometries.
We present a polynomial-time classical algorithm for estimating expectation values of arbitrary observables on typical quantum circuits under any incoherent local noise, including non-unital or dephasing. Although previous research demonstrated that some carefully designed quantum circuits affected by non-unital noise cannot be efficiently simulated, we show that this does not apply to average-case circuits, as these can be efficiently simulated using Pauli-path methods. Specifically, we prove that, with high probability over the circuit gates’ choice, Pauli propagation algorithms with tailored truncation strategies achieve an inversely polynomially small simulation error. This result holds for arbitrary circuit topologies and for any local noise, under the assumption that the distribution of each circuit layer is invariant under single-qubit random gates. Under the same minimal assumptions, we also prove that most noisy circuits can be truncated to an effective logarithmic depth for the task of estimating expectation values of observables, thus generalizing prior results to a significantly broader class of circuit ensembles. We further numerically validate our algorithm with simulations on a 6 × 6 lattice of qubits under the effects of amplitude damping and dephasing noise, as well as real-time dynamics on an 11 × 11 lattice of qubits affected by amplitude damping.
We provide a polynomial-time classical algorithm for noisy quantum circuits. The algorithm computes the expectation value of any observable for any circuit, with a small average error over input states drawn from an ensemble (e.g., the computational basis). Our approach is based upon the intuition that noise exponentially damps nonlocal correlations relative to local correlations. This enables one to classically simulate a noisy quantum circuit by keeping track of only the dynamics of local quantum information. Our algorithm also enables sampling from the output distribution of a circuit in quasipolynomial time, so long as the distribution anticoncentrates. A number of implications are discussed, including a fundamental limit on the efficacy of noise mitigation strategies: For constant noise rates, any quantum circuit for which error mitigation succeeds in polynomial-time on most input states can also be classically simulated in polynomial-time on most input states. Our algorithms scale exponentially in the inverse noise rate, which is fundamental and makes them impractical for current quantum devices.
Noise detrimentally affects quantum computations so that they not only become less accurate but also easier to simulate classically as systems scale up. We construct a classical simulation algorithm, lowesa (low weight efficient simulation algorithm), for estimating expectation values of noisy parameterised quantum circuits with a fixed observable. It combines previous results on spectral analysis of parameterised circuits with Pauli back-propagation and recent ideas for simulations of noisy random circuits. We show, under some conditions on the circuits and mild assumptions on noise, that lowesa gives an efficient, polynomial algorithm in the number of qubits (and depth), with approximation error that vanishes exponentially in the physical error rate and a controllable cutoff parameter. This is valid for any expectation value that may be efficiently evaluated on a quantum computer. We discuss the practical limitations of the method for circuit classes with correlated parameters and its scaling with decreasing error rates.
Quantum circuits with a constant rate of depolarizing noise per qubit per time step are known to converge to the uniform distribution at depth ω(p−1log⁡n)ω(p^{-1}\log n)ω(p−1logn), and hence become trivially classically simulable by uniform sampling. We show that under the physically natural constraint of geometric locality, noisy circuits become classically simulable at shallower depths by substantially more structured classical algorithms. We consider arbitrary geometrically local quantum circuits on nnn qubits, initialized in an arbitrary product state, with nearest-neighbor gates in O(1)O(1)O(1) spatial dimensions and interspersed depolarizing noise of any constant strength ppp. Our first result is that when the depth exceeds a threshold d∗=Θ(p−1log⁡n)d^*=Θ(p^{-1}\log n)d∗=Θ(p−1logn), the output distribution can be approximately sampled in quasipolynomial time. This gives a worst-case simulability result for noisy geometrically local circuits, and matches in its nnn-dependence the best previously known results for noisy random circuits. The proof is based on new information-theoretic bounds showing that in geometrically local noisy circuits, local regions lose correlations and independently converge to maximally mixed strictly before the entire system converges to the uniform distribution. We further prove structural results suggesting a sharper transition at depth Θ~(p−1)\tildeΘ(p^{-1})Θ~(p−1): after coarse-graining the lattice, Pauli weight supported on long connected paths can be truncated with exponentially small error. These results provide evidence for a percolation-like mechanism behind classical simulability at constant depth, and motivate our conjecture that all noisy geometrically local circuits admit quasipolynomial-time approximate sampling once circuit depth exceeds Θ~(p−1)\tildeΘ(p^{-1})Θ~(p−1).
Quantum noise is a central challenge in quantum computing across many applications. Extensive work has examined how qubits couple to their environment, leading to decoherence and irreversible relaxation. This work studies a continuous coherent noise model for quantum circuits and compares it with a discrete Pauli model. The focus is on small, coherent gate errors that accumulate across circuit depth. These errors are modeled as random rotations on the Bloch sphere using a von Mises-Fisher distribution. In the small-angle limit, the model reduces to an isotropic Gaussian distribution. We test the model on quantum error-correction circuits based on the [[5,1,3]] and [[7,1,3]] codes. A variant of Grover's search circuit with different qubit counts is also examined. To enable fair comparison, we introduce a model-independent matching scheme. Pauli and continuous noise channels are aligned using the binary entropy at readout. This isolates the effect of noise structure at fixed uncertainty. An approximate analytical method for the propagation of coherent errors is also developed. The method tracks error distributions both on Clifford and non-Clifford circuits without full Monte Carlo sampling. It reduces simulation cost while preserving accuracy for circuit-level error estimates. The approximation is validated against brute-force simulations, identifying its regime of validity with Clifford and non-Clifford circuits under error correction. Our results show that continuous coherent noise and Pauli noise lead to comparable logical-error trends in the stabilizer-code circuits studied here. This behavior is consistent with syndrome extraction projecting a general single-qubit error onto Pauli-error subspaces before recovery. They also show where simplified propagation models work well and where their accuracy is reduced.
Despite fundamental interests in learning quantum circuits, the existence of a computationally efficient algorithm for learning shallow quantum circuits remains an open question. Because shallow quantum circuits can generate distributions that are classically hard to sample from, existing learning algorithms do not apply. In this work, we present a polynomial-time classical algorithm for learning the description of any unknown n-qubit shallow quantum circuit U (with arbitrary unknown architecture) within a small diamond distance using single-qubit measurement data on the output states of U. We also provide a polynomial-time classical algorithm for learning the description of any unknown n-qubit state | ψ ⟩ = U | 0n ⟩ prepared by a shallow quantum circuit U (on a 2D lattice) within a small trace distance using single-qubit measurements on copies of | ψ ⟩. Our approach uses a quantum circuit representation based on local inversions and a technique to combine these inversions. This circuit representation yields an optimization landscape that can be efficiently navigated and enables efficient learning of quantum circuits that are classically hard to simulate.