Simulating quantum circuits with arbitrary local noise using Pauli Propagation

• Hardware noise creates a central tension: it can simplify classical simulation while encouraging circuits that are less noise-sensitive but more classically tractable [6] [9] [10] [11] [12].Depolarizing noise drives unmeasured circuits rapidly toward the maximally mixed state, whereas dephasing and non-unital noise require different analysis.Source: §I · pp. 1–2
• The authors show that most circuits with arbitrary incoherent local noise admit polynomial-time estimation of observable expectation values to inversely polynomial precision.The guarantee holds when each circuit layer is sampled from a distribution invariant under single-qubit random gates, including non-unital and dephasing noise.Source: §I · p. 2
• The framework assumes only non-unitary single-qubit noise with constant rate, also allowing dynamic non-unitary operations applied at a constant rate [40].It combines Pauli-path simulation with a normal-form representation of local noise [16] [30] [35] [37].Source: §I · p. 2
• Inversely polynomial error can be achieved in polynomial time for all circuit topologies, extending prior precision guarantees beyond one-dimensional connectivity.This accuracy is relevant to physically motivated tasks such as estimating extensive quantities including molecular ground-state energies.Source: §I · pp. 2–3
• The method works for less random circuit ensembles using unitary 1-designs for non-unital or depolarizing-like noise and approximate unitary 2-designs for dephasing noise.Under the same assumptions, incoherent noise reduces observable estimation to an effective logarithmic depth, generalizing Ref. [37].Source: §I · p. 3
• Numerical simulations on 6 × 6 and 11 × 11 lattices show that path-weight-truncated Pauli propagation can outperform analytic accuracy guarantees and remain reasonably efficient beyond the theory’s random-circuit assumptions.The experiments use amplitude damping and dephasing, including a 121-qubit noisy dynamical simulation.Source: §I · p. 3

General local noise model

• Any single-qubit channel admits a normal form with arbitrary unitary rotations and parameters D and t, where unitality is determined by whether t vanishes [35] [37].The model defines constant noise rate through 1/3||D||_2^2 being strictly below one.Source: §II · p. 3
• The framework distinguishes depolarizing-like channels driving states toward the maximally mixed state, dephasing-like channels preserving one Bloch-sphere diameter, and non-unital channels driving states toward another fixed point.Amplitude damping exemplifies non-unital noise, with parameters D=(√(1−γ),√(1−γ),1−γ) and t=(0,0,γ), fixing the computational zero state.Source: §II · pp. 3–4, Figure 2 · p. 4

Random local noise circuit models

• The task is estimating Tr[OC(ρ)] for arbitrary initial states and bounded Hermitian observables, where C is an L-layer noisy random circuit with local noise and non-overlapping O(1)-qubit gates.Random layers and the final single-qubit layer are independently sampled from distributions invariant up to second moment under right-multiplication by random single-qubit gates.Source: §II · p. 4

Locally unbiased circuits

• Locally unbiased layers, sampled from unitary 1-designs, permit efficient classical simulation even when the circuit noise is non-unital.This setting generalizes ensembles invariant under right-multiplication by random Pauli unitaries.Source: §II · p. 4

Approximately locally scrambling circuits

• Approximately locally scrambling layers support efficient classical simulation under arbitrary local noise, including dephasing-like channels.The framework extends unitary 2-design assumptions and includes arbitrary unitaries preceded by two consecutive random Pauli rotations along orthogonal directions [39].Source: §II · pp. 4–5

Noise beyond depolarization

• Prior work shows that carefully designed circuits under non-unital or dephasing noise can remain hard to simulate, despite noise enabling fault-tolerant computation in some regimes [35].Non-unital noise supports computation for Θ(exp(n)) time below threshold, while dephasing supports arbitrary quantum computation for polynomial time.Source: §III · p. 5
• For random circuits, arbitrary local noise induces an effectively logarithmic depth for observable estimation, enabling quasi-polynomial or polynomial simulation depending on circuit locality [37].The present work extends this phenomenon to broader random-circuit classes and achieves inversely polynomial precision in polynomial time across architectures.Source: §III · p. 5

