Magna: simulating magic state factories as cheaply as Clifford circuits

AI summary

Overview

Research area: Quantum information science — classical simulation of noisy, non-Clifford quantum circuits, with a focus on fault-tolerant quantum computing and magic state preparation.

Technical level: Advanced. The paper assumes familiarity with stabilizer formalism, the Clifford hierarchy, tensor networks, CSS codes, and magic state distillation/cultivation.

Scope (one sentence): The authors present Magna, a classical simulator that computes the acceptance rate and output fidelity of magic state factories by contracting globally reduced tensor networks, achieving a cost that does not grow exponentially with the number of output magic states.

What This Paper Is About

Magic state factories — the subroutines that produce the high-fidelity non-Clifford resources needed for universal fault-tolerant quantum computation — are expensive to evaluate because their circuits are full of non-Clifford gates, which defeat efficient Clifford simulation. Existing simulators either track complicated intermediate states or apply global simplifications that still scale exponentially in the number of output magic states. Magna instead computes only the two scalars that matter (acceptance rate and accepted-state fidelity) directly as tensor networks that are globally reduced, and it additionally handles feedforward driven by arbitrary functions of mid-circuit outcomes, including decoder outputs.

Key Contributions

1. A simulator that avoids exponential scaling in output count. Magna expresses the acceptance rate and the fidelity of accepted states as tensor networks and reduces them globally, exploiting a structural correspondence with transversal non-Clifford gates on quantum codes. Bravyi–Haah distillation is simulated up to k = 100 output magic states without exponential growth in the number of outputs.

2. A global reduction with a certified cost. The reduction pushes all Clifford operations to the network boundaries, diagonalizes the remaining commuting π/8 rotations, and confines non-Clifford dependence to a few "logical" coordinates, giving an expansion into a number of stabilizer terms called the representation rank. Both reduction stages require only Gaussian elimination over 𝔽₂ and stabilizer-state contractions, hence polynomial time.

3. Pauli-covariance of the reduced networks. The authors prove that Pauli insertions (stochastic faults or feedforward corrections) only shift affine offsets and add Clifford phases, leaving the phase trilinear form — and therefore the reduction structure — unchanged. One reduction is thus reused across all sampled error realizations.

4. Support for nonlinear feedforward and postselection. Magna handles control rules that are arbitrary functions of mid-circuit outcomes, including decoder outputs, by sampling outcomes in causal order from a third "sampling network," evaluating the classical rule, and returning the decisions as Pauli insertions.

Main Findings

• Bravyi–Haah scaling: For the (3k+8)-to-k distillation family, the largest simulated instance produces k = 100 output magic states from 308 input T states on 716 physical qubits and 10,130 gates, with 201 ms preparation time and 0.0503 ms per draw. Neither preparation time nor per-draw cost grows exponentially in k.

• Representation rank stays at one across the distillation family: In every Bravyi–Haah row reported in Table 1 (from 14-to-2 through 308-to-100), both the fidelity rank r_fid and the acceptance rank r_acc are 1, meaning the global reduction removed essentially all non-Clifford cost.

• Distance-5 cultivation: The paper reports state-of-the-art sampling times for distance-5 magic state cultivation on both the color code (53 T gates on 42 qubits) and the RP² surface code (101 T gates on 61 qubits). The specific timing values for these distance-5 rows are not visible in the provided excerpt, which is truncated partway through Table 1.

• Small-distance cultivation figures that are visible: Color code at d = 3 uses 15 qubits, 96 gates, and 15 T gates, with 2.62 ms preparation and 0.00589 ms per draw. RP² at d = 3 uses 25 qubits, 180 gates, and 31 T gates; its timing entries fall in the truncated portion.

• Nonlinear feedforward validated: On a logical-level surface-code distillation protocol with 15 rounds of decoder-dependent feedforward, Magna recovers the exact theoretical logical error rates under a simple noise model, using a single batch of 16,384 draws.

• Weight-one sampling in practice: When the sampling network reduces to a single stabilizer term (d_W = 0), the proposal distribution equals the true distribution and every sampled history has weight one — the case for all examples in Table 1.

• Per-draw cost is polynomial: Evaluating a draw costs polynomial time in circuit size per term, with the number of terms bounded by the representation rank, which is known as soon as the reference networks are constructed.

• Code switching and TQD are included as benchmarks: Table 1 covers 3DCC-to-2DCC and 3DCC-to-2DSC code switching, and twisted-quantum-double protocols on an L×L periodic lattice with T syndrome rounds; rows marked with an asterisk are stated not to be expanded in this paper and are referred to Ref. [28].

Methodology in Plain English

The simulator never builds the quantum state. Instead, it turns the whole circuit — plus a copy of its conjugate — into a tensor network whose contraction directly equals either the acceptance probability or the fidelity overlap with the target state. Only the measurement record and discarded qubits are traced out.

