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.
AI Summary
Why can classical algorithms that retain local information accurately predict quantum expectation values even when entanglement and magic are large? This paper introduces an experiment-dependent diagnostic, the reactivity, for an initial state, evolution and observable jointly. The signed function $R_\tau(w)$ sums Pauli-path contributions of weight $w$ at time $\tau$; a global version uses total space-time weight. Inserting local depolarizing noise gives $C_\tau(\gamma)=\sum_w e^{-\gamma w}R_\tau(w)$.
Numerical studies of a 51-qubit one-dimensional mixed-field Ising chain and a $5\times5$ transverse-field Ising lattice compare reactivity tails with sparse-Pauli-dynamics memory requirements. The required weight tracks the logarithm of retained Pauli-string counts across several initial states and times, within the accessible range $w\lesssim10$. Rigorous results give learning and circuit-segment recombination estimators with mean-square error $\varepsilon^2+N^{\mathcal O(w_*)}/M$ for $M$ randomized-measurement rounds under a small-tail assumption. Classical simulation guarantees cover low global reactivity and, for time-slice reactivity, Pauli-random circuit ensembles.
“Pauli path spectroscopy” inserts randomized Pauli perturbations and combines measured expectation values to estimate smoothed reactivity features. Resolving width $\delta w$ near weight $w$ has sampling overhead $X\sim\exp[\mathcal O(w/\delta w)]$, allowing fixed relative resolution at increasing weight. A doubled-system coherent protocol accesses individual weights for infinite-temperature correlators.
High reactivity is not a hardness certificate and can be spoofed. Exact noise-based reconstruction is ill-conditioned; efficient measurements smooth away sharp, potentially cancelling features. Numerical evidence is limited by classical convergence, and no hardware demonstration is reported.
No sign of AI-generated textStrong assumptions
Central claim may not hold: The rigorous classical-simulation guarantees concern low global reactivity for general circuits or ensemble-controlled low time-slice reactivity for Pauli-random circuits, rather than unrestricted low time-slice reactivity in Hamiltonian experiments.
For general experiments, Pauli path spectroscopy efficiently measures smooth functionals of reactivity, not the complete reactivity function at arbitrary resolution.
The arbitrary-initial-state classical-simulation theorem omits efficient classical access to the initial state's Pauli expectations, without which even constant-reactivity identity-circuit experiments can encode general quantum computations.
The ancilla-assisted coherent reconstruction contains both a sine-transform sign inconsistency and an inverse-transform normalization error, so its printed formulas do not recover the stated reactivity.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
Why can classical algorithms that retain local information accurately predict quantum expectation values even when entanglement and magic are large? This paper introduces an experiment-dependent diagnostic, the reactivity, for an initial state, evolution and observable jointly. The signed function Rτ(w) sums Pauli-path contributions of weight w at time τ; a global version uses total space-time weight. Inserting local depolarizing noise gives Cτ(γ)=∑we−γwRτ(w).
Numerical studies of a 51-qubit one-dimensional mixed-field Ising chain and a 5×5 transverse-field Ising lattice compare reactivity tails with sparse-Pauli-dynamics memory requirements. The required weight tracks the logarithm of retained Pauli-string counts across several initial states and times, within the accessible range w≲10. Rigorous results give learning and circuit-segment recombination estimators with mean-square error ε2+NO(w∗)/M for M randomized-measurement rounds under a small-tail assumption. Classical simulation guarantees cover low global reactivity and, for time-slice reactivity, Pauli-random circuit ensembles.
“Pauli path spectroscopy” inserts randomized Pauli perturbations and combines measured expectation values to estimate smoothed reactivity features. Resolving width δw near weight w has sampling overhead X∼exp[O(w/δw)], allowing fixed relative resolution at increasing weight. A doubled-system coherent protocol accesses individual weights for infinite-temperature correlators.
High reactivity is not a hardness certificate and can be spoofed. Exact noise-based reconstruction is ill-conditioned; efficient measurements smooth away sharp, potentially cancelling features. Numerical evidence is limited by classical convergence, and no hardware demonstration is reported.
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.
We develop classical simulation algorithms for adaptive quantum circuits that produce states with low levels of ``magic'' (i.e., non-stabilizerness). These algorithms are particularly well-suited to circuits with high rates of Pauli measurements, such as those encountered in quantum error correction and monitored quantum circuits. The measurements serve to limit the buildup of magic induced by non-Clifford operations arising from generic noise processes or unitary gates, respectively. Our algorithms also allow a systematic truncation procedure to achieve approximate simulation. To benchmark our approach, we study the dynamics of all-to-all monitored quantum circuits with a sub-extensive rate of T-gates per unit of circuit depth, where we can simulate previously inaccessible system sizes and depths. We characterize measurement-induced phase transitions in the output wavefunction, including in the entanglement, purification, and magic. We outline the utility of our algorithms to simulate dynamics with low magic and high entanglement, complementary to the leading matrix-product state approaches.
In this this paper we present an inexpensive protocol to perform runtime and memory estimation for large-scale experiments with Pauli Path simulators (PPS). Additionally, we propose a conceptually simple solution for studying whether PPS can be used as a scientific discovery tool, rather than reproducing existing answers. We start by analyzing the dynamics of the Pauli coefficients tracked in the Heisenberg picture. In addition to surprisingly generic convergence features of the Pauli coefficient distributions, we find certain regularities that allow for extrapolation of memory and runtime requirements for smaller and smaller coefficient truncation parameter δ. We then introduce a framework for understanding convergence in the absence of rigorous error guarantees on PPS. Combined with runtime analysis, we propose bifurcating quantum simulation problems broadly into two classes, based on whether there is apparent convergence of expectation values as a function of δ. This serves as a way for practitioners to understand where their problem falls on the frontier of classical simulability. In the case without apparent convergence, PPS may still serve useful as a Monte Carlo-like estimate. Applied to IBM's utility-scale experiments, we show parameter regimes where both behaviors are realized. Some of our key findings challenge conventional intuition: reducing δ does not always improve accuracy, and deeper quantum circuits may actually be easier to simulate than shallower ones. The BlueQubit SDK implementing these methods has been released publicly, offering researchers a comprehensive toolkit for evaluating this frontier classical simulation approach. These results establish practical guidelines for when PPS can serve as a reliable verification tool versus when it should be used as a complementary estimate alongside quantum experiments.
The classical simulation of highly entangling quantum dynamics is conjectured to be generically hard. Thus, recently discovered measurement-induced transitions between highly entangling and low-entanglement dynamics are phase transitions in classical simulability. Here, we study simulability transitions beyond entanglement: noting that some highly entangling dynamics (e.g., integrable systems or Clifford circuits) are easy to classically simulate, thus requiring “magic”—a subtle form of quantum resource—to achieve computational hardness, we ask how the dynamics of magic competes with measurements. We study the resulting “dynamical magic transitions” focusing on random monitored Clifford circuits doped by T gates (injecting magic). We identify dynamical “stabilizer purification”—the collapse of a superposition of stabilizer states by measurements—as the mechanism driving this transition. We find cases where transitions in magic and entanglement coincide, but also others with a magic and simulability transition in a highly (volume-law) entangled phase. In establishing our results, we use Pauli-based computation, a scheme distilling the quantum essence of the dynamics to a magic state register subject to mutually commuting measurements. We link stabilizer purification to “magic fragmentation” wherein these measurements separate into disjoint, O ( 1 ) -weight blocks, and relate this to the spread of magic in the original circuit becoming arrested. Published by the American Physical Society 2024
A recent experiment [T. Lanting et al., Phys. Rev. X 4, 021041 (2014)] claimed to provide evidence of up to eight-qubit entanglement in a D-Wave quantum annealing device. However, entanglement was measured using qubit tunneling spectroscopy, a technique that provides indirect access to the state of the system at intermediate times during the anneal by performing measurements at the end of the anneal with a probe qubit. In addition, an underlying assumption was that the quantum transverse-field Ising Hamiltonian, whose ground states are already highly entangled, is an appropriate model of the device and not some other (possibly classical) model. This begs the question of whether alternative classical or semiclassical models would be equally effective at predicting the observed spectrum and thermal state populations. To check this, we consider a recently proposed classical rotor model with classical Monte Carlo updates, which has been successfully employed in describing features of earlier experiments involving the device. We also consider simulated quantum annealing with quantum Monte Carlo updates, an algorithm that samples from the instantaneous Gibbs state of the device Hamiltonian. Finally, we use the quantum adiabatic master equation, which cannot be efficiently simulated classically and which has previously been used to successfully capture the open-system quantum dynamics of the device. We find that only the master equation is able to reproduce the features of the tunneling spectroscopy experiment, while both the classical rotor model and simulated quantum annealing fail to reproduce the experimental results. We argue that this bolsters the evidence for the reported entanglement.
We introduce a family of quantum circuits that possess standard indicators of classical simulation hardness including high entanglement entropy, magic, and non-Gaussianity, yet admit efficient classical simulation via matrix product states (MPS). Our construction uses logical circuits of high-rate Calderbank-Shor-Steane (CSS) codes with enhanced symmetries. Using code automorphisms and transversal diagonal gates from higher levels of the Clifford hierarchy, we realize nonlocal logical Clifford and non-Clifford gates, showing how error-correcting codes can compile complex logical circuits into simple physical operations. Simulation efficiency rests on two properties: (i) diagonal transversal gates do not increase bond dimension, and (ii) permutations are tracked classically via on-the-fly relabeling, avoiding costly SWAP networks. Unlike Clifford or matchgate simulation, our method accepts a broad class of initial states, including dense entangled, magic, and non-Gaussian inputs, provided the encoded state retains an efficient MPS representation. We also release an exact phase-polynomial backend for monomial subfamilies, whose cost is set by higher-degree phase terms rather than entanglement growth. We demonstrate the method on an infinite polar CSS code family, showing bond dimension stays bounded by the encoding cost regardless of circuit depth. These results show that for some circuit families, standard resource measures are individually insufficient to indicate simulation hardness. As a near-term application, we use the compiled MPS as a classical reference for direct fidelity estimation of a quantum device running nontrivial logical circuits. Pauli sampling on the encoded reference, with a Clifford pushback through the known encoder, provides the ideal expectation values, so the logical output fidelity can be estimated from local Pauli readout alone, without costly state tomography.