Pauli propagation under noise

• Pauli propagation previously achieved polynomial-time, inverse-polynomial-precision simulation for depolarizing-noise circuits, including output sampling, observable estimation, and random-input settings [13, 15, 29, 16].Worst-case extensions cover sufficiently deep depolarizing circuits, shallow Clifford-dominated circuits, and nearly maximally mixed inputs [30].Source: §III · p. 5
• Prior non-unital extensions include effectively depolarizing spontaneous-emission models [16] and randomized Pauli Propagation for Clifford circuits with Pauli rotations and amplitude damping [47].This work provides a unified treatment of arbitrary local noise, including non-unital and dephasing-like noise, across several noisy random-circuit classes.Source: §III · pp. 5–6

Noiseless Pauli-path methods

• Unlike Ref. [39], which truncates Pauli operators by weight, the present algorithm truncates Pauli paths by path weight, yielding a significantly lower runtime for inverse-polynomial precision in noisy circuits.Ref. [39] established polynomial or quasi-polynomial simulation for noiseless random circuits, with almost-polynomial improvements under geometric locality and poly-logarithmic depth.Source: §III · p. 6

Broader Pauli-path applications

• Pauli-path methods also efficiently simulate noiseless near-Clifford circuits and have been applied numerically to Hamiltonian simulation, QCNNs, and linear cross-entropy benchmarking [48] [49] [50] [6] [52] [39] [53].Table I compares prior and present runtimes for estimating observable expectation values under different noise models and average-case assumptions.Source: §III · p. 6, Table I · p. 6

Theoretical guarantees

• Assuming local, non-unital noise with constant noise rate, the noisy expectation value Tr[OC(ρ)] is classically estimable in time M · poly(n, ϵ−1, δ−1), within error ϵ∥O∥, with probability 1 −δ.The result applies to independently sampled circuit layers whose distribution is invariant under single-qubit unitary 1-designs; average-case assumptions exclude schemes such as the “quantum refrigerator” [35].Source: §IV · pp. 6–7
• For unital, including dephasing-like, local noise, the same runtime applies to arbitrary observables, under approximately scrambling single-qubit gate ensembles.If depth is at least logarithmic in n, the estimate remains polynomial-time for inverse-polynomial ϵ and δ; the result improves prior quasi-polynomial scaling and relates efficient simulation to absent barren plateaus [37] [54].Source: §IV · p. 7

Noise-induced shallow depth

• Local noise effectively reduces typical noisy circuits to their last O(log(1/ϵ)) layers for estimating expectation values, extending prior truncation results [37].Combined with logarithmic-depth simulation results [39, 55], this yields polynomial-time simulation across architectures rather than only almost-polynomial scaling for fixed geometric dimension.Source: §IV · p. 7

Numerical implementation

• In periodic 6×6 Hamiltonian variational circuits on 36 qubits, average simulation error is often significantly smaller than theoretical bounds for amplitude-damping noise.The simulations use RX, RZ, and RZZ rotation gates, a central Pauli-Z observable, and the all-zero initial state; the circuit ensemble lacks local 2-designs required by Refs. [37] [39].Source: §IV · p. 8
• At a quantum critical point, noisy simulations converged as algorithmic truncations were loosened; for γ = 0.05, path-weight truncation 30 was trusted to approximately t = 0.8, using 12GB and one hour.Higher-noise cases with γ = 0.1 and 0.2 appeared accurate until the final time t = 0.92.Source: §IV · pp. 8–9
• These real-time results extend beyond the theoretical guarantees because the circuit has correlated angles, yet suitable truncations still produce accurate results at criticality.The benchmark uses second-order Trotterization with dt = 0.04 and up to 23 steps, comparing convergence against the resource-intensive noise-free setup motivated by Ref. [58].Source: §IV · p. 9

Pauli-path analysis

