Complexity of tensor network simulation for noisy quantum circuits

Song Cheng; Yuguo Shao; Zhengwei Liu; Zishuo Zhao

arxiv: 2606.00474 · v1 · pith:5QSBWNGNnew · submitted 2026-05-30 · ❄️ cond-mat.str-el · quant-ph

Complexity of tensor network simulation for noisy quantum circuits

Yuguo Shao , Zishuo Zhao , Song Cheng , Zhengwei Liu This is my paper

Pith reviewed 2026-06-28 18:27 UTC · model grok-4.3

classification ❄️ cond-mat.str-el quant-ph

keywords tensor network simulationnoisy quantum circuitsoperator entanglement entropymatrix product operatorsprojected entangled pair operatorsclassical simulabilitydepolarizing noise

0 comments

The pith

Single-qubit depolarizing noise lets poly(n)-bond tensor networks simulate arbitrary circuits to fixed absolute error after constant depth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that local depolarizing noise limits operator entanglement growth enough for tensor networks to approximate circuit evolution with only polynomial bond dimension. For arbitrary circuits this suffices at constant depth for fixed absolute Hilbert-Schmidt error and at logarithmic depth for relative error, with matching lower bounds. One-dimensional circuits admit polynomial-bond matrix product operators that bound error across the full trajectory at every depth. In higher dimensions the same noise yields polynomial average boundary bond dimensions for projected entangled pair operators, uniformly in depth.

Core claim

For single-qubit depolarizing noise, tensor networks with polynomial bond dimension achieve fixed absolute Hilbert-Schmidt error on arbitrary circuits after order-1 depth, while relative error requires order-log-n depth; the bound is tight. One-dimensional local circuits admit whole-trajectory error-bounded matrix product operators of polynomial bond dimension at every depth. General single-qubit noise with contraction coefficient below 1/3 yields constant operator entanglement entropy with high probability on random gates, and below 1/48 yields logarithmic growth in the worst case. Higher-dimensional circuits then support uniform-in-depth polynomial average boundary bond dimensions in proje

What carries the argument

Operator entanglement entropy (OEE), serving as a proxy that upper-bounds the minimal bond dimension needed to keep Hilbert-Schmidt simulation error below a fixed threshold.

If this is right

Polynomial bond dimension suffices for absolute-error simulation of noisy arbitrary circuits after constant depth.
Relative-error simulation of the same circuits requires only logarithmic depth.
In one dimension, polynomial-bond MPOs bound error for the entire trajectory at all depths.
Higher-dimensional PEPOs have polynomial average boundary bonds uniformly in depth under depolarizing or sufficiently contracting noise.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The separation between absolute and relative error suggests that practical simulation thresholds depend on the chosen accuracy measure.
The OEE plateau under strong contraction may extend to other local noise channels beyond the depolarizing case.
The 1D whole-trajectory result could be tested by constructing explicit MPO representations for small noisy circuits and measuring truncation error growth.

Load-bearing premise

The analysis assumes the noise is single-qubit depolarizing or has contraction coefficient below explicit thresholds, and that operator entanglement entropy accurately tracks the bond dimension required to control error.

What would settle it

An explicit family of circuits with single-qubit depolarizing noise in which the operator entanglement entropy grows faster than any polynomial at constant depth while absolute error remains fixed would falsify the poly(n) sufficiency claim.

Figures

Figures reproduced from arXiv: 2606.00474 by Song Cheng, Yuguo Shao, Zhengwei Liu, Zishuo Zhao.

**Figure 2.** Figure 2: The maximum operator entanglement entropy [PITH_FULL_IMAGE:figures/full_fig_p016_2.png] view at source ↗

**Figure 3.** Figure 3: Schematic of a 1D circuit with nearest-neighbor two-qubit gates and noise applied after each layer of unitary gates. [PITH_FULL_IMAGE:figures/full_fig_p036_3.png] view at source ↗

read the original abstract

