PaperlayerView exact revision on arXiv

Source-linked AI summary

Simulating quantum circuits with arbitrary local noise using Pauli Propagation

Armando Angrisani, Antonio A. Mele, Manuel S. Rudolph, M. Cerezo, Zoë Holmes

arXiv:2501.13101v2quant-ph

TL;DR

The paper addresses efficient classical simulation of typical quantum circuits under arbitrary incoherent local noise, including noise types beyond depolarizing models. It combines Pauli propagation with path-weight truncation and proves inverse-polynomial-precision estimation for most circuits under single-qubit-randomness assumptions, while also establishing effective logarithmic depth and numerical validation.

  • Problem

    Existing results left open whether typical circuits under arbitrary local noise, including non-unital or dephasing noise, could be efficiently simulated.

  • Method

    The paper combines Pauli-path simulation with path-weight truncation under circuit-layer distributions invariant under single-qubit random gates.

  • Results

    Expectation values of observables can be estimated in polynomial time with inverse-polynomial accuracy for most circuits under arbitrary local incoherent noise, including non-unital and dephasing noise.

  • Takeaways & Limitations

    Under the stated randomness assumptions, most noisy circuits have an effective logarithmic depth for expectation-value estimation, and numerical errors can be substantially below analytic guarantees.

Abstract

from arXiv · show

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\times6$ lattice of qubits under the effects of amplitude damping and dephasing noise, as well as real-time dynamics on an $11\times11$ lattice of qubits affected by amplitude damping.

I. INTRODUCTION

The paper addresses how hardware noise affects the classical simulability of quantum circuits, extending efficient simulation beyond depolarizing noise and highly random ensembles. It combines Pauli propagation with path-weight truncation to simulate typical noisy circuits under broad local-noise assumptions.

  • Hardware noise creates a tension between implementing quantum algorithms and maintaining circuits that are hard to simulate classically.Noise can simplify classical simulation, while noise-resistant circuit design can favor classically tractable circuits.
  • Prior analyses focused largely on depolarizing noise, whose Pauli representation suppresses global operators more strongly than local ones.This structure supports Pauli-path simulation methods but does not capture many experimental dissipation processes.
  • Non-unital and dephasing noise can behave differently from depolarizing noise, and carefully designed circuits under these noises may remain difficult to simulate.Non-unital noise can reduce entropy, while dephasing can support quantum computation for polynomial time in some constructions.
  • The paper develops efficient simulation for typical circuits with arbitrary local incoherent noise, including non-unital and dephasing noise.Each circuit layer must be sampled from a distribution invariant under suitable single-qubit random gates.
  • Path-weight truncation combined with Pauli propagation achieves inversely polynomial error in polynomial time for arbitrary circuit topologies.The truncation tracks cumulative Pauli weight along branches rather than only the current Pauli weight.
  • Under the same minimal assumptions, incoherent noise reduces expectation-value estimation to an effective logarithmic-depth circuit.Gates outside this depth window can be ignored for the estimation task.
  • Numerical simulations on a periodic 6×6 lattice with amplitude damping and dephasing found substantially smaller errors than the analytic bounds.The simulations used a transverse-field Ising variational ansatz and Monte Carlo certification.

II. FRAMEWORK

The framework represents arbitrary single-qubit noise through normal-form parameters and studies noisy random circuits with locally unbiased or locally scrambling layers. These assumptions cover depolarizing-like, dephasing-like, and non-unital noise while retaining efficient-simulation guarantees.

  • A single-qubit noise channel is represented using contraction parameters D and translation parameters t in a normal form.The channel is unital when N(I)=I and non-unital otherwise.
  • Constant noise rate means 1/3∥D∥2^2 is a constant strictly smaller than one.
  • Depolarizing-like noise drives states toward the maximally mixed state, whereas dephasing-like noise drives states toward a Bloch-sphere diameter.
  • Non-unital noise does not preserve the identity and drives states toward a fixed point different from the maximally mixed state.Amplitude damping is a representative example whose fixed point is the computational zero state.
  • The framework applies to arbitrary local noise with constant noise rate, including non-unital and dephasing-like channels.
  • The circuit consists of alternating layers of local noise and non-overlapping gates, followed by a final single-qubit layer.The task is estimating Tr[OC(ρ)] for bounded Hermitian observables and arbitrary initial states.
  • Locally unbiased layers use single-qubit unitary 1-designs, while locally scrambling layers use unitary 2-designs.Approximately locally scrambling distributions extend this framework and can include arbitrary unitaries preceded by orthogonal random Pauli rotations.