The key structural trick is to recognize that a magic state factory resembles a transversal non-Clifford gate on an error-correcting code. All Clifford gates are commuted to the edges of the network, leaving a bulk of commuting π/8 rotations that can be simultaneously diagonalized. The stabilizer boundaries then restrict the computational-basis labels that contribute to an affine subspace, which plays the role of a code space. Directions along which the phase is purely Clifford — the analogue of X-type stabilizers — are absorbed into the boundaries, leaving non-Clifford dependence only on a small number of logical coordinates. The network then becomes a short sum of stabilizer terms, and the number of terms is the representation rank, taken as the smaller of 2^{d_W} and c(t), the known stabilizer decomposition size of t copies of |T⟩.

For noise, the authors sample Pauli error realizations. Because the reduction is covariant under Pauli insertions, each sampled fault merely shifts an affine offset and adds a Clifford phase, so the expensive reduction is done once and reused for every draw. Sample counts scale as O(log(1/δ)/ε²) for acceptance and O(log(1/δ)/(p(acc)ε²)) for fidelity.

Arbitrary nonlinear feedforward is handled by introducing a virtual control qubit: prepare it in |0⟩, apply X^{f(m)} where f is the classical rule, use it to control a fixed Clifford gate, then trace it out. Postselection on a nonlinear condition uses the same construction but projects the virtual qubit onto |1⟩. To sample the outcomes that f depends on with their physical probabilities, a third network joins the protocol to its conjugate; conditional probabilities follow from ratios of network contractions, and a telescoping argument shows the probability of a full history is a single contraction. Outcomes are proposed from an affine-support distribution and reweighted, or drawn from exact conditionals via an exact-marginal method.

Why This Matters

Evaluating a magic state factory currently requires either simulating intermediate states bloated with irrelevant non-Clifford content or paying a cost exponential in the number of output states. Magna removes that bottleneck and, unusually, supports decoder-driven classical control — the feature real fault-tolerant protocols actually use. This makes large-scale, quantitative comparison of factory designs practical rather than aspirational.

Applications:

• Resource estimation for fault-tolerant architectures: obtaining accurate acceptance rates and logical error rates for distillation, cultivation, and code-switching protocols under circuit-level noise.
• Factory design and optimization: sweeping parameters such as code distance, distillation block size, and input T count without re-running an exponentially costly simulation, since preparation is done once and reused across draws.
• Decoder development and validation: the 15-round decoder-dependent logical-level distillation benchmark provides a testbed where simulation output can be checked against exact theoretical logical error rates.
• Architecture comparison: directly comparing color codes, RP² surface codes, and code-switching routes on common footing.

Industry relevance: Quantum hardware and software companies need reliable overhead estimates to size machines and to choose between competing factory designs. The authors' affiliation with Qosmos Technology (Beijing) Co., Ltd indicates industrial interest in tooling for this kind of large-scale evaluation and optimization.

Future Directions

• Extending beyond the supported gate set. The framework covers initialization in computational-basis states, Clifford gates plus T, CS, and CCZ, computational-basis measurements, reset/discard, linear Clifford or Pauli feedforward, and linear postselection. Broadening this component list — for example to other third-level Clifford-hierarchy gates or richer mid-circuit operations — is a natural next step.
• Controlling sampling variance when interference is present. The affine-support proposal leaves open the possibility that the proposal and true distributions mismatch due to non-Clifford interference. The exact-marginal method is implemented as a fallback; characterizing when each method is preferable remains an open question.
• Handling faults on feedforward gates more generally. Faults on conditioned gates become controlled Pauli operators to which the covariance argument does not apply, and Magna handles them only by treating the control outcomes as sampling legs. A more general treatment would widen applicability under realistic noise models.
• Scaling to full-scale factory evaluation and optimization. The stated aim is to provide infrastructure for large-scale evaluation and optimization of magic state factories; demonstrating this on industrially relevant, full-size factory designs with many parallel outputs is the obvious continuation.

Target Audience

Researchers and engineers working on fault-tolerant quantum computing who need quantitative performance estimates for magic state factories — particularly those doing resource estimation, factory architecture comparison, decoder design, or classical simulation tool development. It will also interest theorists working on stabilizer-rank methods, phase polynomials, and the simulation complexity of non-Clifford circuits. Readers should be comfortable with stabilizer formalism and tensor-network reasoning; the paper is not introductory.

Authors’ abstract

Classical simulation of magic state factories, including distillation, cultivation, and code switching, is challenging because of their substantial non-Clifford content. We introduce $\texttt{magna}$ (magic-state-factory assessment via global network algebra), a classical simulator that simulates such protocols as cheaply as Clifford circuits. $\texttt{magna}$ expresses the figures of merit of a protocol, namely the acceptance rate and the fidelity of the accepted states, as tensor networks, which it reduces globally by exploiting a structural correspondence with transversal gates on quantum codes. $\texttt{magna}$ further supports feedforward conditioned on arbitrary functions of mid-circuit measurement outcomes, including decoder outputs. We simulate Bravyi--Haah distillation with up to 100 output magic states at a cost that does not grow exponentially in the number of outputs, and achieve state-of-the-art sampling times for distance-5 magic state cultivation on both color codes and RP$^2$ surface codes. Finally, we validate nonlinear feedforward on a logical-level distillation protocol with 15 rounds of decoder-dependent feedforward. $\texttt{magna}$ aims to contribute to the key infrastructure for the large-scale evaluation and optimization of magic state factories.