We aim to rigorously address how local noise affects classical simulability of quantum dynamics benchmarked by tensor-network methods. Using operator entanglement entropy (OEE), we prove the following: (1) For single-qubit depolarizing noise on arbitrary circuits, tensor networks with $\mathrm{poly}(n)$ bond dimension suffice for fixed absolute Hilbert-Schmidt error after $\order{1}$ depth, while relative error demands $\order{\log n}$ depth; and this bound is optimal. (2) For single-qubit depolarizing noise on 1D local circuits, the existence of whole-trajectory error-bounded matrix product operator (MPO) of $\mathrm{poly}(n)$ bond dimension at all depths. (3) For general single-qubit noise in 1D brickwall circuits, random two-design gates with contraction coefficient $c<1/3$ yield an $\order{1}$ OEE plateau with probability $1-Te^{-\Omega(n)}$, while arbitrary gates with $c<1/48$ give $\order{\log n}$ OEE in the worst case. (4) In higher dimensions, these bounds yield uniform-in-depth $\mathrm{poly}(n)$ average boundary-bond dimensions for projected entangled pair operators~(PEPO) across every cut -- under depolarizing noise at either absolute or relative accuracy, and under general noise with strong contraction at absolute accuracy. Our results establish a rigorous connection between certain noise models, circuit types, and their classical simulability.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives explicit, optimal depth thresholds showing when single-qubit depolarizing noise makes arbitrary circuits tensor-network simulable to fixed absolute error after constant depth.

read the letter

The central result is that for single-qubit depolarizing noise on any circuit, poly(n) bond dimension suffices for constant absolute Hilbert-Schmidt error after O(1) depth, while relative error needs O(log n) depth, and both bounds are claimed optimal. For 1D brickwall circuits the same noise model yields whole-trajectory error-bounded MPOs of poly(n) bond dimension at every depth. These statements rest on operator entanglement entropy controlling the required bond dimension under explicit contraction coefficients.

The proofs appear to apply standard contraction arguments to the noisy operator evolution and then convert OEE bounds into bond-dimension statements. The extension to general single-qubit noise with c < 1/3 or c < 1/48, and the higher-dimensional average-boundary claims for PEPOs, are the parts that go beyond earlier tensor-network simulability work. The optimality statements are the clearest addition.

The main limitation is that everything is conditioned on the noise being single-qubit depolarizing (or a general channel with sufficiently strong contraction). If the physical noise deviates from that model the thresholds do not apply. The translation from OEE to actual simulation error also assumes the usual worst-case relations between entanglement and bond dimension; any looseness there would affect the constants but not the scaling. No circularity or post-hoc fitting is visible.

The paper is for people who need rigorous depth cutoffs when deciding whether a noisy circuit is still classically tractable. Anyone working on tensor-network methods for open quantum systems or on the practical limits of quantum advantage will get direct use from the bounds. It is mathematically grounded enough to merit referee time even if the proofs turn out to need tightening on the error constants.

Referee Report

0 major / 3 minor

Summary. The manuscript proves several bounds on tensor-network simulability of noisy quantum circuits using operator entanglement entropy (OEE) as the key quantity. For single-qubit depolarizing noise on arbitrary circuits, poly(n) bond dimension suffices to achieve fixed absolute Hilbert-Schmidt error after O(1) depth while relative error requires O(log n) depth, and both bounds are claimed optimal. For 1D local circuits the same noise model admits whole-trajectory error-bounded MPOs of poly(n) bond dimension at all depths. For general single-qubit noise on 1D brickwall circuits, contraction coefficient thresholds (c < 1/3 for random two-design gates, c < 1/48 for arbitrary gates) imply O(1) or O(log n) OEE plateaus with high probability. In higher dimensions the same noise assumptions yield uniform-in-depth poly(n) average boundary-bond dimensions for PEPOs.

Significance. If the proofs are correct, the work supplies the first rigorous, noise-model-specific guarantees that link local noise strength directly to polynomial classical simulability via tensor networks, including optimality statements and high-probability results for random gates. The explicit contraction-coefficient thresholds and the distinction between absolute versus relative error are technically useful. The connection between OEE and minimal bond dimension follows standard tensor-network reasoning and is applied here to both MPOs and PEPOs.

minor comments (3)

