Determining the quantum-classical boundary between quantum circuits that can be efficiently simulated classically and those that cannot remains a fundamental question. One approach to classical simulation is to represent the output of a quantum circuit as a Clifford-augmented matrix product state (CAMPS), which, via a disentangling algorithm, decomposes the wave function into Clifford and MPS components, and from which Pauli expectation values can be computed in time polynomial in the MPS bond dimension. In this work, we develop an optimization-free disentangling (OFD) algorithm for Clifford circuits either doped with T gates or, equivalently, preceded by multiqubit gates of the form α I + β P . We give a simple and easily computed algebraic criterion that characterizes the individual quantum circuits for which OFD generates an efficient CAMPS—the bond dimension is exponential in the null space of a Galois binary field GF(2) matrix induced by a tableau of the twisted Pauli strings P . This significantly increases the number of circuits with rigorous polynomial-time classical simulations. We also give evidence that the typical N qubit random Clifford circuit doped with N uniformly distributed T gates of polylogarithmic depth or greater has a CAMPS with polynomial bond dimension. In addition, we compare OFD against disentangling by optimization. We further explore the representability of CAMPS for random Clifford circuits doped with more than N T gates. We also propose algorithms for sampling, probability, and amplitude estimation of bitstrings, and evaluation of entanglement Rényi entropy from CAMPS, which, though still having exponential complexity, are more efficient than standard MPS simulations. This work establishes a versatile framework for understanding classical simulatability of Clifford + T circuits and explores the interplay between quantum entanglement and quantum magic in quantum systems.
Determining the quantum-classical boundary between quantum circuits that can be efficiently simulated classically and those that cannot remains a fundamental question. One approach to classical simulation is to represent the output of a quantum circuit as a Clifford-augmented matrix product state (CAMPS), which, via a disentangling algorithm, decomposes the wave function into Clifford and MPS components, and from which Pauli expectation values can be computed in time polynomial in the MPS bond dimension. In this work, we develop an optimization-free disentangling (OFD) algorithm for Clifford circuits either doped with T gates or, equivalently, preceded by multiqubit gates of the form α I + β P . We give a simple and easily computed algebraic criterion that characterizes the individual quantum circuits for which OFD generates an efficient CAMPS—the bond dimension is exponential in the null space of a Galois binary field GF(2) matrix induced by a tableau of the twisted Pauli strings P . This significantly increases the number of circuits with rigorous polynomial-time classical simulations. We also give evidence that the typical N qubit random Clifford circuit doped with N uniformly distributed T gates of polylogarithmic depth or greater has a CAMPS with polynomial bond dimension. In addition, we compare OFD against disentangling by optimization. We further explore the representability of CAMPS for random Clifford circuits doped with more than N T gates. We also propose algorithms for sampling, probability, and amplitude estimation of bitstrings, and evaluation of entanglement Rényi entropy from CAMPS, which, though still having exponential complexity, are more efficient than standard MPS simulations. This work establishes a versatile framework for understanding classical simulatability of Clifford + T circuits and explores the interplay between quantum entanglement and quantum magic in quantum systems.
The study of classical simulability is a key part of quantum information theory, providing new tools for fundamental research and the development of quantum computing. An increasingly successful framework for the study of simulability is resource theory. The best-known and best-understood quantum resource is entanglement, but in recent years nonstabilizerness, or magic, has also been gathering attention from the community. It is not yet well understood to what extent different resources play off each other in making systems hard to classically simulate. It has recently been shown that Clifford-augmented matrix product states (CAMPS) allow for efficient circuit simulation in some cases where both entanglement and magic are present. Another emerging method which has shown the ability to simulate systems with both resources is Pauli propagation (PP). Furthermore, the interplay between entanglement and magic at the level of physical phenomena is also poorly understood, in particular in the context of real-time dynamics. In this work, I implement an analytical algorithm proposed by Fux et al. (2025) which allows CAMPS to efficiently simulate essentially the first N non-Clifford Pauli exponential gates in an N-qubit quantum circuit, reproducing results obtained by greedy-search entanglement cooling in the paper. I then develop CAMPS-PP, a method for expectation value dynamics which evolves the state as a CAMPS and the observable in the Heisenberg picture using PP. I show that this method is significantly faster than pure CAMPS for slightly deep random Pauli rotation circuits at the tested system sizes, up to N=100, with improvements of up to two orders of magnitude for N=20. Finally, in order to investigate the physical relevance of magic I apply CAMPS-PP to an XXZ Heisenberg Floquet circuit with Clifford and non-Clifford angles, finding that CAMPS-PP slightly extends the simulable non-Clifford gate density and significantly reduces memory requirements compared to PP.
Quantum magic is a necessary resource for quantum computers to be not efficiently simulable by classical computers. Previous results have linked the of quantum magic, characterized by the number of T gates or the stabilizer rank, to classical simulability. However, the effect of the of quantum magic on the hardness of simulating a quantum circuit remains open. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and T layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case in which all T gates are distributed in a single layer, performing amplitude estimation and sampling to multiplicative error are already classically intractable under reasonable assumptions, but Pauli observables are easy to evaluate. Surprisingly, with the addition of just one T -gate layer or merely replacing all T gates with T 1 / 2 , the Pauli evaluation task reveals a sharp complexity transition from being in P to being GapP-complete. Nevertheless, when the precision requirement is relaxed to 1 / poly ( n ) additive error, we are able to give a polynomial-time classical algorithm to compute amplitudes, Pauli observables, and sampling from log ( n ) -sized marginal distributions for any magic-depth-1 circuit that is decomposable into a product of diagonal gates. This rules out certain forms of quantum advantage in these circuits. Our research provides new techniques to simulate highly magical circuits while shedding light on their complexity and their significant dependence on the magic depth.
Clifford circuits acting on product magic states provide a compact ansatz exhibiting extensive magic, volume-law entanglement, and even classically hard sampling under standard complexity assumptions. Here, we efficiently recover its hidden product subsystems from two-copy Bell sampling. Quadratic relations between Bell samples determine the irreducible blocks after removing Pauli stabilizers, and binary linear algebra constructs a Clifford disentangler. For logarithmic-size blocks, approximate learning of the full state is efficient whenever the state remains inverse-polynomially separated from acquiring additional Pauli stabilizers. We efficiently learn n-qubit states prepared by random T-doped Clifford circuits with T-gate density below one via O(n2) Bell samples, and disentangle hidden product blocks in Clifford-augmented matrix product states. For unitary learning, we exactly learn T-depth-one circuits using O(n2) queries. Finally, we rule out pseudorandom states and unitaries with a product bipartition hidden by Clifford circuits.
We show that states obtained from deep random Clifford circuits doped with non-Clifford phase gates (including T gates and sqrt[T] gates) can be disentangled completely, provided the number of non-Clifford gates is smaller or approximately equal to the number of qubits. This implies that Pauli expectation values of such states can be efficiently simulated classically, despite them exhibiting both extensive entanglement and extensive nonstabilizerness. We prove this result analytically using a quantum error correction formulation, demonstrate its applicability numerically, and discuss consequences for the disentanglability of states generated through Hamiltonian dynamics. We show that this result implies a novel representation of approximate state designs that can also facilitate their efficient generation, and we propose a novel quantum circuit compression scheme for Clifford circuits doped with non-Clifford phase gates.
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.
In this work, we investigate the Kitaev honeycomb model employing the recently developed Clifford Circuits Augmented Matrix Product States (CAMPS) method. While the model in the gapped phase is known to reduce to the toric code model - whose ground state is entirely constructible from Clifford circuits - we demonstrate that the very different gapless quantum spin liquid (QSL) phase can also be significantly disentangled with Clifford circuits. Specifically, CAMPS simulations reveal that approximately two-thirds of the entanglement entropy in the isotropic point arises from Clifford-circuit contributions, enabling dramatically more efficient computations compared to conventional matrix product state (MPS) methods. Crucially, this finding implies that the Kitaev QSL state retains significant Clifford-simulatable structure, even in the gapless phase with non-abelian anyon excitations when time reversal symmetry is broken. This property not only enhances classical simulation efficiency significantly but also suggests substantial resource reduction for preparing such states on quantum devices. As an application, we leverage CAMPS to study the Kitaev-Heisenberg model and determine the most accurate phase boundary between the anti-ferromagnetic phase and the Kitaev QSL phase in the model. Our results highlight how Clifford circuits can effectively disentangle the intricate entanglement of Kitaev QSLs, opening avenues for efficiently simulating related and similar strongly correlated models.