Complexity of tensor network simulation for noisy quantum circuits

arXiv:2606.00474 · cond-mat.str-el, quant-ph · Submitted 2026-05-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai.

Mira: And I'm Mira, here with Lev.

Kai: We're looking at the paper: "Complexity of tensor network simulation for noisy quantum circuits".

Mira: Here's the gist of the paper. Complexity of tensor network simulation for noisy quantum circuits aims to rigorously address how local noise affects classical simulability of quantum dynamics benchmarked by tensor-network methods The results establish a rigorous connection between certain noise models, circuit types, and their classical simulability Operator Entanglement as a Diagnostic Operator entanglement serves as the natural diagnostic for these thresholds Vectorizing a density operator as a pure state in the doubled Hilbert space maps an MPO to an MPS, whose bond dimension across a bipartition is controlled by the entropy of the operator Schmidt coefficients Two distinct entropies are relevant here: the unnormalized operator entanglement SOE, which incorporates purity decay and governs absolute Hilbert-Schmidt truncation, and its purity-rescaled normalized counterpart SeOE, which governs relative-error truncation These two entropies optimally govern the absolute and relative truncation error of the operator Schmidt decomposition, respectively Noise-Dependent Simulation Thresholds The paper establishes several bounds based on noise models and circuit structures For single-qubit depolarizing noise, tensor networks with poly(n) bond dimension suffice for fixed absolute Hilbert-Schmidt error after O(1) depth, while relative error demands O(log n) depth In higher dimensions, these bounds yield uniform-in-depth poly(n) average boundary-bond dimensions for projected entangled pair operators (PEPO) across every cut under depolarizing noise at either absolute or relative accuracy For general single-qubit noise in 1D brickwall circuits, random two-design gates with contraction coefficient c < 1/3 yield an O(1) OEE plateau with probability 1 − T e−omega(n) while arbitrary gates with c < 1/48 give O(log n) OEE in the worst case Whole-Trajectory Simulation and Error Control Proposition 1 ensures that for a noisy trajectory on a one-dimensional local circuit, there exists a sequential approximation with each ρbl having poly(n) bond dimension across the prescribed cut, such that for every l,∥ρl − ρbl∥22 ≤ ε∥ρl∥22 Proposition 4 shows that this sequential MPO trajectory achieves any fixed absolute error tolerance ε ∈ (0, 1) with polynomial bond dimension Worst-Case Analysis and Locality For general single-qubit noise in 1D brickwall circuits, strong contraction (c(N) < 1/48) yields a worst-case logarithmic OEE bound of SOE(ρl) = O(log n) for every choice of gates and every l The analysis using the quantum Wasserstein distance of order 1 allows for bounding the error, leading to a polynomial bond dimension for the approximate state at block endpoints Generalization to Higher Dimensions The results generalize to higher dimensions, yielding uniform-in-depth poly(n) average boundary-bond dimensions for PEPO across every cut under depolarizing noise and general noise with strong contraction at absolute accuracy The local rank bound implies that log χabs∂(A) = O(log n), which means χabs∂(A) = O(poly(n)), uniformly in L The findings establish a rigorous connection between noise, circuits, operator entanglement, and classical simulability This demonstrates that local noise suppresses the operator entanglement relevant to absolute accuracy much earlier than it suppresses the normalized operator entanglement relevant to relative accuracy The entire trajectory can be simulated with polynomial bond dimension under depolarizing noise and logarithmic depth for relative error The analysis provides a unified theory of how dissipation reshapes quantum complexity Key Results Summary 1.

Kai: For single-qubit depolarizing noise, the thresholds are Labs = O(1) for absolute accuracy and Lrel = Θ(log n) for relative error 2.

Mira: For general single-qubit noise in 1D brickwall circuits, strong contraction (c < 1/48) yields a worst-case logarithmic OEE bound of SOE(ρl) = O(log n) for every choice of gates and every l 3.

Kai: For the depolarizing setting, the average PEPO boundary-bond dimensions required to approximate ρL at absolute Hilbert-Schmidt error ε and relative error δ obey log χabs∂(A) = O(log n), log χrel∂(A) = O(log n) 4.

Paper summary: Kai: So we're looking at this paper, "Complexity of tensor network simulation for noisy quantum circuits." It’s tackling how local noise messes with whether we can simulate quantum dynamics using tensor networks. The main idea is connecting certain noise types and circuit structures directly to what makes a problem classically simulable.

Mira: It seems like they’re using operator entanglement entropy, or OEE, as this natural diagnostic tool for those thresholds. They map a density operator onto something called an MPS, which is controlled by the entropy of its Schmidt coefficients across a split in the system.