The abstract and introduction should explicitly define 'whole-trajectory error-bounded' and state whether the error is measured in the Heisenberg or Schrödinger picture.
Notation for the contraction coefficient c is introduced in claim (3) but its precise relation to the depolarizing channel parameter should be stated once in a dedicated preliminary section.
Figure captions for any OEE-vs-depth plots should include the precise circuit ensemble, noise strength, and number of samples used to generate the high-probability statements.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment and recommendation of minor revision. The provided summary accurately captures the key results on operator entanglement entropy bounds, optimality statements, and implications for MPO/PEPO simulability under local noise. As the report lists no specific major comments, we have no points requiring point-by-point rebuttal or revision at this stage.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper presents explicit mathematical proofs that bound tensor-network bond dimensions via operator entanglement entropy under stated assumptions on single-qubit depolarizing or contractive noise and on circuit locality. These bounds are derived from contraction properties and standard OEE-to-bond-dimension relations rather than from any fitted parameter renamed as a prediction, self-defined quantity, or load-bearing self-citation chain. The abstract and summarized argument contain no reduction of the central claims to their own inputs by construction; the results remain conditional on external, falsifiable noise-model parameters and follow conventional tensor-network reasoning without internal circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard properties of quantum channels and entropy measures; no free parameters or new entities are introduced in the abstract.

axioms (2)

domain assumption Operator entanglement entropy bounds the minimal bond dimension required for a given simulation error
Invoked throughout the four numbered results as the bridge between noise and tensor-network size.
domain assumption Depolarizing noise and brickwall circuit contraction coefficients behave as stated in the theorems
Core modeling choice for all four claims.

pith-pipeline@v0.9.1-grok · 5802 in / 1462 out tokens · 23617 ms · 2026-06-28T18:27:56.006715+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

15 extracted references

[1]

Property of the purity-controlled bound Here we present some useful properties of the maximum operator entanglement entropyS max OE (t) and eSmax OE (t). Some people might be concerned that the purity upper bound for normalized operator entanglement entropy eSOE(ρ) is trivial, as it is purity dependent while in the definition, the purity scale has been no...
[2]

Similarly result is also true for operator Schmidt decomposition, as shown by the following lemma

