Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2605.18943

Noise-induced Simulability Transition from Operator Scrambling

Neil Dowling, Xhek Turkeshi, Jacopo De Nardis, Guglielmo Lami

quant-phcond-mat.stat-mechSubmitted May 18, 2026• Announced May 20, 2026• 0 citations
arXivHTMLPDF

Abstract

The complexity of simulating quantum many-body dynamics, or quantum computations, in the Heisenberg picture is governed by the scrambling of initially simple operators into superpositions of exponentially many Pauli strings. The corresponding expansion coefficients define the Pauli spectrum, whose structure controls the performance of classical algorithms based on truncating Pauli expansions. Here we determine the finite-depth Pauli spectrum of random quantum circuits, both in the noiseless case and in the presence of local noise, through its moments, given by the operator stabilizer Rényi entropies. In noiseless circuits, we uncover a hierarchy in the approach to the fully scrambled regime: low moments equilibrate at relatively short depths, while higher moments, which are sensitive to rare, large-amplitude Pauli coefficients, require parametrically larger depths. In noisy circuits, scrambling competes with an effective suppression of operator spreading. Above a critical error per cycle $γ_c N=\mathcal{O}(1)$, the operator fails to reach the fully scrambled distribution and remains supported on an atypically sparse subset of Pauli strings. Conversely, below this scale, we rigorously show that classical simulation remains exponentially hard, demonstrating that finite noise does not automatically imply classical simulability. The resulting noise-induced transition in operator complexity therefore delineates the boundary between intrinsically hard quantum dynamics and those that remain classically accessible.

Comments
7+5 pages, 6 figures

Related papers

Complex Quantum Dynamics Versus Classical Simulability of Noisy Random Circuits

Anjali Waghmare, Sergii Strelchuk, Sathyawageeswar Subramanian

Claims of quantum advantage rest on the classical hardness of simulating quantum circuits. Magic, operator scrambling, anticoncentration, and non-Gaussianity for fermionic circuits are standard diagnostics of complex quantum dynamics. For pure states, some of these have been rigorously connected to classical simulability. Whether these diagnostics reliably track the limits of efficient classical simulation under noise remains unclear. Here, we show that in noisy Clifford+$T$ and nearest-neighbour matchgate+SWAP circuits, dynamical diagnostics and classical simulability can separate in both directions. In particular, the diagnostics can remain nontrivial after classical simulation becomes efficient, or become trivial before known efficient classical algorithms apply. We trace this mismatch to the different statistical properties they probe: magic and scrambling depend on fourth-order statistics of the Pauli spectrum, whereas the simulation algorithms depend primarily on second-order moments, which local noise suppresses at different rates. Thus, dynamical diagnostics measured on a noisy quantum device do not by themselves constitute evidence for classical hardness.

quant-pharXiv:2609.39734•Oct 1, 2026•0 citations

Classical Simulation Healed by Quantum Entanglement

Jue Xu, Chu Zhao, Xiangran Zhang +2 more

Entanglement is not only the origin of exotic quantum phenomena, but also widely regarded as the fundamental barrier to classical simulation of quantum dynamics. We overturn this intuition: for predicting local observables under Hamiltonian evolution, entanglement in the quantum state actually heals the classical simulation error in the Heisenberg picture. Classical algorithms that propagate observables in the Pauli basis with proper truncation have shown remarkable empirical success in simulating noiseless quantum dynamics, yet all prior rigorous guarantees required noise or randomness---leaving the physically relevant noiseless regime without theoretical foundation. To close this gap, we prove that the truncation error of Low-weight Pauli Dynamics (LPD) admits an average-case bound without assuming randomness, provided the state is sufficiently entangled. Since tensor-network methods efficiently simulate low-entanglement states while LPD thrives precisely in the complementary regime, together they extend rigorous classical simulation to longer times, sharpening the boundary between classically simulable and genuinely quantum dynamics.

quant-pharXiv:2601.15770•Jan 23, 2026•0 citations

Complexity of tensor network simulation for noisy quantum circuits