Lev: So what they're doing is looking at two different types of entanglement—unnormalized operator entanglement, or SOE, and purity-rescaled normalized operator entanglement, or SeOE—and showing how these govern absolute versus relative truncation errors in the decomposition.

Kai: They establish several bounds based on noise models and circuit structures. For example, with single-qubit depolarizing noise on arbitrary circuits, they find that tensor networks with a polynomial bond dimension are enough for fixed absolute Hilbert-Schmidt error after a constant depth of O(one) <ref:2606.00474#pg1,single-qubit depolarizing noise on arbitrary circuits>.

Mira: But then they show that if you want relative error control, you need a logarithmic depth of O(log n). That separation between the two accuracy criteria is something they highlight as really important.

Lev: In higher dimensions, for depolarizing noise on local circuits, the results suggest uniform-in-depth polynomial average boundary bond dimensions for projected entangled pair operators across every cut under either absolute or relative accuracy. That sounds like a strong statement about how stable the simulation complexity is.

Kai: They also look at general single-qubit noise in one dimensional brickwall circuits where they find that random two-design gates with a contraction coefficient less than one over three give an O(one) OEE plateau with probability one minus e to the omega of n <ref:2606.00474#pg1,an O(1) OEE plateau with probability>.

Mira: That means for those specific gate types, you get a good bound on absolute error, but if you want relative error control, you’re looking at something logarithmic in n. And then they mention that arbitrary gates with a contraction coefficient less than one over forty eight give an O(log n) OEE in the worst case.

Paper summary: Lev: When we think about running this on real hardware, these bounds tell us what the overhead really lands on. For general single-qubit noise in one dimensional brickwall circuits, strong contraction with a coefficient of less than one over forty eight yields a worst-case logarithmic bound for SOE of rho L, which is O(log n) for every choice of gates and every layer l.

Kai: That means even in the worst-case scenario for those specific noise conditions, you can still get that logarithmic bound on operator entanglement when you're looking at absolute accuracy. How does that translate to what a person actually experiences?

Mira: It means the noise doesn't destroy the simulation complexity as fast as we might think if we focus on the right measure of entanglement. The paper proves there is a rigorous connection between these specific noise models, circuit types, and their classical simulability.

Lev: For whole trajectory simulation on one dimensional local circuits under depolarizing noise, they show that there exists a sequential approximation where each layer has a polynomial bond dimension across the cut for every layer l. This ensures you can hit any fixed absolute error tolerance epsilon between zero and one with polynomial bond dimension.

Kai: That’s interesting because it suggests that even when things get noisy, we can approximate the whole path of the quantum evolution with manageable complexity if we use this sequential approach.

Mira: The analysis using the quantum Wasserstein distance of order one allows them to bound the error, which leads to a polynomial bond dimension for that approximate state at block endpoints. That’s where you see how they control the total simulation error across time.

Lev: They also generalize these results to higher dimensions, showing uniform-in-depth polynomial average boundary bond dimensions for projected entangled pair operators across every cut under depolarizing noise and general noise with strong contraction at absolute accuracy. The local rank bound implies that the logarithmic scale of alpha delta of A is O(log n), which means alpha delta of A is polynomial in n, uniformly in time.

Paper summary: Kai: So, if we move to higher dimensions, the complexity stays polynomial on average for the relevant operators under these strong noise conditions when looking at absolute error. That's a big statement about scaling behavior.

Mira: The main finding they establish is that local noise suppresses operator entanglement relevant to absolute accuracy much earlier than it suppresses the normalized operator entanglement relevant to relative accuracy. That separation in thresholds is the core of what they’re proving here.

Lev: This suggests that dissipation reshapes quantum complexity in a very specific way, depending on whether you care about the absolute error or just the relative structure simplification. It’s a unified theory for how noise affects simulation difficulty.

Kai: So, to wrap up this paper, "Complexity of tensor network simulation for noisy quantum circuits," they rigorously connect the dots between noise models and classical simulability using operator entanglement entropy as their primary measure.

Mira: The authors demonstrate that local noise has a distinct effect on absolute versus relative accuracy thresholds, setting concrete bounds like labs equals O(one) for absolute error after one layer of depolarizing noise <ref:2606.00474#pg1>.

Lev: For the practical side, they show that whole trajectory simulation can be achieved with polynomial bond dimension under depolarizing noise and logarithmic depth if you are aiming for relative error control.

Kai: What this means for the field is that we have a clearer map showing exactly which circuit structures and noise types allow for efficient classical simulation using tensor networks. It sets clear complexity boundaries based on the physical properties of the noise itself.

Mira: The paper suggests that understanding these thresholds might help us figure out which specific noise features—like fixed points or anisotropy—are what actually simplify classical simulation in a real noisy environment.