Operator entanglement entropy with tail control Eckart-Young theorem [44] states that the best rank-rapproximation of a matrixMin terms of the Frobenius norm is given by the sum of the firstrsingular values and corresponding singular vectors ofM. Similarly result is also true for operator Schmidt decomposition, as shown by the following lemma. Lemma 3(Eck...
[3]

Operator entanglement and mutual information Whenρis a pure state, we have eSOE(ρ) = 2S(A)ρ,(C61) whereS(A) ρ =−tr{ρ A logρ A}is the von Neumann entropy of the reduced density matrixρ A = tr B{ρ}. We now generalize this relation to mixed states, obtaining the following inequality: Theorem 9.For any bipartite stateρof systemABwith purityt= tr ρ2 , the norm...
[4]

22 Lemma 7.LetP={p i}m i=1 andQ={q i}m i=1 be two non-negative sequence, witht P =Pm i=1 pi andt Q =Pm i=1 qi both less than or equal to1

Continuity bound of Operator Entanglement In this section, we establish the following continuity bound on the difference in operator entanglement entropy between two bipartite quantum states in terms of theirl 2 distance. 22 Lemma 7.LetP={p i}m i=1 andQ={q i}m i=1 be two non-negative sequence, witht P =Pm i=1 pi andt Q =Pm i=1 qi both less than or equal t...
[5]

For ann-qubit stateρ, if each qubit undergoes independent depolarizing noise channel, the overall noise channel can be expressed asN ⊗n(ρ)

Purity decay under depolarizing noise We first consider single-qubit depolarizing noise channel defined as: N(σ) = (1−λ)σ+λ I 2 ,(D1) whereλ∈[0,1] is the depolarizing probability andσis a single-qubit state. For ann-qubit stateρ, if each qubit undergoes independent depolarizing noise channel, the overall noise channel can be expressed asN ⊗n(ρ). For an-qu...
[6]

Lemma 10(OEE bounds from hypercontractivity).Assume that the input state is pure, and fix a bipartitionA|B

Operator entanglement bounds under depolarizing noise Combining the hypercontractive purity estimate with the purity-controlled OEE bound (theorem 6) gives the following bounds for the OEE. Lemma 10(OEE bounds from hypercontractivity).Assume that the input state is pure, and fix a bipartitionA|B. Let nmin = min{|A|,|B|}, x L = (1−λ) 2L, α L = 1−x L 1 +x L...
[7]

Sincen δ logngrows faster than lognfor every fixedδ >0, the normalized OEE is super- logarithmic throughout the window (D60)

By monotonicity offand by (D77), f(x L)≥f(y n)≥ 3 2 yn log2 1 yn = 3 2 n−(1−δ)(1−δ) log 2 n.(D79) Combining this with (D59) yields eSOE(ρL) = n 2 f(x L)≥ 3 4(1−δ)n δ log2 n,(D80) which proves (D61). Sincen δ logngrows faster than lognfor every fixedδ >0, the normalized OEE is super- logarithmic throughout the window (D60). This establishes the claimed Θ(l...
[8]

Fix a cut of the chain and a relative error toleranceε∈(0,1)

Efficient whole-trajectory simulation for 1D noisy circuits Proposition 4(Whole-trajectory noisy circuit simulation at fixed error (proposition 1 in the main text)).Consider ann-qubit noisy trajectory on a one-dimensional architecture, ρℓ =D ⊗n λ ◦ Uℓ(ρℓ−1), ρ 0 =|0⟩ ⟨0|⊗n ,(D81) whereλ∈(0,1)is a fixed depolarizing strength,U ℓ(·) =U ℓ(·)U † ℓ , and eachU...
[9]

Single-qubit noise Here we consider the general single qubit noise channelN. Using the following lemma, we can obtain the normal form of single-qubit noise channels: Lemma 11(Normal form of a quantum channel [37, 38]).Any single-qubit quantum channelNcan be brought into a canonical form via pre- and post-unitary rotations such that N(·) =UN ′(V †(·)V)U †,...
[10]

Auxiliary orbit state Here we consider a specific case that the quantm system is arranged in a 1D chain and the unitary evolution is given by a circuit with nearest-neighbor two-qubit gates, and the noise is applied to each qubit after each layer of unitary gates, as illustrated in fig. 3. Formally, we denote theℓ-th layer of unitary gates asU ℓ, which is...
[11]

Specifically, we consider a random circuit that the two-qubit gates in each layer of the circuit are drawn independently from a 2-design distribution

Average case analysis In this section, we consider the average case, which means that the unitary gates in the circuit are drawn from random distribution, and we analyze the average behavior of the operator entanglement entropy under the effect of noise. Specifically, we consider a random circuit that the two-qubit gates in each layer of the circuit are d...
[12]

Using the quantum Wasserstein distance of order 1 introduced in Ref

Worst case analysis In this section, we provide a worst-case analysis of the effect of general noise on the operator entanglement entropy. Using the quantum Wasserstein distance of order 1 introduced in Ref. [50]. Unlike other more commonly used distance measures such as the trace distance and the fidelity, the quantum Wasserstein distance of order 1 aren...
[13]

Proof.By lemma 21, we have∥N − E∥ ⋄ ≤ √ 3c 1− √ 3c

If the initial stateρis a product state, then the output stateρ ℓ = Φ(ρ)satisfies SOE(ρℓ) =O(logn),∀ℓ≥0.(E70) Moreover, for any arbitrary input stateρ, there exists a cross-over depthL ∗ =O(logn)such that for allℓ≥L ∗, the above bound holds. Proof.By lemma 21, we have∥N − E∥ ⋄ ≤ √ 3c 1− √ 3c. Therefore, imposingc < 1 48 implies∥N − E∥ ⋄ < 1
[14]

DefineL ∗ to be the smallest integer such that 2n(3η) L∗ < 1 4, whereη=∥N − E∥ ⋄. Then we haveL ∗ =O(log 2 n), and by theorem 12 we have for allℓ≥L ∗, SOE(ρℓ)−S OE(σ(L∗) ℓ ) ≤4n(3η) L∗ (2 min{nA, nB}+ 2) +h(4n(3η) L∗) +η(4n(3η) L∗)≤ O(log 2 n).(E71) By lemma 13, the auxiliary orbit stateσ (L∗) ℓ has operator entanglement entropyS OE(σ(L∗) ℓ ) upper bounde...
[15]

If the initial stateρis a product state, then the output stateρ ℓ = Φ(ρ)satisfies SOE(ρℓ) =O(logn),∀ℓ≥0.(E79) Moreover, for any arbitrary input stateρ, there exists a cross-over timeL ∗ =O(logn)such that for allℓ≥L ∗, the above bound holds. Appendix F: Generalization to higher-dimension This section makes precise the cut-rank and average bond dimension st...

[1] [1]

Property of the purity-controlled bound Here we present some useful properties of the maximum operator entanglement entropyS max OE (t) and eSmax OE (t). Some people might be concerned that the purity upper bound for normalized operator entanglement entropy eSOE(ρ) is trivial, as it is purity dependent while in the definition, the purity scale has been no...

[2] [2]

Similarly result is also true for operator Schmidt decomposition, as shown by the following lemma

Operator entanglement entropy with tail control Eckart-Young theorem [44] states that the best rank-rapproximation of a matrixMin terms of the Frobenius norm is given by the sum of the firstrsingular values and corresponding singular vectors ofM. Similarly result is also true for operator Schmidt decomposition, as shown by the following lemma. Lemma 3(Eck...

[3] [3]

Operator entanglement and mutual information Whenρis a pure state, we have eSOE(ρ) = 2S(A)ρ,(C61) whereS(A) ρ =−tr{ρ A logρ A}is the von Neumann entropy of the reduced density matrixρ A = tr B{ρ}. We now generalize this relation to mixed states, obtaining the following inequality: Theorem 9.For any bipartite stateρof systemABwith purityt= tr ρ2 , the norm...

[4] [4]

22 Lemma 7.LetP={p i}m i=1 andQ={q i}m i=1 be two non-negative sequence, witht P =Pm i=1 pi andt Q =Pm i=1 qi both less than or equal to1

Continuity bound of Operator Entanglement In this section, we establish the following continuity bound on the difference in operator entanglement entropy between two bipartite quantum states in terms of theirl 2 distance. 22 Lemma 7.LetP={p i}m i=1 andQ={q i}m i=1 be two non-negative sequence, witht P =Pm i=1 pi andt Q =Pm i=1 qi both less than or equal t...

[5] [5]

For ann-qubit stateρ, if each qubit undergoes independent depolarizing noise channel, the overall noise channel can be expressed asN ⊗n(ρ)

Purity decay under depolarizing noise We first consider single-qubit depolarizing noise channel defined as: N(σ) = (1−λ)σ+λ I 2 ,(D1) whereλ∈[0,1] is the depolarizing probability andσis a single-qubit state. For ann-qubit stateρ, if each qubit undergoes independent depolarizing noise channel, the overall noise channel can be expressed asN ⊗n(ρ). For an-qu...

[6] [6]

Lemma 10(OEE bounds from hypercontractivity).Assume that the input state is pure, and fix a bipartitionA|B

Operator entanglement bounds under depolarizing noise Combining the hypercontractive purity estimate with the purity-controlled OEE bound (theorem 6) gives the following bounds for the OEE. Lemma 10(OEE bounds from hypercontractivity).Assume that the input state is pure, and fix a bipartitionA|B. Let nmin = min{|A|,|B|}, x L = (1−λ) 2L, α L = 1−x L 1 +x L...

[7] [7]

Sincen δ logngrows faster than lognfor every fixedδ >0, the normalized OEE is super- logarithmic throughout the window (D60)

By monotonicity offand by (D77), f(x L)≥f(y n)≥ 3 2 yn log2 1 yn = 3 2 n−(1−δ)(1−δ) log 2 n.(D79) Combining this with (D59) yields eSOE(ρL) = n 2 f(x L)≥ 3 4(1−δ)n δ log2 n,(D80) which proves (D61). Sincen δ logngrows faster than lognfor every fixedδ >0, the normalized OEE is super- logarithmic throughout the window (D60). This establishes the claimed Θ(l...

[8] [8]

Fix a cut of the chain and a relative error toleranceε∈(0,1)

Efficient whole-trajectory simulation for 1D noisy circuits Proposition 4(Whole-trajectory noisy circuit simulation at fixed error (proposition 1 in the main text)).Consider ann-qubit noisy trajectory on a one-dimensional architecture, ρℓ =D ⊗n λ ◦ Uℓ(ρℓ−1), ρ 0 =|0⟩ ⟨0|⊗n ,(D81) whereλ∈(0,1)is a fixed depolarizing strength,U ℓ(·) =U ℓ(·)U † ℓ , and eachU...

[9] [9]

Single-qubit noise Here we consider the general single qubit noise channelN. Using the following lemma, we can obtain the normal form of single-qubit noise channels: Lemma 11(Normal form of a quantum channel [37, 38]).Any single-qubit quantum channelNcan be brought into a canonical form via pre- and post-unitary rotations such that N(·) =UN ′(V †(·)V)U †,...

[10] [10]

Auxiliary orbit state Here we consider a specific case that the quantm system is arranged in a 1D chain and the unitary evolution is given by a circuit with nearest-neighbor two-qubit gates, and the noise is applied to each qubit after each layer of unitary gates, as illustrated in fig. 3. Formally, we denote theℓ-th layer of unitary gates asU ℓ, which is...

[11] [11]

Specifically, we consider a random circuit that the two-qubit gates in each layer of the circuit are drawn independently from a 2-design distribution

Average case analysis In this section, we consider the average case, which means that the unitary gates in the circuit are drawn from random distribution, and we analyze the average behavior of the operator entanglement entropy under the effect of noise. Specifically, we consider a random circuit that the two-qubit gates in each layer of the circuit are d...

[12] [12]

Using the quantum Wasserstein distance of order 1 introduced in Ref

Worst case analysis In this section, we provide a worst-case analysis of the effect of general noise on the operator entanglement entropy. Using the quantum Wasserstein distance of order 1 introduced in Ref. [50]. Unlike other more commonly used distance measures such as the trace distance and the fidelity, the quantum Wasserstein distance of order 1 aren...

[13] [13]

Proof.By lemma 21, we have∥N − E∥ ⋄ ≤ √ 3c 1− √ 3c

If the initial stateρis a product state, then the output stateρ ℓ = Φ(ρ)satisfies SOE(ρℓ) =O(logn),∀ℓ≥0.(E70) Moreover, for any arbitrary input stateρ, there exists a cross-over depthL ∗ =O(logn)such that for allℓ≥L ∗, the above bound holds. Proof.By lemma 21, we have∥N − E∥ ⋄ ≤ √ 3c 1− √ 3c. Therefore, imposingc < 1 48 implies∥N − E∥ ⋄ < 1

[14] [14]

DefineL ∗ to be the smallest integer such that 2n(3η) L∗ < 1 4, whereη=∥N − E∥ ⋄. Then we haveL ∗ =O(log 2 n), and by theorem 12 we have for allℓ≥L ∗, SOE(ρℓ)−S OE(σ(L∗) ℓ ) ≤4n(3η) L∗ (2 min{nA, nB}+ 2) +h(4n(3η) L∗) +η(4n(3η) L∗)≤ O(log 2 n).(E71) By lemma 13, the auxiliary orbit stateσ (L∗) ℓ has operator entanglement entropyS OE(σ(L∗) ℓ ) upper bounde...

[15] [15]

If the initial stateρis a product state, then the output stateρ ℓ = Φ(ρ)satisfies SOE(ρℓ) =O(logn),∀ℓ≥0.(E79) Moreover, for any arbitrary input stateρ, there exists a cross-over timeL ∗ =O(logn)such that for allℓ≥L ∗, the above bound holds. Appendix F: Generalization to higher-dimension This section makes precise the cut-rank and average bond dimension st...