Non-Clifford gates are essential for avoiding classical simulability under the Gottesman-Knill theorem. An error-corrected circuit with non-Clifford gates will therefore be an important element for realizing useful fault-tolerant quantum algorithms. However, accurately understanding the fault-tolerant performance of such circuits faces challenges due to the classical hardness of simulating these circuits. We avoid simulating logical measurements and develop exact and efficient classical methods for benchmarking circuits composed of X, CNOT, and diagonal gates in the Clifford hierarchy, including state and gate teleportation gadgets with feedforward. For circuits with third-level diagonal gates, our benchmarking algorithm efficiently samples syndrome statistics and estimates the output logical fidelity and expectation values of certain Clifford observables, including all Pauli observables. The evaluation of syndrome expectation values also extends to circuits with fourth-level diagonal gates. Our algorithm scales polynomially in the number of physical qubits n and circuit depth T, independent of the number of logical qubits. The benchmarking applications include IQP sampling and magic state preparation/cultivation. We demonstrate the practical utility of our simulation algorithms by using them to optimize high-rate magic state distillation factories based on three copies of a [[27,3,3]] tricycle code.
Non-Clifford gates are essential for avoiding classical simulability under the Gottesman-Knill theorem. An error-corrected circuit with non-Clifford gates will therefore be an important element for realizing useful fault-tolerant quantum algorithms. However, accurately understanding the fault-tolerant performance of such circuits faces challenges due to the classical hardness of simulating these circuits. We avoid simulating logical measurements and develop exact and efficient classical methods for benchmarking circuits composed of X, CNOT, and diagonal gates in the Clifford hierarchy, including state and gate teleportation gadgets with feedforward. For circuits with third-level diagonal gates, our benchmarking algorithm efficiently samples syndrome statistics and estimates the output logical fidelity and expectation values of certain Clifford observables, including all Pauli observables. The evaluation of syndrome expectation values also extends to circuits with fourth-level diagonal gates. Our algorithm scales polynomially in the number of physical qubits n and circuit depth T, independent of the number of logical qubits. The benchmarking applications include IQP sampling and magic state preparation/cultivation. We demonstrate the practical utility of our simulation algorithms by using them to optimize high-rate magic state distillation factories based on three copies of a [[27,3,3]] tricycle code.
We show that every intermediate state of a broad class of non-Clifford quantum error-correction circuits is a third-order phase-polynomial state, even under stochastic Pauli noise. The class includes magic state distillation and cultivation, code switching and gauge fixing, transversal non-Clifford gates with syndrome extraction, and injection of diagonal magic states. Third-order phase-polynomial states strictly generalize stabilizer states, and we prove that they are exactly the stabilizer states of the diagonal-Clifford-and-Pauli (DCP) stabilizer formalism that we introduce. We characterize these states and show that their representations can be updated in polynomial time. This yields an exact polynomial-time simulation algorithm for these circuits and, more broadly, a framework for reasoning about their internal states and about magic states in general. We provide an open-source implementation, \texttt{merlin}, and benchmark it against existing non-Clifford simulators on distillation, cultivation, and code switching circuits. The benchmarks demonstrate improved runtime and memory scaling as the number of logical outputs grows in Bravyi-Haah distillation, and simulation of a code switching circuit beyond the reach of all other tested simulators.
The preparation of high-fidelity logical magic states is a crucial subroutine for universal fault-tolerant quantum computation (FTQC). Predicting the performance of FTQC and developing improved protocols rely on numerical methods to classically simulate logical magic state preparation in the presence of noise. Clifford logic on Pauli-stabilizer codes with circuit-level Pauli errors can be efficiently simulated using Pauli-stabilizer formalism, but the non-Clifford operations required to prepare logical magic states render generic simulation inefficient. We introduce Clifford-stabilizer simulation, an exact and efficient algorithm based on updating a Clifford-stabilizer group to simulate noisy preparation protocols for a broad class of logical magic states used to implement non-Clifford gates in the third level of the Clifford hierarchy under circuit-level Pauli errors. Clifford-stabilizer simulation applies to a range of operations that commonly appear in preparation protocols for such logical magic states, including Pauli-stabilizer measurements, logical Clifford measurements, and transversal non-Clifford gates. Our algorithm for Clifford-stabilizer simulation maps a non-Clifford circuit with sampled circuit-level Pauli errors to a Clifford circuit that exactly reproduces its measurement outcome distribution, achieving time and space complexities polynomial in relevant protocol parameters. We perform exact simulation of magic state cultivation up to fault distance 7 by Clifford-stabilizer simulation. Our method provides a route to perform exact benchmarking of large-scale logical magic state preparation protocols required for useful FTQC.
Zero-level CCZ Distillation
Magic state distillation is a key component of fault-tolerant quantum computation, as it enables the implementation of non-Clifford gates such as the T gate and the CCZ gate via gate teleportation. However, conventional distillation protocols require a large number of logical qubits and introduce substantial spatial and temporal overhead, posing a significant bottleneck for scalable fault-tolerant quantum computation. In this work, we propose a zero-level distillation protocol that efficiently generates a high-fidelity logical CCZ magic state using only physical qubits on a two-dimensional square lattice with nearest-neighbor interactions. Our method leverages the transversal T/T† operation of the [[8,3,2]] code to fault-tolerantly encode the state CCZ∣+++⟩, which is subsequently teleported to three surface-code logical qubits via lattice surgery. To enable teleportation between codes with different distances, we introduce adaptively initialized teleportation (AIT), a tailored initialization procedure for the surface code. Numerical simulations demonstrate that the logical error rate scales as pL≃300×p2 with respect to the physical error rate p. For example, the proposed method improves the logical error rate by approximately one and two orders of magnitude at p=10−3 and p=10−4, respectively, compared to conventional seven-T-gate approaches. The distillation circuit requires only 22 physical qubits, 3 logical qubits, and a circuit depth of 24, reducing the space-time overhead by a factor of approximately 5-10 compared to previous methods. This result highlights the practicality of CCZ-state distillation in early fault-tolerant quantum computation and offers a new direction toward resource-efficient physical-level magic state distillation beyond conventional T-state generation.
Developing space- and time-efficient logical magic state preparation protocols will likely be an essential step towards building a large-scale fault-tolerant quantum computer. Motivated by this need, we introduce a scalable method for simulating logical magic state preparation protocols under the standard circuit-level noise model. When applied to protocols based on code switching, magic state cultivation, and magic state distillation, our method yields a complexity polynomial in (i) the number of qubits and (ii) the non-stabilizerness, e.g., stabilizer rank or Pauli rank, of the target encoded magic state. The efficiency of our simulation method is rooted in a curious fact: every circuit-level Pauli error in these protocols propagates to a Clifford error at the end. This property is satisfied by a large family of protocols, including those that repeatedly measure a transversal Clifford that squares to a Pauli. We provide a proof-of-principle numerical simulation that prepares a magic state using such logical Clifford measurements. Our work enables practical simulation of logical magic state preparation protocols without resorting to approximations or resource-intensive state-vector simulations.
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.
Magic state distillation (MSD) is an essential element for universal fault-tolerant quantum computing, which distills a high-fidelity magic state from noisy magic states using ideal (error-corrected) Clifford operations. For ideal Clifford operations, it needs to be performed on the logical qubits and hence incurs a large spatiotemporal overhead, which is one of the major bottlenecks for the realization of fault-tolerant quantum computers (FTQCs). Here we propose zero-level distillation, which prepares a high-fidelity logical magic state at the physical level, namely , using physical qubits and nearest-neighbor two-qubit gates on a square lattice. We develop a zero-level distillation circuit and show that distillation can be made even more efficient than the conventional sophisticated approaches with logical level distillations. The key idea involves the Knill -type distillation using the Steane code and its careful mapping to the square-lattice architecture with error detection. The distilled magic state on the Steane-code state is then teleported or converted to surface codes. We numerically find that the error rate of the logical magic state scales as approximately 100 × p 2 in terms of the physical error rate p . For example, with a physical error rate of p = 10 − 4 ( 10 − 3 ), the logical error rate is reduced to p L = 10 − 6 ( 10 − 4 ), resulting in an improvement of 2 (1) orders of magnitude. This contributes to reducing both space and time overhead for early FTQC as well as full-fledged FTQC combined with conventional multilevel distillation protocols.