Yuguo Shao, Zishuo Zhao, Song Cheng +1 more

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^{-Ω(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.

cond-mat.str-elCross-listedarXiv:2606.00474•Jun 2, 2026•0 citations

Characterizing Pauli propagation via operator complexity

Yuguo Shao, Song Cheng, Zhengwei Liu

Pauli-propagation simulation represents observables in the Pauli basis and evolves their coefficients in the Heisenberg picture. In this work, we bridge operator complexity and the resource cost of Pauli-propagation methods by proving that the truncation error is governed by the Operator Stabilizer Rényi entropy (OSE) $${{{\mathcal{S}}}}^{\alpha }(O)$$. Our bounds quantify how OSE controls the compressibility of the evolving operator and give explicit prescriptions for the Top-K budget required to achieve a target accuracy. As an analytic test case, we prove that for the 1D Heisenberg model at Jz = 0, the number of non-zero Pauli coefficients generated from a local operator grows at most quadratically with the number of Trotter steps. We then benchmark the Top-K Pauli propagation on XXZ Heisenberg chains. The numerical results show high accuracy with a small truncation number K in the free regime (Jz = 0) and competitive performance against tensor-network methods, such as TDVP, in the interacting case (Jz = 0.5). These results position OSE as a resource measure for Pauli-propagation methods. Classical simulations of quantum dynamics are often limited by rapidly growing entanglement, motivating observable-based methods. Here, the authors show that operator stabilizer entropy gives a priori error bounds for Pauli propagation and determines the Pauli-term budget needed to reach a target accuracy.

arXiv:2510.22311•Communications Physics•Jul 27, 2026•0 citations

Simulating Noisy Variational Quantum Algorithms: A Polynomial Approach

Yuguo Shao, Fuchuan Wei, Song Cheng +1 more

Large-scale variational quantum algorithms are widely recognized as a potential pathway to achieve practical quantum advantages. However, the presence of quantum noise might suppress and undermine these advantages, which blurs the boundaries of classical simulability. To gain further clarity on this matter, we present a novel polynomial-scale method based on the path integral of observable's backpropagation on Pauli paths (OBPPP). This method efficiently approximates expectation values of operators in variational quantum algorithms with bounded truncation error in the presence of single-qubit Pauli noise. Theoretically, we rigorously prove: (i) For a constant minimal nonzero noise rate γ, OBPPP's time and space complexity exhibit a polynomial relationship with the number of qubits n, the circuit depth L. (ii) For variable γ, in scenarios where more than two nonzero noise factors exist, the complexity remains Poly(n,L) if γ exceeds 1/logL, but grows exponential with L when γ falls below 1/L. Numerically, we conduct classical simulations of IBM's zero-noise extrapolated experimental results on the 127-qubit Eagle processor [Y. Kim et al., Evidence for the utility of quantum computing before fault tolerance, Nature (London) 618, 500 (2023).NATUAS0028-083610.1038/s41586-023-06096-3]. Our method attains higher accuracy and faster runtime compared to the quantum device. Furthermore, our approach allows us to simulate noisy outcomes, enabling accurate reproduction of IBM's unmitigated results that directly correspond to raw experimental observations. Our research reveals the vital role of noise in classical simulations and the derived method is general in computing the expected value for a broad class of quantum circuits and can be applied in the verification of quantum computers.

arXiv:2306.05804•Physical Review Letters•Sep 18, 2024•31 citations

Quantum Circuits with Classically Simulable Operator Scrambling

Mike Blake, Noah Linden

We introduce a new family of quantum circuits for which the scrambling of a subspace of nonlocal operators is classically simulable. We call these circuits "super-Clifford circuits" since the Heisenberg time evolution of these operators corresponds to Clifford evolution in operator space. Thus we are able to classically simulate the time evolution of certain single Pauli strings into operators with operator entanglement that grows linearly with the number of qubits. These circuits provide a new technique for studying scrambling in systems with a large number of qubits, and are an explicit counter example to the intuition that classical simulability implies the absence of scrambling.

arXiv:2002.12824•Physical Review Letters•Jul 15, 2020•6 citations
The complexity of simulating quantum many-body dynamics, or quantum computations, in the Heisenberg picture is governed by the scrambling of initially simple operators into superpositions of exponentially many Pauli strings. The corresponding expansion coefficients define the Pauli spectrum, whose structure controls the performance of classical algorithms based on truncating Pauli expansions. Here we determine the finite-depth Pauli spectrum of random quantum circuits, both in the noiseless case and in the presence of local noise, through its moments, given by the operator stabilizer Rényi entropies. In noiseless circuits, we uncover a hierarchy in the approach to the fully scrambled regime: low moments equilibrate at relatively short depths, while higher moments, which are sensitive to rare, large-amplitude Pauli coefficients, require parametrically larger depths. In noisy circuits, scrambling competes with an effective suppression of operator spreading. Above a critical error per cycle γcN=O(1)γ_c N=\mathcal{O}(1)γc​N=O(1), the operator fails to reach the fully scrambled distribution and remains supported on an atypically sparse subset of Pauli strings. Conversely, below this scale, we rigorously show that classical simulation remains exponentially hard, demonstrating that finite noise does not automatically imply classical simulability. The resulting noise-induced transition in operator complexity therefore delineates the boundary between intrinsically hard quantum dynamics and those that remain classically accessible.
Claims of quantum advantage rest on the classical hardness of simulating quantum circuits. Magic, operator scrambling, anticoncentration, and non-Gaussianity for fermionic circuits are standard diagnostics of complex quantum dynamics. For pure states, some of these have been rigorously connected to classical simulability. Whether these diagnostics reliably track the limits of efficient classical simulation under noise remains unclear. Here, we show that in noisy Clifford+TTT and nearest-neighbour matchgate+SWAP circuits, dynamical diagnostics and classical simulability can separate in both directions. In particular, the diagnostics can remain nontrivial after classical simulation becomes efficient, or become trivial before known efficient classical algorithms apply. We trace this mismatch to the different statistical properties they probe: magic and scrambling depend on fourth-order statistics of the Pauli spectrum, whereas the simulation algorithms depend primarily on second-order moments, which local noise suppresses at different rates. Thus, dynamical diagnostics measured on a noisy quantum device do not by themselves constitute evidence for classical hardness.
Entanglement is not only the origin of exotic quantum phenomena, but also widely regarded as the fundamental barrier to classical simulation of quantum dynamics. We overturn this intuition: for predicting local observables under Hamiltonian evolution, entanglement in the quantum state actually heals the classical simulation error in the Heisenberg picture. Classical algorithms that propagate observables in the Pauli basis with proper truncation have shown remarkable empirical success in simulating noiseless quantum dynamics, yet all prior rigorous guarantees required noise or randomness---leaving the physically relevant noiseless regime without theoretical foundation. To close this gap, we prove that the truncation error of Low-weight Pauli Dynamics (LPD) admits an average-case bound without assuming randomness, provided the state is sufficiently entangled. Since tensor-network methods efficiently simulate low-entanglement states while LPD thrives precisely in the complementary regime, together they extend rigorous classical simulation to longer times, sharpening the boundary between classically simulable and genuinely quantum dynamics.
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 poly(n)\mathrm{poly}(n)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 poly(n)\mathrm{poly}(n)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/3c<1/3c<1/3 yield an $\order{1}$ OEE plateau with probability 1−Te−Ω(n)1-Te^{-Ω(n)}1−Te−Ω(n), while arbitrary gates with c<1/48c<1/48c<1/48 give $\order{\log n}$ OEE in the worst case. (4) In higher dimensions, these bounds yield uniform-in-depth poly(n)\mathrm{poly}(n)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.
Pauli-propagation simulation represents observables in the Pauli basis and evolves their coefficients in the Heisenberg picture. In this work, we bridge operator complexity and the resource cost of Pauli-propagation methods by proving that the truncation error is governed by the Operator Stabilizer Rényi entropy (OSE) Sα(O){{{\mathcal{S}}}}^{\alpha }(O)Sα(O). Our bounds quantify how OSE controls the compressibility of the evolving operator and give explicit prescriptions for the Top-K budget required to achieve a target accuracy. As an analytic test case, we prove that for the 1D Heisenberg model at Jz = 0, the number of non-zero Pauli coefficients generated from a local operator grows at most quadratically with the number of Trotter steps. We then benchmark the Top-K Pauli propagation on XXZ Heisenberg chains. The numerical results show high accuracy with a small truncation number K in the free regime (Jz = 0) and competitive performance against tensor-network methods, such as TDVP, in the interacting case (Jz = 0.5). These results position OSE as a resource measure for Pauli-propagation methods. Classical simulations of quantum dynamics are often limited by rapidly growing entanglement, motivating observable-based methods. Here, the authors show that operator stabilizer entropy gives a priori error bounds for Pauli propagation and determines the Pauli-term budget needed to reach a target accuracy.
Large-scale variational quantum algorithms are widely recognized as a potential pathway to achieve practical quantum advantages. However, the presence of quantum noise might suppress and undermine these advantages, which blurs the boundaries of classical simulability. To gain further clarity on this matter, we present a novel polynomial-scale method based on the path integral of observable's backpropagation on Pauli paths (OBPPP). This method efficiently approximates expectation values of operators in variational quantum algorithms with bounded truncation error in the presence of single-qubit Pauli noise. Theoretically, we rigorously prove: (i) For a constant minimal nonzero noise rate γ, OBPPP's time and space complexity exhibit a polynomial relationship with the number of qubits n, the circuit depth L. (ii) For variable γ, in scenarios where more than two nonzero noise factors exist, the complexity remains Poly(n,L) if γ exceeds 1/logL, but grows exponential with L when γ falls below 1/L. Numerically, we conduct classical simulations of IBM's zero-noise extrapolated experimental results on the 127-qubit Eagle processor [Y. Kim et al., Evidence for the utility of quantum computing before fault tolerance, Nature (London) 618, 500 (2023).NATUAS0028-083610.1038/s41586-023-06096-3]. Our method attains higher accuracy and faster runtime compared to the quantum device. Furthermore, our approach allows us to simulate noisy outcomes, enabling accurate reproduction of IBM's unmitigated results that directly correspond to raw experimental observations. Our research reveals the vital role of noise in classical simulations and the derived method is general in computing the expected value for a broad class of quantum circuits and can be applied in the verification of quantum computers.
We introduce a new family of quantum circuits for which the scrambling of a subspace of nonlocal operators is classically simulable. We call these circuits "super-Clifford circuits" since the Heisenberg time evolution of these operators corresponds to Clifford evolution in operator space. Thus we are able to classically simulate the time evolution of certain single Pauli strings into operators with operator entanglement that grows linearly with the number of qubits. These circuits provide a new technique for studying scrambling in systems with a large number of qubits, and are an explicit counter example to the intuition that classical simulability implies the absence of scrambling.