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:2501.13101 · PRX Quantum

Simulating Quantum Circuits with Arbitrary Local Noise Using Pauli Propagation

Armando Angrisani, Antonio Anna Mele, Manuel S. Rudolph, Marco Cerezo, Zoë Holmes

Published Mar 17, 2026• 70 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/fb28-wlv2

Related papers

Classically Estimating Observables of Noiseless Quantum Circuits

Armando Angrisani, Alexander Schmidhuber, Manuel S. Rudolph +3 more

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.

arXiv:2409.01706•Physical Review Letters•Sep 8, 2025•118 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

Classical simulation of noisy quantum circuits via locally entanglement-optimal unravelings

Simon Cichy, Paul K. Faehrmann, Lennart Bittel +2 more

Classical simulations of noisy quantum circuits are instrumental to our understanding of the behavior of real-world quantum systems and the identification of regimes where one expects quantum advantage. In this work, we present a highly parallelizable tensor-network-based classical algorithm, equipped with rigorous accuracy guarantees, for simulating n -qubit quantum circuits with arbitrary single-qubit noise. Our algorithm represents the state of a noisy quantum system by a particular ensemble of matrix product states from which we stochastically sample. Each pure state evolved under a single-qubit noise process is then represented by the ensemble of states that achieves the minimal average entanglement (the entanglement of formation) between the noisy qubit and the remainder. This approach lets us use a more compact representation of the quantum state for a given accuracy requirement and noise level. For a given maximum bond dimension χ and circuit, our algorithm comes with an upper bound on the simulation error, runs in poly ( n , χ ) -time, and improves upon related prior work (1) in scope by extending analytic methods from the three commonly considered noise models to general single-qubit noise, (2) in performance by deriving an exact, closed-form solution to the local entanglement minimization problem, previously approached via variational heuristics, thereby guaranteeing local optimality without numerical optimization overhead, and (3) in conceptual contribution by showing that the fixed unraveling used in prior work becomes equivalent to our choice of unraveling in the special case of depolarizing, dephasing, and amplitude damping noise acting on a maximally entangled state.

arXiv:2508.05745•Physical Review A•Jul 9, 2026•13 citations

Efficient simulation of noisy IQP circuits with amplitude-damping noise

Shravan Shravan, Mohsin Raza, Ariel Shlosberg

Efficient classical simulation of noisy intermediate-scale quantum (NISQ) circuits has been a topic of intense study over the past few years. The majority of results on efficient simulation assume that the circuits undergo some variant of unital noise or involve sufficient randomness. However, there are limited results for circuits undergoing non-unital noise in the absence of randomness. In this work, we present a polynomial-time classical algorithm to sample from the output distributions of amplitude-damped instantaneous quantum polynomial (IQP) circuits. Our algorithm works for circuits generated by arbitrary $l$-local diagonal gates with depth $d = Ω(\log(n))$, undergoing constant amplitude-damping noise.

quant-pharXiv:2604.05036•Apr 8, 2026•3 citations

Pauli path simulations of noisy quantum circuits beyond average case

Guillermo González-García, J. I. Cirac, Rahul Trivedi

For random quantum circuits on n qubits of depth Θ ( log ⁡ n ) with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method \cite{Aharonov2023_paulipaths} . This paper aims to study the performance of this method beyond random circuits. We first consider the classical simulation of local observables in circuits composed of Clifford and T gates – going beyond the average case analysis, we derive sufficient conditions for simulatability in terms of the noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate than T gates, the simulation becomes classically easy. As an application of this result, we study 2D QAOA circuits that attempt to find low-energy states of classical Ising models on general graphs. There, our results shows that for hard instances of the problem, which correspond to Ising model's graph being geometrically non-local, a QAOA algorithm mapped to a geometrically local circuit architecture using SWAP gates does not have any asymptotic advantage over classical algorithms if depolarized at a constant rate. Finally, we illustrate instances where the Pauli path method fails to give the correct result, and also initiate a study of the trade-off between fragility to noise and classical complexity of simulating a given quantum circuit.

arXiv:2407.16068•Quantum•May 5, 2025•35 citations

Quantum Enhanced Pauli Propagation

S. Majumder, J. R. Garrison, L. Luo +8 more

Accurately estimating observables on noisy quantum devices remains a central challenge for near-term quantum algorithms. While quantum error mitigation techniques can reduce noise-induced bias, they often rely on unverifiable assumptions about the circuit noise, and cannot guarantee the magnitude of residual bias error. Here, rather than using classical resources to mitigate a noisy quantum circuit execution, we propose a hybrid algorithm that uses quantum resources to improve the accuracy of approximate classical Pauli-path simulation. Our protocol, Quantum Enhanced Pauli Propagation (QuEPP), uses Clifford perturbation theory (CPT) to construct a classically simulable ensemble of Clifford circuits from the low-order terms in CPT, which directly provide the approximate classical Pauli-path simulation of the target circuit. Noisy quantum expectation values of this ensemble are then used to infer a global rescaling factor that corrects quantum execution of the target circuit, providing higher-order contributions absent from the truncated low-order classical simulation. This approach requires no noise characterization, applies to arbitrary circuits, and provides a provable route to asymptotically unbiased estimates. Using IBM Heron hardware, we demonstrate QuEPP on 2D random mirror circuits of up to 49 qubits and circuit depth 80, as well as Trotterized Hamiltonian evolution, showing consistent improvements beyond classical CPT and unmitigated quantum results. QuEPP offers a simple, scalable, and model-free framework for enabling accurate quantum computation in the pre-fault-tolerant era.

