The limits of magic-state distillation

Technical Summary: The Limits of Magic-State Distillation

Problem Statement
Magic-state factories constitute a significant overhead in fault-tolerant quantum computing, consuming noisy non-Clifford resources (such as $T$ states) to produce high-fidelity target states. While resource theories provide general bounds, they often yield weak scaling (e.g., $n \gtrsim d$) or assume deterministic success. Conversely, exhaustive searches have resolved input counts for specific code families but have not established whether adaptive, postselected, or multistage protocols could outperform static stabilizer codes. The central question addressed is: What is the minimum number of noisy inputs $n$ required for an arbitrary stabilizer protocol to distill a target state $\tau$ with error suppression order $d$ (output error $O(p^d)$), given an input error rate $p$?

Methodology
The authors reduce the infinite space of potential distillation protocols (including adaptive, postselected, and multistage strategies) to a combinatorial search over stabilizer codes via two key theoretical reductions:

1. Reduction to Single-Code Projection (Theorem 1): The paper proves that any stabilizer protocol tolerating a set of fault patterns is no more powerful than a single stabilizer code projection. Specifically, a protocol accepts a fault-free input and renders a set of fault patterns harmless if and only if there exists a stabilizer code $C$ on the $n$ inputs such that every tolerated input state projects either onto the encoded target vector or to zero. This eliminates the need to search over complex circuit topologies, feedforward, or randomness, replacing them with the search for signed stabilizer codes.
2. Symmetry of Complementary Faults (Theorem 2): For targets with rational Pauli expectations (e.g., CCZ, CS), the paper demonstrates that a fault pattern $e$ is harmless if and only if its complement $e + \mathbf{1}$ is harmless. This symmetry arises because the automorphism $\sigma$ (flipping the sign of $\sqrt{2}$) commutes with stabilizer operations and maps a noisy state $\rho_T(p)$ to $\rho_T(1-p)$. This effectively doubles the set of fault patterns that must be tolerated, significantly pruning the search space for candidate codes.

Using these reductions, the authors employ exact arithmetic over the ring $\mathbb{Z}[\sqrt{2}, i]$ to perform exhaustive searches over signed stabilizer codes up to $n=9$ inputs. They utilize integer programming and SAT solvers to construct explicit factories (upper bounds) and verify them against the "collapse" conditions derived from Theorem 1. Analytic arguments using "witness" states and linear programming relaxations provide lower bounds for higher orders.

Key Contributions and Results
The paper establishes the first exact minimum input counts $n_{\min}(\tau, d)$ for error suppression by arbitrary stabilizer protocols, resolving several open questions regarding the optimality of existing factories:

• Optimality of Existing Factories: The search confirms that the eight-input quadratic CCZ factory is optimal; no adaptive or multistage protocol can distill a CCZ state with order $d=2$ using fewer than eight inputs. Similarly, the eight-input quadratic CS factory is optimal.
• New Lower Bounds for T States: For distilling a single $T$ state with quadratic suppression ($d=2$), the paper proves that eight inputs are insufficient. The minimum required is nine inputs. The authors explicitly construct a nine-input factory with an ideal-input acceptance probability of $1/128$ and an error coefficient of $27/2$, improving upon the previous best of ten inputs.
• General Lower Bounds:
  • For rational targets (non-stabilizer states) at order $d$, $n \ge 2d + 1$.
  • For one $T$ state at order $d$, $n \ge 2d$.
  • These bounds hold for arbitrary postselection and exceed previous general bounds of $\max(d, \nu)$, where $\nu$ is the stabilizer nullity.
• Constructive Improvements:
  • A two-level design yields a quartic ($d=4$) CCZ factory using 48 inputs, achieving a leading error coefficient of $864p^4$, which is less than one-third of the previous best for 48 inputs.
  • A 36-input cubic ($d=3$) CCZ factory is rediscovered, improving upon the previous best of 47 inputs for that class.
  • A six-input protocol for the CCCZ state is confirmed as optimal for $d=1$.

Significance
The paper claims to settle the question of whether adaptivity, postselection, or multistage processing can reduce the resource cost of small magic-state factories. By proving that every such protocol is equivalent to a single stabilizer code projection, the authors demonstrate that for small factories (specifically quadratic suppression of $T$, CS, and CCZ states), no such strategies can reduce the input count below the limits found by exhaustive code searches.

The results provide the first exact lower bounds that survive arbitrary postselection and strictly exceed the stabilizer nullity bound for rational targets. While the paper acknowledges gaps remain for higher-order suppression (e.g., cubic and quartic $T$ states), it establishes that the "single-code reduction" removes the trade-off between protocol complexity and resource efficiency for the regimes most relevant to near-term fault-tolerant architectures where cultivated inputs already possess low error rates. The work complements existing asymptotic constructions and exact concentration results by defining the precise resource costs for the small-scale factories used in practical implementations.