Noise-induced Simulability Transition from Operator Scrambling

• URL: http://arxiv.org/abs/2605.18943v1
• Date: Mon, 18 May 2026 18:00:00 GMT
• Title: Noise-induced Simulability Transition from Operator Scrambling
• Abstract summary: We study the finite-depth Pauli spectrum of random quantum circuits.<n>In noisy circuits, scrambling competes with an effective suppression of operator spreading.<n>We rigorously show that classical simulation remains exponentially hard.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Wavelength-Uniform Quantum Algorithms for Quantum Dynamics [39.740772144144366]
  We develop a quantum algorithm for it all ranges of wavelengths. Specifically, it has a it complexity in spatial dimension, and discretization and bounds it without negative powers of possibly small wavelength, thus enabling it to capture the correct physical observables even if the spatial grid does not resolve the frequency, hence defying the Nyquist-Shannon sampling theorem.
  arXiv  Detail & Related papers  (2026-09-07T12:00:04Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  Glassiness -- a phenomenon in physics characterized by a rough free-energy landscape -- implies hardness for stable classical algorithms.<n>We prove that the standard notion of quantum glassiness based on replica symmetry breaking obstructs stable quantum algorithms for Gibbs sampling.
  arXiv  Detail & Related papers  (2025-10-09T17:37:33Z)
• Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity [0.616870773176256]
  We present a classical algorithm that runs in $nrmpolylog(n)$ time for simulating quantum circuits under local depolarizing noise.<n>Our results significantly extend the boundary of classical simulability and suggest that noise generically enforces approximate Markovianity and classical simulability.
  arXiv  Detail & Related papers  (2025-10-07T18:00:03Z)
• Constructive interference at the edge of quantum ergodic dynamics [116.94795372054381]
  We characterize ergodic dynamics using the second-order out-of-time-order correlators, OTOC$(2)$.<n>In contrast to dynamics without time reversal, OTOC$(2)$ are observed to remain sensitive to the underlying dynamics at long time scales.
  arXiv  Detail & Related papers  (2025-06-11T21:29:23Z)
• Improved amplitude amplification strategies for the quantum simulation of classical transport problems [41.94295877935867]
  We show that oblivious amplitude amplification when applied to non-unitary dynamics leads to a distortion of the quantum state and to an accompanying error in the quantum update.<n>We also propose an amplification strategy that helps mitigate the distortion error, while still securing an enhanced success probability.
  arXiv  Detail & Related papers  (2025-02-25T15:17:03Z)
• Simulating quantum circuits with arbitrary local noise using Pauli Propagation [0.0]
  We present a classical algorithm for estimating expectation values of arbitrary observables on typical quantum circuits under any incoherent local noise.<n>We show that this does not apply to average-case circuits, as these can be efficiently simulated using Pauli-path methods.
  arXiv  Detail & Related papers  (2025-01-22T18:57:16Z)
• Efficient simulation of parametrized quantum circuits under non-unital noise through Pauli backpropagation [4.903915603499684]
  Pauli backpropagation algorithms have already demonstrated their ability to efficiently simulate certain classes of parameterized quantum circuits.<n>Here, we close this gap by adapting Pauli backpropagation to non-unital noise.
  arXiv  Detail & Related papers  (2025-01-22T17:58:59Z)
• Pauli weight requirement of the matrix elements in time-evolved local operators: dependence beyond the equilibration temperature [0.0]
  We investigate whether "light" Pauli strings can be applied to quenches starting from homogeneous product states. In some cases, the light Pauli strings suffice to describe the dynamics, enabling efficient simulation with current algorithms. We analyze this behavior using a newly introduced measure of complexity, the Operator Weight Entropy.
  arXiv  Detail & Related papers  (2024-09-20T16:02:19Z)
• Classically estimating observables of noiseless quantum circuits [36.688706661620905]
  We present a classical algorithm for estimating expectation values of arbitrary observables on random unstructured quantum circuits.<n>Our results show that estimating observables of quantum circuits exhibiting chaotic and locally scrambling behavior is classically tractable across all geometries.
  arXiv  Detail & Related papers  (2024-09-03T08:44:33Z)
• A polynomial-time classical algorithm for noisy quantum circuits [1.2708457954150887]
  We provide a-time classical algorithm for noisy quantum circuits. Our approach is based upon the intuition that noise exponentially damps non-local correlations. For constant noise rates, any quantum circuit for which error mitigation is efficient on most input states, is also classically simulable on most input states.
  arXiv  Detail & Related papers  (2024-07-17T17:48:39Z)
• Noise-induced shallow circuits and absence of barren plateaus [2.5295633594332334]
  We show that any noise truncates' most quantum circuits to effectively logarithmic depth. We then prove that quantum circuits under any non-unital noise exhibit lack of barren plateaus for cost functions composed of local observables.
  arXiv  Detail & Related papers  (2024-03-20T19:00:49Z)
• Scalable noisy quantum circuits for biased-noise qubits [37.69303106863453]
  We consider biased-noise qubits affected only by bit-flip errors, which is motivated by existing systems of stabilized cat qubits. For realistic noise models, phase-flip will not be negligible, but in the Pauli-Twirling approximation, we show that our benchmark could check the correctness of circuits containing up to $106$ gates.
  arXiv  Detail & Related papers  (2023-05-03T11:27:50Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.