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.
AI Summary
The paper asks whether dynamical diagnostics of noisy circuits—magic, scrambling, anticoncentration and fermionic non-Gaussianity—track efficient classical simulation. It compares random Clifford+$T$ circuits with local depolarising noise and nearest-neighbour matchgate+SWAP circuits with Majorana dephasing, using tensor-network, stabilizer-decomposition, Pauli-path, uniform-sampling and fermionic-degree-truncation criteria.
The reported simulation and diagnostic boundaries do not coincide: resource signatures can persist in efficiently sampleable regimes, while diagnostics can become trivial outside the regimes covered by the algorithms considered. The proposed mechanism is different noise sensitivity of spectral moments. For undoped global Clifford circuits, the weak-noise decay exponent of the $2m$-th Pauli moment approaches $m$ times that of the second moment; numerical calculations support an approximately twofold fourth-/second-moment decay-rate ratio in doped brickwork circuits. Fourth-order Clifford-commutant transfer networks evaluate magic diagnostics, while second-moment transfer matrices determine sampling criteria. Under sparse noise, the paper reports a magic-window depth scaling as $\Theta(N)$ versus a $\Theta(1)$ uniform-sampling threshold, yielding $N^*=3\log_2[1/(\varepsilon^2\delta_c)]+O(1)$ for sampling error $\varepsilon$ and circuit failure probability $\delta_c$.
For matchgate circuits, simulation bounds depend on Majorana-degree tails rather than a scalar resource diagnostic. Non-Gaussianity is evaluated by density-matrix simulation for $N\leq8$; the displayed map uses $N=6$ and 20 realizations. Its boundary depends on numerical resolution, and sector-transfer formulas assume within-sector equilibration. Uncovered regions carry no hardness guarantee, and a non-positive magic witness does not establish absence of magic.
Some signs of AI-generated textOverclaimsStrong assumptionsPossible error
Central claim may not hold: The abstract's scrambling conclusion has no supporting noisy-OTOC calculation or scrambling-versus-simulation comparison in the supplied paper.
The proposed universal fourth-versus-second-moment mechanism exceeds the demonstrated result, since anticoncentration is second order and entropy-based fermionic non-Gaussianity is not shown to be fourth order.
For sparse-noise nearest-neighbour circuits, disjoint unaffected light cones rule out the claimed size-independent ensemble uniform-sampling depth asymptotically, and the necessary purity condition does not establish witness persistence, undermining the crossover derivation.
The assumption-free Majorana degree-tail identity is false, already giving 5/3 instead of 3 for the initial two-qubit state, and the advertised exact brickwork sector evolution requires an unestablished within-sector uniformity assumption.
The matchgate resource-disappearance boundary is supported only at numerical resolutions on small systems, not as an exact vanishing boundary.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper asks whether dynamical diagnostics of noisy circuits—magic, scrambling, anticoncentration and fermionic non-Gaussianity—track efficient classical simulation. It compares random Clifford+T circuits with local depolarising noise and nearest-neighbour matchgate+SWAP circuits with Majorana dephasing, using tensor-network, stabilizer-decomposition, Pauli-path, uniform-sampling and fermionic-degree-truncation criteria.
The reported simulation and diagnostic boundaries do not coincide: resource signatures can persist in efficiently sampleable regimes, while diagnostics can become trivial outside the regimes covered by the algorithms considered. The proposed mechanism is different noise sensitivity of spectral moments. For undoped global Clifford circuits, the weak-noise decay exponent of the 2m-th Pauli moment approaches m times that of the second moment; numerical calculations support an approximately twofold fourth-/second-moment decay-rate ratio in doped brickwork circuits. Fourth-order Clifford-commutant transfer networks evaluate magic diagnostics, while second-moment transfer matrices determine sampling criteria. Under sparse noise, the paper reports a magic-window depth scaling as Θ(N) versus a Θ(1) uniform-sampling threshold, yielding N∗=3log2[1/(ε2δc)]+O(1) for sampling error ε and circuit failure probability δc.
For matchgate circuits, simulation bounds depend on Majorana-degree tails rather than a scalar resource diagnostic. Non-Gaussianity is evaluated by density-matrix simulation for N≤8; the displayed map uses N=6 and 20 realizations. Its boundary depends on numerical resolution, and sector-transfer formulas assume within-sector equilibration. Uncovered regions carry no hardness guarantee, and a non-positive magic witness does not establish absence of magic.
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), 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.
Magic states are essential for universal quantum computation and are widely viewed as a key source of quantum advantage, yet in realistic devices they are inevitably noisy. In this work, we characterize how noise on injected magic resources changes the classical simulability of quantum circuits and when it induces a transition from classically intractable behavior to efficient classical simulation. We adopt a resource-centric noise model in which only the injected magic components are noisy, while the baseline states, operations, and measurements belong to an efficiently simulable family. Within this setting, we develop an approximate classical sampling algorithm with controlled error and prove explicit noise-dependent conditions under which the algorithm runs in polynomial time. Our framework applies to both qubit circuits with Clifford baselines and fermionic circuits with matchgate baselines, covering representative noise channels such as dephasing and particle loss. We complement the analysis with numerical estimates of the simulation cost, providing concrete thresholds and runtime scaling across practically relevant parameter regimes.
A confluence of recent works has shown that many quantum circuits and dynamics are efficiently simulable by classical algorithms that track local information, even when conventional complexity measures such as the entanglement and magic are high. Here, we introduce a novel measure of complexity, the reactivity, to capture this new method of classical attack. Unlike conventional complexity measures, the reactivity does not capture a property of a quantum state or operator in isolation, but rather a quantum experiment as a whole. We provide numerical and rigorous evidence that quantum experiments with low reactivity are simple by a host of measures: they are efficient to classically simulate, learn, and fast-forward. This motivates the search for quantum experiments with high reactivity, which may evade these simplistic features. To this end, we introduce easily implementable experimental protocols---dubbed Pauli path spectroscopy---that allow one to efficiently measure the reactivity of any quantum experiment of interest. Our protocols are applicable even when the experiment itself is beyond the reach of classical simulation.
The quantum-trajectory description of a noisy quantum circuit is not unique: every Kraus representation of the noise channel defines a different unraveling, i.e., a different ensemble of pure states that averages to the same density matrix. While all unravelings share the same expectation values of observables, they generally differ in the amount of quantum resources carried by the individual trajectories. Here we study non-stabilizerness, or magic, quantified by the stabilizer Rényi entropy, in quantum-trajectory unravelings of Haar-random and T-doped random Clifford brickwork circuits subject to local dephasing noise of strength p. The canonical unraveling in terms of Pauli jumps is Clifford and leaves magic untouched, so that trajectories retain the Haar-random value of non-stabilizerness. Exploring the full two-parameter family of minimal unravelings, we find that the trajectory-averaged magic can be substantially reduced by a state-independent choice of Kraus operators, and that the optimal choice is not in general the projective-measurement unraveling, but a two-outcome generalized measurement in which the Kraus operators correspond to a weak measurement of the noisy qubit. The optimal unraveling reduces the extensive magic density of the trajectories by a p-dependent factor without altering its linear scaling with system size. At the same time, it produces a very broad distribution of magic over trajectories, with a sizable fraction of trajectories retaining Haar-random magic. Since the cost of stabilizer-based classical simulation grows exponentially with the magic of the state, these high-magic trajectories, rather than the average, control the simulation cost. Our results delineate the potential and the limitations of unraveling optimization as a route to the classical simulation of noisy quantum dynamics with stabilizer methods.
Classically hard-to-simulate quantum states, or "magic" states, are prerequisites to quantum advantage, highlighting an apparent separation between classically and quantumly tractable problems. Classically simulable states such as Clifford circuits on stabilizer states, free bosonic states, free fermions, and matchgate circuits are all in some sense Gaussian. While free bosons and fermions arise from quadratic Hamiltonians, recent works have demonstrated that bosonic and qudit systems converge to Gaussians and stabilizers under convolution. In this work, we similarly identify convolution for fermions and find efficient measures of non-Gaussian magic in pure fermionic states. We demonstrate that three natural notions for the Gaussification of a state—(1) the Gaussian state with the same covariance matrix, (2) the fixed point of convolution, and (3) the closest Gaussian in relative entropy—coincide by proving a central limit theorem for fermionic systems. We then utilize the violation of Wick's theorem and the matchgate identity to quantify non-Gaussian magic in addition to a SWAP test.
For random quantum circuits on n qubits of depth Θ ( log n ) with depolarizing noise, the task of sampling from the output state can be efficiently performed classically using a Pauli path method \cite{Aharonov2023_paulipaths} . This paper aims to study the performance of this method beyond random circuits. We first consider the classical simulation of local observables in circuits composed of Clifford and T gates – going beyond the average case analysis, we derive sufficient conditions for simulatability in terms of the noise rate and the fraction of gates that are T gates, and show that if noise is introduced at a faster rate than T gates, the simulation becomes classically easy. As an application of this result, we study 2D QAOA circuits that attempt to find low-energy states of classical Ising models on general graphs. There, our results shows that for hard instances of the problem, which correspond to Ising model's graph being geometrically non-local, a QAOA algorithm mapped to a geometrically local circuit architecture using SWAP gates does not have any asymptotic advantage over classical algorithms if depolarized at a constant rate. Finally, we illustrate instances where the Pauli path method fails to give the correct result, and also initiate a study of the trade-off between fragility to noise and classical complexity of simulating a given quantum circuit.