Lev: Future work should look at those channel-level features, and also extending this operator entanglement framework beyond the full density operator to tasks involving just expectation values of a few observables. That would make it directly relevant for near-term applications.

Conclusion: Kai: So we're wrapping up on this paper, "Complexity of tensor network simulation for noisy quantum circuits." It’s about figuring out exactly when simulating quantum dynamics with tensor networks becomes too hard because of noise.

Mira: Yeah, the title itself is a bit heavy, but what it means plainly is they’re mapping out the boundary between what’s classically possible and what requires serious overhead from those tensor network methods when noise gets involved.

Lev: For me, the authors are smart for connecting these things—noise models to circuit types and then directly to that entanglement measure. It's not just theoretical; they’re giving us a roadmap for how much effort we need.

Kai: Right, so they're showing that local noise doesn't just mess up everything equally; it has a specific effect on the relevant entanglement depending on whether you care about absolute error or relative error.

Mira: That separation is key. They’re proving that the way noise messes with the simulation complexity changes fundamentally depending on whether you are looking at how accurate your absolute result is versus how much the structure itself simplifies.

Lev: And from where I stand, this means we can start thinking about specific noise channels—like depolarizing noise or those strong contraction ones—and know upfront if our simulation will run in polynomial time or if we're going to hit a wall.

Kai: Exactly. It gives us concrete benchmarks for what kind of circuit structure and what kind of noise allows for a manageable simulation complexity, which is super useful when you’re actually building hardware.

Mira: It moves the conversation past just saying "noisy circuits are hard" to specifying *how* they are hard, linking it to these operator entanglement metrics.

Lev: So, the big picture here is that we now have a rigorous way to connect physical noise properties and circuit geometry directly to the complexity of classical simulation, which helps us design better error-corrected protocols.

Kai: It sets a new standard for how we measure the difficulty of simulating quantum evolution under real-world noisy conditions.

Mira: And it opens up questions about those specific noise structures, like fixed points or anisotropy, that might actually simplify the complexity phase diagram further.

Lev: We'll take those channel-level features next to see if they offer any shortcuts for running on actual quantum hardware.

Yuguo Shao, Zishuo Zhao, Song Cheng, Zhengwei Liu

Yau Mathematical Sciences Center Tsinghua University · Beijing Institute of Mathematical Sciences and Applications Department of Mathematics Tsinghua University

cond-mat.str-el, quant-ph

Submitted: 2026-05-30

Updated: 2026-11-04

Comments: 43 pages, 3 figures

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 97/100

The gist: Complexity of tensor network simulation for noisy quantum circuits aims to rigorously address how local noise affects classical simulability of quantum dynamics benchmarked by tensor-network methods…

Key concepts

Operator Entanglement
This measures how entangled a quantum state is by treating it as a pure state in a larger space. It is used to diagnose the limitations of tensor network approximations, specifically determining how much information needs to be kept (the bond dimension) to accurately represent the quantum dynamics.
SOE and SeOE
These are two different ways to measure operator entanglement. SOE focuses on absolute error truncation, which relates to Hilbert-Schmidt norms. SeOE is purity-rescaled and governs relative error truncation, which is more relevant when dealing with small errors in the simulation.
Poly(n) Bond Dimension
This refers to a bond dimension that grows polynomially with the system size 'n'. The paper shows that under certain noise conditions, approximating the quantum state requires a polynomial bond dimension for absolute accuracy, meaning classical simulation remains tractable up to this limit.
Contraction Coefficient (c)
This parameter describes how much entanglement is lost during gate operations in 1D brickwall circuits. Strong contraction (c < 1/48) leads to a worst-case logarithmic bound on operator entanglement, indicating that even with strong noise, the required simulation resources remain relatively low.

Terminology

Summary

Complexity of tensor network simulation for noisy quantum circuits aims to rigorously address how local noise affects classical simulability of quantum dynamics benchmarked by tensor-network methods The results establish a rigorous connection between certain noise models, circuit types, and their classical simulability

Operator Entanglement as a Diagnostic

Operator entanglement serves as the natural diagnostic for these thresholds Vectorizing a density operator as a pure state in the doubled Hilbert space maps an MPO to an MPS, whose bond dimension across a bipartition is controlled by the entropy of the operator Schmidt coefficients Two distinct entropies are relevant here: the unnormalized operator entanglement SOE, which incorporates purity decay and governs absolute Hilbert-Schmidt truncation, and its purity-rescaled normalized counterpart SeOE, which governs relative-error truncation These two entropies optimally govern the absolute and relative truncation error of the operator Schmidt decomposition, respectively

Noise-Dependent Simulation Thresholds