III. RELATED WORKS

Prior work established Pauli-path simulation in restricted noise or circuit settings and identified both efficiently simulable and hard noisy-circuit regimes. This paper distinguishes its path-weight truncation approach from current-weight truncation and broadens the supported setting.

  • Earlier work developed noisy-circuit simulation primarily for depolarizing noise and related Pauli-path methods.
  • Some carefully designed circuits under non-unital or dephasing noise can remain hard to simulate classically.Prior constructions exploit non-unital noise as a resource for long-depth fault-tolerant computation and support arbitrary quantum computation for polynomial time under dephasing.
  • Random-circuit studies found qualitative differences between unital and non-unital noise, including altered output anti-concentration and local-observable concentration.These differences are associated with the effective cooling of qubits under non-unital noise.
  • Prior non-unital simulation results covered specific randomized noise models, whereas this work targets arbitrary local noise under broader circuit assumptions.
  • The present algorithm truncates Pauli paths by cumulative path weight rather than truncating operators above a current-weight threshold.This distinction explains differences in runtime relative to the compared noiseless method.
  • Pauli-path methods have also been shown effective for noiseless near-Clifford circuits and received numerical support on Hamiltonian-simulation and QCNN circuits.
  • Table I compares runtimes for estimating bounded-observable expectation values at inversely polynomial precision and failure probability across noise models and circuit assumptions.

IV. RESULTS

The paper proves polynomial-time average-case classical simulation for typical noisy circuits under broad local-noise and circuit-ensemble assumptions, and shows that noise effectively reduces expectation-value estimation to logarithmic depth. Numerical experiments support accurate Pauli-path simulation, often exceeding analytic guarantees.

  • Theoretical guarantees: Polynomial-time simulation achieves additive error ϵ∥O∥ with probability 1 −δ for non-unital noise when observables contain M Pauli terms.The runtime is M · poly(n, ϵ−1, δ−1), assuming constant local noise and independently sampled layers invariant under single-qubit unitary 1-designs.
  • Theoretical guarantees: Polynomial-time simulation also covers arbitrary observables under local unital noise, including dephasing-like channels.This result requires circuit layers invariant under approximately scrambling single-qubit gates and a constant noise rate.
  • Theoretical guarantees: For logarithmic-or-greater circuit depth, arbitrary observables can be estimated in polynomial time for inverse-polynomial ϵ and δ.The guarantee holds within additive error ϵ∥O∥ with probability at least 1 −δ over circuit randomness.
  • Noise-induced shallow depth: Local noise effectively truncates typical circuits to their last logarithmic-many layers for expectation-value estimation.This generalizes an earlier result beyond circuits composed of two-qubit gates sampled from unitary 2-designs and applies across architectures.
  • Numerical validation: Theoretical bounds are often exceeded in practice: Pauli-path simulation errors are substantially smaller than predicted in amplitude-damping and dephasing experiments.The experiments use a periodic 6×6 lattice, parametrized RX, RZ, and RZZ gates, and a central Pauli-Z observable.
  • Numerical validation: Simulation error decays exponentially with path-weight truncation order, while stronger noise makes circuits easier to simulate on average.For all-zero initial states, mean square errors are orders of magnitude lower than Frobenius-norm errors at the same truncation order.
  • Numerical validation: A real-time amplitude-damping simulation used truncation convergence to support accuracy through approximately t = 0.8 for γ = 0.05.The run used path-weight truncation 30, around 12GB of peak memory, and approximately one hour; stronger-noise systems appeared accurate through t = 0.92.
  • Numerical validation: The real-time numerical regime lacks theoretical accuracy guarantees because its circuit has highly structured, correlated angles.Nevertheless, suitable Pauli-propagation truncations produced accurate results for systems including a quantum critical point.

V. METHODS