• The analysis assumes circuit-layer distributions invariant under random single-qubit Clifford gates, while noting that broader ensembles require more detailed analysis.This assumption is used to present the methods and proof ideas concisely.Source: §V · p. 10
• The Heisenberg-evolved observable is expanded over Pauli paths, each weighted by products of layer-transition coefficients, and paths are truncated by a cutoff k.The resulting estimator retains only low path-weight contributions to control the otherwise exponential path sum.Source: §V · pp. 10–11

The Pauli propagation algorithm

• The iterative Pauli propagation algorithm branches when non-Clifford unitaries or non-unital noise split Pauli terms, then discards paths exceeding the weight cutoff.For polynomially many observable terms and logarithmic k, this keeps the runtime polynomial in system size.Source: §V · p. 11

Intuitive explanation of theoretical guarantees

• Random-gate averaging makes arbitrary incoherent noise contract Pauli operators in Frobenius norm, exponentially suppressing contributions according to Pauli weight.This extends the depolarizing-noise intuition to non-unital channels through an effective averaged contraction.Source: §V · p. 12
• The average truncation error decreases exponentially with k, while the truncated observable is computable in poly(n)-time for k ∈ O(log(n)) and observables containing at most poly(n) Pauli terms.These guarantees apply under the random-gate averaging framework used for the arbitrary-noise analysis.Source: §V · p. 12

Estimating “dense” Hamiltonians under non-unital noise

• Dense Hamiltonians with long-range interactions remain outside the polynomial-time guarantee because their Pauli-term count can make runtime super-polynomial.Theorem 1 covers observables with polynomially many Pauli terms and precision poly(n−1)∥H∥F on most circuits; if ℓ∈ω(1), H contains nω(1) terms.Source: §VI · p. 12

Classically sampling under arbitrary noise

• Extending classical sampling from depolarizing to arbitrary noise remains unresolved because non-unital noise causes quasi-polynomial truncation costs and eliminates anti-concentration.The algorithms of Ref. use Θ(log(n)) truncation for projector expectations, while random circuits with non-unital noise do not exhibit anti-concentration [36].Source: §VI · p. 13

Circuits with correlated parameters

• The analysis assumes independently sampled layers, leaving correlated-parameter circuits such as Trotterized and variational circuits as a significant theoretical challenge.Training updates in variational algorithms break parameter independence, while numerical studies such as Fig. 5 may provide insight into classical simulability.Source: §VI · p. 13

Alternative noise models

• Determining classical simulability under coherent, gate-dependent, or long-range-correlated noise remains an important direction beyond the current local incoherent, gate-independent models.Examples include cross-talk errors [62].Source: §VI · p. 13

VII. CODE AVAILABILITY

• Numerical simulations use the open-source PauliPropagation.jl package, while path-weight-truncation extensions are forthcoming and available upon request.Source: §VII · p. 13

1. Notation

• The notation introduces [n], expectations over distributions, and independently sampled product distributions.Source: §1 · p. 17
• Operators on n qubits are vectorized by mapping |i⟩⟨j| to |i⟩⊗|j⟩, providing a representation in H_n⊗2.Source: §1 · p. 17
• Linear maps, including quantum channels, are represented by matrices whose products encode composition and whose adjoints correspond to adjoint matrices.Source: §1 · p. 18
• The Pauli basis P_n={I,X,Y,Z}⊗n describes channels through transition amplitudes collected in a 4^n × 4^n Pauli Transfer Matrix, with support and weight counting non-identity factors.Source: §1 · p. 18
• The preliminaries define Schatten p-norms, trace and Hilbert-Schmidt norms, the infinity norm, and normalized Frobenius or Pauli 2-norms for operators.Source: §1 · pp. 18–19
• For normalized operator identities, the notation also introduces the flip, or SWAP, operator F.Source: §1 · p. 19

2. Ensembles of linear maps and states