quant-pharXiv:2603.14485•Mar 17, 2026•5 citations
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 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.
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.
Classical simulations of noisy quantum circuits are instrumental to our understanding of the behavior of real-world quantum systems and the identification of regimes where one expects quantum advantage. In this work, we present a highly parallelizable tensor-network-based classical algorithm, equipped with rigorous accuracy guarantees, for simulating n -qubit quantum circuits with arbitrary single-qubit noise. Our algorithm represents the state of a noisy quantum system by a particular ensemble of matrix product states from which we stochastically sample. Each pure state evolved under a single-qubit noise process is then represented by the ensemble of states that achieves the minimal average entanglement (the entanglement of formation) between the noisy qubit and the remainder. This approach lets us use a more compact representation of the quantum state for a given accuracy requirement and noise level. For a given maximum bond dimension χ and circuit, our algorithm comes with an upper bound on the simulation error, runs in poly ( n , χ ) -time, and improves upon related prior work (1) in scope by extending analytic methods from the three commonly considered noise models to general single-qubit noise, (2) in performance by deriving an exact, closed-form solution to the local entanglement minimization problem, previously approached via variational heuristics, thereby guaranteeing local optimality without numerical optimization overhead, and (3) in conceptual contribution by showing that the fixed unraveling used in prior work becomes equivalent to our choice of unraveling in the special case of depolarizing, dephasing, and amplitude damping noise acting on a maximally entangled state.
Efficient classical simulation of noisy intermediate-scale quantum (NISQ) circuits has been a topic of intense study over the past few years. The majority of results on efficient simulation assume that the circuits undergo some variant of unital noise or involve sufficient randomness. However, there are limited results for circuits undergoing non-unital noise in the absence of randomness. In this work, we present a polynomial-time classical algorithm to sample from the output distributions of amplitude-damped instantaneous quantum polynomial (IQP) circuits. Our algorithm works for circuits generated by arbitrary lll-local diagonal gates with depth d=Ω(log⁡(n))d = Ω(\log(n))d=Ω(log(n)), undergoing constant amplitude-damping noise.
For random quantum circuits on n qubits of depth Θ ( log ⁡ n ) with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method \cite{Aharonov2023_paulipaths} . This paper aims to study the performance of this method beyond random circuits. We first consider the classical simulation of local observables in circuits composed of Clifford and T gates – going beyond the average case analysis, we derive sufficient conditions for simulatability in terms of the noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate than T gates, the simulation becomes classically easy. As an application of this result, we study 2D QAOA circuits that attempt to find low-energy states of classical Ising models on general graphs. There, our results shows that for hard instances of the problem, which correspond to Ising model's graph being geometrically non-local, a QAOA algorithm mapped to a geometrically local circuit architecture using SWAP gates does not have any asymptotic advantage over classical algorithms if depolarized at a constant rate. Finally, we illustrate instances where the Pauli path method fails to give the correct result, and also initiate a study of the trade-off between fragility to noise and classical complexity of simulating a given quantum circuit.
Accurately estimating observables on noisy quantum devices remains a central challenge for near-term quantum algorithms. While quantum error mitigation techniques can reduce noise-induced bias, they often rely on unverifiable assumptions about the circuit noise, and cannot guarantee the magnitude of residual bias error. Here, rather than using classical resources to mitigate a noisy quantum circuit execution, we propose a hybrid algorithm that uses quantum resources to improve the accuracy of approximate classical Pauli-path simulation. Our protocol, Quantum Enhanced Pauli Propagation (QuEPP), uses Clifford perturbation theory (CPT) to construct a classically simulable ensemble of Clifford circuits from the low-order terms in CPT, which directly provide the approximate classical Pauli-path simulation of the target circuit. Noisy quantum expectation values of this ensemble are then used to infer a global rescaling factor that corrects quantum execution of the target circuit, providing higher-order contributions absent from the truncated low-order classical simulation. This approach requires no noise characterization, applies to arbitrary circuits, and provides a provable route to asymptotically unbiased estimates. Using IBM Heron hardware, we demonstrate QuEPP on 2D random mirror circuits of up to 49 qubits and circuit depth 80, as well as Trotterized Hamiltonian evolution, showing consistent improvements beyond classical CPT and unmitigated quantum results. QuEPP offers a simple, scalable, and model-free framework for enabling accurate quantum computation in the pre-fault-tolerant era.