The methods rewrite noisy-circuit expectation values as Pauli-path sums and estimate them by propagating observables while truncating paths by weight. Random-gate averaging supplies contraction guarantees that make the truncated computation efficient for broad local-noise models.

  • Circuit assumptions: The analysis assumes independently sampled layers invariant under random single-qubit gates, while allowing more general circuit ensembles beyond the concise Clifford-invariance presentation.The unital-noise result uses approximately scrambling single-qubit gates; the non-unital setting uses single-qubit unitary 1-design invariance.
  • Pauli-path representation: The approach expresses Heisenberg-evolved observables as sums over Pauli paths, each carrying a product of layer-transition coefficients.A path is γ = (P0, P1, ..., PL), with an associated Fourier coefficient formed from successive Pauli-basis transitions.
  • Truncation strategy: The estimator retains only Pauli paths whose path weight is below a cutoff, reducing the exponential path sum to a manageable computation.The truncation order k defines the retained estimator, while paths with larger weight are discarded during iterative propagation.
  • Pauli propagation: Pauli propagation iteratively applies adjoint circuit layers, with non-Clifford unitaries and non-unital noise splitting one Pauli term into multiple paths.Clifford unitaries and Pauli noise preserve a single Pauli path, whereas general layers generate a tree-like path structure.
  • Noise averaging: Random-gate averaging makes arbitrary incoherent noise contract Pauli Frobenius norms on average, including noise that can expand them under individual Heisenberg evolutions.This reproduces the effective suppression pattern needed for Pauli-path truncation and supports the decomposition into an effective depolarizing component plus a residual map.
  • Guarantees: The truncated observable has exponentially decreasing average error with increasing cutoff and can be computed in poly(n)-time when k ∈ O(log(n)) and O contains at most poly(n) Pauli terms.For unital noise, an alternative strategy also gives polynomial runtime when the truncation order scales logarithmically with system size.

VI. OPEN PROBLEMS

The paper identifies open problems involving dense Hamiltonians, classical sampling under arbitrary noise, correlated circuit parameters, and broader noise models. These boundaries concern observable complexity, sampling methods, layer independence, and assumptions about local incoherent noise.

  • Dense Hamiltonians: The main result excludes dense Hamiltonians with long-range interactions because observables containing more than polynomially many Pauli terms can make runtime super-polynomial.The stated polynomial-time guarantee applies when the observable contains polynomially many Pauli terms.
  • Classical sampling: Extending classical sampling from depolarizing to arbitrary noise remains unresolved, because truncated projector estimates can require quasi-polynomial time and non-unital noise lacks anti-concentration.The paper identifies both the truncation cost and the absence of anti-concentration as challenges.
  • Correlated parameters: The analysis assumes independently sampled circuit layers, excluding correlated-parameter circuits such as Trotterized and trained variational circuits.The paper suggests numerical studies may provide insight while theoretical analysis of correlations remains challenging.
  • Alternative noise models: The noise model is restricted to local incoherent noise independent of the applied gate, leaving coherent errors and long-range correlations such as crosstalk for future work.The paper explicitly identifies classical simulability under these alternative noise models as an open direction.

VII. CODE AVAILABILITY

The paper provides an open-source implementation for its numerical simulations and notes that path-weight-truncation extensions are forthcoming.

  • Code availability: Numerical simulations used the open-source PauliPropagation.jl package.The package supported the simulations reported in this work.
  • Code availability: Extensions needed for path-weight truncation were not yet publicly available at the time of writing.The authors stated that these extensions would soon be released.
  • Code availability: The path-weight-truncation extensions could be shared upon request before public release.The authors offered access on request.

2. Ensembles of linear maps and states

The paper introduces linear-map ensembles that support analysis of noisy random circuits without requiring global or local unitary 2-designs. It develops locally unbiased and approximately locally scrambling distributions and relates them to orthogonality and entropy properties.

  • Locally unbiased distributions: Locally unbiased distributions remain invariant under right-multiplication by independent single-qubit unitary 1-designs.This generalizes Pauli-invariance, which requires invariance under random Pauli operators.
  • Orthogonality properties: Local unbiasedness makes Pauli operators with different supports orthogonal in expectation, yielding corresponding identities for arbitrary observables.The result follows from the single-qubit 1-design property and trace preservation.
  • Pauli invariance: Pauli-invariant distributions impose the stronger condition that distinct Pauli operators, not merely different supports, are orthogonal in expectation.Pauli-invariance is equivalent to vanishing second-moment cross terms for every distinct Pauli pair.
  • Approximate local scrambling: Approximately locally scrambling distributions extend local scrambling by allowing controlled deviations from uniform Pauli-direction mixing.Their deviation is quantified through an entropy bound, Dmax(pa∥pu) ≤ log(1 + 2η), and the property is preserved under unitary evolution.