• Locally unbiased map ensembles remain invariant under single-qubit unitary 1-designs, generalizing Pauli-invariant distributions and enabling analysis without global or local unitary 2-design assumptions.The framework is motivated as a tool for studying noisy random circuits under weaker ensemble assumptions.Source: §2 · pp. 19–20
• Locally unbiased ensembles make Pauli operators with different supports orthogonal in expectation, while Pauli invariance is equivalent to orthogonality for every distinct Pauli pair.These properties also induce corresponding vanishing relations for arbitrary observables.Source: §2 · pp. 20–21
• Approximate local scrambling controls Pauli-weight distributions through Dmax(pa∥pu) <= log(1 + 2η) and is preserved under unitary evolution by data processing.Two-axis Pauli rotations provide an η = 1/4 example, whereas single-axis rotations are neither approximate scramblers for η < 1 nor unitary 1-designs.Source: §2 · pp. 23–25
• Low-average state ensembles generalize state 1-designs and provide bounds on observable second moments through their average-purity parameter c [16].Unitary 1-design evolution of any state produces a low-average ensemble with purity 1.Source: §2 · p. 25

3. Noise channels

• Single-qubit noise is modeled as N^⊗n, characterized in the Pauli basis, and decomposed into unitary factors plus a six-parameter non-unitary normal form with diagonal coefficients D and identity-to-Pauli terms t.The analysis excludes purely unitary noise and begins classifying non-unitary unital channels, including the depolarizing class.Source: §3 · p. 26
• Non-unitary unital single-qubit noise belongs to either the depolarizing or dephasing class, while non-unital noise has a nonzero translation vector and can increase operator purity.Depolarizing noise converges to the maximally mixed state, whereas dephasing noise converges to states on a Bloch-sphere diameter; non-unital noise converges to a non-maximally mixed state.Source: §3 · p. 26

P DP + |bP tP |sgn(DP ) . (A82)

• The analysis derives a constraint on the normal-form parameters D and t for arbitrary single-qubit channels.The proof constructs an observable O and state ρ from coefficients maximizing the relevant bound, shows ∥O∥∞ = 1, and applies Hölder’s inequality together with properties of D and x^2 ≤ x for |x| ≤ 1.Source: §3 · p. 27, P DP + |bP tP |sgn(DP ) . (A82) · p. 28

• Pauli Propagation represents an L-layered quantum circuit as a quantum channel and its vectorized matrix form.Source: §4 · p. 28
• Each Pauli path γ = (P0, P1, P2, . . . , PL) has Fourier coefficient Φγ(C) given by the product of layer-to-layer Pauli transition amplitudes.Source: §4 · p. 29
• The Schrödinger- and Heisenberg-evolved operators are expressed as sums over Pauli paths, which can be approximated by retaining a suitable subset A and its truncated linear map.Source: §4 · p. 29
• The adjoint of the truncated map C_A is also considered.Source: §4 · p. 29

a. Orthogonality of Pauli paths

• Pauli paths are categorized by their component supports and by the sum of their component Pauli weights.These quantities are formalized as path support and path weight.Source: a. Orthogonality of Pauli paths · p. 29
• Under independent locally unbiased layers, with the adjoint final layer also locally unbiased, paths with different supports have uncorrelated Fourier coefficients.For distinct supports, the expected coefficient product is zero.Source: a. Orthogonality of Pauli paths · pp. 29–30
• Under independent Pauli-invariant layers, with the adjoint final layer also Pauli invariant, distinct Pauli paths have uncorrelated Fourier coefficients.The expected product of coefficients for different paths is zero.Source: a. Orthogonality of Pauli paths · pp. 29–30
• The orthogonality proof selects a layer where two paths differ and uses the corresponding local-unbiased or Pauli-invariant averaging, including the final adjoint layer when needed.Linearity of expectation and the trace then yields a zero expected coefficient product.Source: a. Orthogonality of Pauli paths · p. 30

b. Estimating second moments by sampling Pauli paths