The paper establishes several bounds based on noise models and circuit structures For single-qubit depolarizing noise, tensor networks with poly(n) bond dimension suffice for fixed absolute Hilbert-Schmidt error after O(1) depth, while relative error demands O(log n) depth In higher dimensions, these bounds yield uniform-in-depth poly(n) average boundary-bond dimensions for projected entangled pair operators (PEPO) across every cut under depolarizing noise at either absolute or relative accuracy For general single-qubit noise in 1D brickwall circuits, random two-design gates with contraction coefficient c < 1/3 yield an O(1) OEE plateau with probability 1 − T e−omega(n) while arbitrary gates with c < 1/48 give O(log n) OEE in the worst case

Whole-Trajectory Simulation and Error Control

Proposition 1 ensures that for a noisy trajectory on a one-dimensional local circuit, there exists a sequential approximation with each ρbl having poly(n) bond dimension across the prescribed cut, such that for every l,∥ρl − ρbl∥22 ≤ ε∥ρl∥22 Proposition 4 shows that this sequential MPO trajectory achieves any fixed absolute error tolerance ε ∈ (0, 1) with polynomial bond dimension

Worst-Case Analysis and Locality

For general single-qubit noise in 1D brickwall circuits, strong contraction (c(N) < 1/48) yields a worst-case logarithmic OEE bound of SOE(ρl) = O(log n) for every choice of gates and every l The analysis using the quantum Wasserstein distance of order 1 allows for bounding the error, leading to a polynomial bond dimension for the approximate state at block endpoints

Generalization to Higher Dimensions

The results generalize to higher dimensions, yielding uniform-in-depth poly(n) average boundary-bond dimensions for PEPO across every cut under depolarizing noise and general noise with strong contraction at absolute accuracy The local rank bound implies that log χabs∂(A) = O(log n), which means χabs∂(A) = O(poly(n)), uniformly in L

Conclusion on Complexity

The findings establish a rigorous connection between noise, circuits, operator entanglement, and classical simulability This demonstrates that local noise suppresses the operator entanglement relevant to absolute accuracy much earlier than it suppresses the normalized operator entanglement relevant to relative accuracy The entire trajectory can be simulated with polynomial bond dimension under depolarizing noise and logarithmic depth for relative error The analysis provides a unified theory of how dissipation reshapes quantum complexity

Key Results Summary

  1. For single-qubit depolarizing noise, the thresholds are Labs = O(1) for absolute accuracy and Lrel = Θ(log n) for relative error

  2. For general single-qubit noise in 1D brickwall circuits, strong contraction (c < 1/48) yields a worst-case logarithmic OEE bound of SOE(ρl) = O(log n) for every choice of gates and every l

  3. For the depolarizing setting, the average PEPO boundary-bond dimensions required to approximate ρL at absolute Hilbert-Schmidt error ε and relative error δ obey log χabs∂(A) = O(log n), log χrel∂(A) = O(log n)

  4. For the worst-case PEPO boundary dimension under strong contraction, log χabs∂(A) = O(log n), χabs∂(A) = O(poly(n)), uniformly in time

Further Research Directions

Future work could explore channel-level features—fixed points, anisotropy, contraction directions—that dissipate operator entanglement would clarify which noise structures simplify classical simulation The OEE framework also needs to extend beyond the full density operator to fewobservable tasks, for instance, shallow tomography where only expectation values of a handful of observables are needed before it becomes directly relevant to near-term applications Identifying whether the thresholds c = 1/3 and c = 1/48 are fundamental would map out a sharper complexity phase diagram for noisy dynamics The paper assumes i.i.d.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Polynomial bond dimension simulation for noisy quantum circuits: AI systems can simulate 1D local circuits with fixed absolute error in O(log n) depth using a poly(n) bond dimension MPO, which is a significant reduction compared to noiseless simulation.

  2. Adaptive error control for trajectory simulation: AI systems can implement sequential approximations where the relative error tolerance epsilon is maintained throughout a long trajectory by repeatedly applying compression steps that contract residual errors by depolarizing noise, ensuring the final approximation has polynomial bond dimension.

  3. Worst-case entanglement barrier detection: AI systems can analyze noise channel parameters like the contraction coefficient c(N) to determine if an O(1) operator entanglement plateau will be achieved or if a logarithmic worst-case bound is necessary for simulation complexity.

  4. Cutwise PEPO boundary estimation: For higher dimensional systems, AI systems can estimate the average boundary-bond dimension across any arbitrary cut by leveraging the relationship between operator entanglement and projected entangled pair operators (PEPOs), providing bounds like log chi abs∂(A) = O(log n).

  5. Noise-robust state characterization: AI systems can use normalized operator entanglement entropy SeOE to bound the difference between two quantum states based on their L2 distance, allowing for the characterization of entanglement structure under noisy evolution.

Sources

Related papers