4. The Pauli propagation method

The Pauli propagation framework represents layered quantum-channel evolution as sums over paths through the Pauli basis. Truncation retains a selected subset of paths to approximate state or observable evolution.

  • Pauli-path representation: A layered quantum channel is represented in vectorized form, enabling evolution to be decomposed into transitions between Pauli operators.Each path records a sequence of Pauli operators across the circuit layers.
  • Pauli-path representation: Each Pauli path receives a Fourier coefficient equal to the product of its layer-by-layer transition amplitudes.The coefficient multiplies the transitions from the initial Pauli operator through the final layer.
  • Truncation: The evolved state and observable are expressed as sums over Pauli paths in the Schrödinger and Heisenberg pictures.Approximation is obtained by selecting a subset of paths and forming the associated truncated linear map.

a. Orthogonality of Pauli paths

Orthogonality of Pauli paths provides the central second-moment simplification for random circuits. Locally unbiased layers decorrelate paths with different supports, while Pauli-invariant layers decorrelate all distinct paths.

  • Path structure: A Pauli path is characterized by the supports of its component operators and by the sum of their Pauli weights.These definitions organize paths for the orthogonality analysis.
  • Support orthogonality: Independent locally unbiased layers make Fourier coefficients of paths with different supports uncorrelated.The same conclusion holds when the final adjoint channel is also sampled from a locally unbiased distribution.
  • Full path orthogonality: Independent Pauli-invariant layers make Fourier coefficients of any two distinct Pauli paths uncorrelated.The argument extends the support-based cancellation to paths differing at any Pauli position.

b. Estimating second moments by sampling Pauli paths

The paper estimates second-moment quantities by sampling Pauli paths according to observable- and layer-dependent transition weights. Orthogonality makes variances and truncation errors expressible in a common path-sum form, enabling randomized polynomial-time estimation under suitable sampling assumptions.

  • Path-sum quantities: Variances of expectation values and mean squared truncation errors can both be written as weighted sums over Pauli paths.The weights use the initial state, observable, and selected path subset.
  • Monte Carlo estimation: The Monte Carlo estimator samples the final Pauli operator from the observable coefficients and propagates backward through layer transition distributions.Each sampled path is assigned a normalization factor times a path function.
  • Guarantees: The estimator’s samples lie in [0, 1], allowing Chernoff-Hoeffding concentration to provide precision and confidence guarantees.The runtime depends on the requested precision, confidence, and per-sample sampling cost.
  • Monte Carlo estimation: The estimator is unbiased because the sampling probability cancels the path-weight normalization.The sampled output is λ_j = K(γ) · f(γ), whose expectation equals the target second-moment quantity.
  • Noise and norm contraction: Random-unitary averaging restores Frobenius-norm contraction for traceless observables under arbitrary local noise, including non-unital and dephasing channels.This extends norm-truncation analysis beyond depolarizing noise, despite dephasing invariances and possible norm increases under individual non-unital evolutions.

2. Average-case norm contraction

The paper defines contraction coefficients for local single-qubit noise and shows that random single-qubit gates induce average Frobenius-norm contraction for broad noise classes, including non-unital and dephasing noise.

  • Contraction coefficients: Contraction coefficients quantify how single-qubit channels affect observable norms under local noise.The paper introduces both ordinary and mean-squared contraction coefficients as technical tools for average-case analysis.
  • Depolarizing-like and non-unital noise: For depolarizing-like and non-unital channels, the contraction coefficient is strictly smaller than 1.This strict contraction follows by iterating the single-qubit channel bound.
  • Dephasing noise: Dephasing noise requires approximate scrambling because its contraction can arise only after a Pauli observable spreads into multiple Pauli components.The analysis treats exact unitary 2-designs and approximate scramblers, including the dephasing class.
  • Average contraction: Averaging over tensor products of single-qubit unitary 1-designs prevents the associated linear map from increasing the Frobenius norm on average.The effective depolarizing rate is chosen from the mean-squared contraction coefficient of the noise channel.
  • Circuit assumptions: The noisy-circuit model permits arbitrary non-overlapping O(1)-qubit unitary gates interleaved with local single-qubit noise and random single-qubit layers.The layer distributions satisfy the paper's stated invariance assumptions, with 1-design conditions for the relevant noise classes.