• Pauli-invariant channel ensembles make distinct Pauli-path Fourier coefficients uncorrelated, enabling efficient estimation of several associated second-moment quantities.This assumption is the structural basis for the path-sampling analysis and includes the general Pauli-path functional framework.Source: b. Estimating second moments by… · p. 31
• The estimator applies to variances of expectation values and mean squared errors, which can be expressed as second moments of functions over Pauli paths.Orthogonality of distinct Pauli paths converts these quantities into path-function averages, including errors from restricting the path set and normalized Frobenius-norm errors.Source: b. Estimating second moments by… · pp. 31–32
• Theorem 4 gives a classical randomized algorithm that estimates Pauli-path functionals with precision ϵ and failure probability δ under efficient path-sampling assumptions.The estimator samples the final Pauli according to observable-dependent weights, propagates backward through layer-dependent transition distributions, and has runtime determined by the sampling cost and the required number of samples.Source: b. Estimating second moments by… · p. 32
• The randomized procedure samples PL and successively samples Pi−1, then outputs λj = K(γ) · f(γ), yielding an unbiased estimator for the target value F(Dcirc).Source: b. Estimating second moments by… · pp. 32–33

Appendix B: Technical Lemmas for noisy random channels

• Appendix B introduces technical tools for studying how noise affects random quantum circuits.These tools support the analysis of noisy random channels used throughout the paper.Source: Appendix B · p. 33

1. Motivation: bounding the Frobenius norm under Heisenberg evolution

• Dephasing can leave observables supported on {I, Z}⊗n invariant, while non-unital amplitude damping can increase the Frobenius norm under Heisenberg evolution.Thus, norm-truncation arguments based solely on pointwise contraction do not generally extend beyond depolarizing noise.Source: §1 · p. 34
• Despite these counterexamples, averaging over random unitaries makes the adjoint of any local noise channel contract the Frobenius norm of every traceless observable.The result covers potentially non-unital and dephasing noise and generalizes prior bounds requiring local or global unitary 2-designs to a broader class of circuit ensembles.Source: §1 · p. 34

2. Average-case norm contraction

• Average-case contraction coefficients are defined for single-qubit channels and relate directly to Frobenius-norm contraction under random single-qubit gates.The framework includes ordinary and mean-squared contraction coefficients relative to a distribution over U(2).Source: §2 · pp. 34, 35, 37, 38
• Any single-qubit channel has contraction coefficient at most 1, with strict contraction for depolarizing-like or non-unital noise.The strict-contraction condition is expressed through the channel’s normal-form parameters, while the broader result gives the universal upper bound.Source: §2 · p. 35
• Approximately scrambling single-qubit evolution also yields contraction for dephasing noise, including exact simplifications when the gate distribution is a unitary 2-design.This extends contraction analysis beyond channels whose normal-form parameter bound is already strictly below 1.Source: §2 · pp. 36–37

3. Effective depolarizing rate of noisy random channels

• For arbitrary local noise, an effective depolarizing decomposition can be chosen with p = 1 − χ_D(N), ensuring the associated linear map does not increase Frobenius norm in expectation over a single-qubit 1-design.The result extends the phenomenon previously identified for a specific non-unital noise model to any noise channel under unitary 1-design averaging.Source: §3 · p. 39

Appendix C: Noisy circuit model

• The noisy circuit model consists of n-qubit unitary layers interleaved with local single-qubit noise and a final single-qubit gate layer.Unitary layers use non-overlapping O(1)-qubit gates, while the single-qubit gate distributions are assumed to be 1-designs; extensions allow layer- or qubit-dependent distributions and noise channels.Source: Appendix C · pp. 40–41
• The final unitary layer is optional, and any additional terminal local noise can be absorbed into the measured observable through the adjoint channel.This preserves the applicability of the circuit formulation when the physical circuit ends with noise rather than a final gate layer.Source: Appendix C · p. 40

Appendix D: Classical simulation of noisy random circuits

• The simulation approximates a Heisenberg-evolved observable by retaining only Pauli paths whose total weight is below a fixed truncation threshold k.The construction tracks path amplitudes through Fourier coefficients for both the physical noisy circuit and the depolarizing channels removed via a non-physical linear map.Source: Appendix D · pp. 41–42

Average contraction

• Fourier coefficients obey Φγ(C) = (1 −p)^|γ| Φγ(˜C), while the averaged map ˜C does not increase the Frobenius norm under Heisenberg evolution.Combining this proportionality with Pauli-path orthogonality controls contributions from paths beyond the weight cutoff.Source: §1 · pp. 42–43

Mean squared error

• Theorem 5 establishes mean-squared-error control for observables obtained by restricting Heisenberg evolution to Pauli paths below a weight cutoff.The bound uses path orthogonality, exponential coefficient suppression, and non-increasing average Frobenius norm.Source: §1 · pp. 43–44

Arbitrary-noise enumeration

• Non-unital noise can create Ω(n^(k−1)) legal paths, invalidating the unital counting bound and motivating the modified arbitrary-noise enumeration.The counterexample uses amplitude damping with a k-local Hamiltonian observable.Source: §1 · pp. 44–45
• Lemma 13 bounds legal Pauli paths of weight at most k by M exp(O(k)) and enumerates them in time Mn exp(O(k)) for arbitrary noise.The result assumes each unitary layer contains non-overlapping 1- and 2-qubit gates and the observable has M Pauli terms.Source: §1 · p. 45

Time complexity

• Theorem 6 gives a classical algorithm running in M · poly(n, 1/ϵ, 1/δ) for arbitrary local noise and observables containing M Pauli terms.It approximates Tr[OC(ρ)] within additive error ϵ∥O∥F with probability at least 1 −δ over the circuit choice.Source: §1 · p. 47
• For unital noise and logarithmic-or-greater depth, the runtime becomes polynomial in n for inverse-polynomial ϵ and δ.The approximation retains additive error ϵ∥O∥F with probability at least 1 −δ.Source: §1 · p. 47

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

• On average over random unitaries, the Frobenius norm of an observable’s traceless components is exponentially suppressed under noisy Heisenberg evolution.This extends the result of Ref. [37] to the broader circuit classes studied here.Source: Appendix E · p. 47
• Theorem 7 establishes the observable-suppression bound for all observables, which underlies the effective-depth corollary.The corollary follows by applying Theorem 7 to the truncated channel and using Markov’s inequality.Source: Appendix E · pp. 48–49
• The same suppression framework yields a corollary for the trace distance between noisy evolutions.The trace-distance statement is obtained from the observable bound and Hilbert–Schmidt norm identities.Source: Appendix E · p. 48
• Random noisy circuits can be truncated to effective logarithmic depth when estimating expectation values, with high probability over circuit choice.The truncation retains only a suitable suffix of depth j ∈ O(log(ε^-1δ^-1)).Source: Appendix E · pp. 48–49

Appendix F: Necessity of the random circuit assumption

• If BPP ≠ BQP, no efficient classical algorithm can simulate non-unital noisy circuits using fixed circuits and randomness only over input states.The impossibility holds with high probability over the sampled input-state distribution.Source: Appendix F · p. 49
• The impossibility follows by combining a non-unital probabilistic reset channel with fault-tolerant compilation of arbitrary circuits from Ref. [35].After waiting O(log(n/ε)) steps, the noise drives the initially random state close enough to the reset state for the assumed simulator to solve a BQP-complete task.Source: Appendix F · pp. 49–50
• For the reset channel, the probability that at least one of n qubits remains unreset after L steps is at most n(1 − p)^L.Choosing L = O(log(n/ε)) makes this failure probability sufficiently small for the reduction.Source: Appendix F · p. 50

• Non-unital noise such as amplitude damping is therefore a more demanding simulation setting than noiseless or depolarizing noise, where outputting zero can suffice.Source: Appendix G · p. 50
• Amplitude damping makes zero-output simulation ineffective because observable expectation values have large variances from the absence of barren plateaus [37].This absence was established for local 2-design circuits and is also observed in the paper’s ansatz, which does not satisfy those assumptions.Source: Appendix G · p. 50
• Figure 6 confirms the absence of barren plateaus under amplitude damping in a 60-qubit 1D bricklayer circuit using RX-RZ-RZZ gates.The plotted Z-expectation variance was estimated with 10^6 randomly sampled Pauli paths via Theorem 4.Source: Appendix G · p. 50, Figure 6 · p. 51