1. Average contraction implies efficient classical simulation

Average Frobenius-norm contraction makes high-weight Pauli paths negligible, while tailored enumeration handles the extra paths created by non-unital noise. This yields polynomial-time estimation for typical noisy circuits.

  • Path-weight suppression: Fourier coefficients of noisy and effectively depolarizing circuits differ by a factor exponential in Pauli-path weight.This proportionality connects path-weight truncation to mean-squared simulation error.
  • Truncation: For arbitrary local noise, truncating Pauli paths by weight controls the mean-squared error through the effective depolarizing rate.The theorem constructs an observable evolution restricted to paths of weight below a cutoff.
  • Non-unital noise: Non-unital noise can create exponentially many additional legal paths, so the unital-noise enumeration bound does not generally apply.Amplitude damping provides a counterexample with at least Ω(n^(k−1)) legal paths in the stated setting.
  • Arbitrary-noise enumeration: If an observable contains M Pauli terms, legal paths of weight at most k number at most M exp(O(k)) and can be enumerated in time Mn exp(O(k)).This modified enumeration argument applies when unitary layers contain non-overlapping 1- and 2-qubit gates.
  • Simulation complexity: For observables with M Pauli terms, a classical algorithm runs in M · poly(n, 1/ϵ, 1/δ) time and achieves additive error ϵ∥O∥F with probability at least 1 −δ.For unital noise with logarithmic-or-greater depth, the runtime is polynomial in n for inverse-polynomial ϵ and δ.

Appendix E: Effective depth of noisy random circuits beyond local 2-designs

Random noisy circuits suppress traceless observable components exponentially with depth on average, so expectation values can be approximated using only an effective logarithmic-depth suffix. Input-state randomness alone cannot provide the same general guarantee under standard complexity assumptions.

  • Effective depth: Average random-unitary evolution exponentially suppresses traceless observable components with circuit depth under local noise.This extends the effective-depth argument beyond ensembles based on local 2-designs.
  • Noise-induced shallow depth: Random noisy circuits can be truncated to an effective depth j ∈ O(log(ϵ^-1δ^-1)) while preserving expectation values with probability at least 1 −δ.The truncated circuit retains the final j layers and the final single-qubit layer.
  • Proof strategy: The effective-depth result follows from bounds on Heisenberg evolution between arbitrary states, not from a specific initial-state preparation.The proof applies the contraction theorem to the truncated circuit and then uses Markov's inequality.
  • Input-state randomness: Using only randomness in input states cannot yield efficient simulation of fixed non-unital noisy circuits if BPP ≠ BQP.The argument uses a reset channel and fault-tolerant computation after O(log(n/ε)) noise-only steps.
  • Reset-channel argument: For the reset-channel construction, the probability that at least one qubit remains unreset is at most n(1 −p)^L.Choosing L = O(log(n/ε)) makes this probability sufficiently small for the reduction.

Appendix G: Additional numerical results

The appendix numerically examines amplitude damping and emphasizes that its absence of barren plateaus makes zero-output heuristics ineffective. Figure 6 studies variance for a 60-qubit bricklayer circuit.

  • Motivation: Amplitude damping is a non-unital setting where observable expectations can have large variances, undermining zero-output simulation strategies.The appendix presents this regime as more challenging than noiseless or depolarizing cases.
  • Figure 6: Figure 6 estimates the variance of a middle-lattice Z expectation value for 60 qubits using 10^6 randomly sampled Pauli paths.The circuit uses a 1D bricklayer RX-RZ-RZZ ansatz, and γ denotes the amplitude damping rate.
Loading 2501.13101v2…