Magic-state factories are a major cost of fault-tolerant quantum computing, yet how few noisy inputs they need is known only for restricted protocols. We show that, for tolerating input faults, any stabilizer protocol, however adaptive, postselected or multistage, is no better than a projection onto one stabilizer code, and that for rational targets a fault pattern is harmful exactly when its complement is. Searches over all codes show that quadratic distillation of one T state needs exactly nine inputs and that the eight-input CCZ factory is optimal. At order $d$, one T state needs $n\geq2d$.
AI Summary
How many noisy T states are necessary to distill a target magic state with output error $O(p^d)$ when arbitrary adaptive, postselected and multistage stabilizer protocols are allowed? The paper studies inputs with independent Z faults of probability $p$, assuming ideal Clifford operations and counting inputs per run.
Two reductions underpin the results. Any protocol tolerating specified fault patterns can be replaced by a single stabilizer-code projection and Clifford decoding, preserving fault tolerance but not acceptance probability. For targets with rational Pauli expectations, Galois conjugation shows that a fault pattern is harmless exactly when its complement is. These reductions enable exhaustive searches over all input stabilizer codes, using symmetry reduction and exact arithmetic; analytic witness arguments provide bounds at arbitrary suppression order.
Quadratic distillation requires exactly nine inputs for one T state, eight for CS and eight for CCZ, establishing optimality of the existing eight-input CCZ factory. The nine-input T construction accepts ideal inputs with probability $1/128$ and has error $\frac{27}{2}p^2+O(p^3)$. General bounds are $n\geq2d$ for one T state when $d\geq2$ and $n\geq2d+1$ for rational nonstabilizer targets. A 48-input quartic CCZ construction has leading error $864p^4$, versus the previously reported $2816p^4$.
The input-count objective does not measure space-time overhead or expected consumption per accepted output; the nine-input T factory is worse on the latter metric than the previous ten-input protocol. Higher-order optima remain unresolved, including cubic T at 10–15 inputs and cubic CCZ at 10–36. Several exclusions depend on large computer-assisted searches.
No sign of AI-generated text
Error found: The abstract omits the necessary restriction d ≥ 2 from its T-state bound n ≥ 2d: passing through one noisy T state already achieves order-one error suppression with n = 1.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Magic-state factories are a major cost of fault-tolerant quantum computing, yet how few noisy inputs they need is known only for restricted protocols. We show that, for tolerating input faults, any stabilizer protocol, however adaptive, postselected or multistage, is no better than a projection onto one stabilizer code, and that for rational targets a fault pattern is harmful exactly when its complement is. Searches over all codes show that quadratic distillation of one T state needs exactly nine inputs and that the eight-input CCZ factory is optimal. At order d, one T state needs n≥2d.
How many noisy T states are necessary to distill a target magic state with output error O(pd) when arbitrary adaptive, postselected and multistage stabilizer protocols are allowed? The paper studies inputs with independent Z faults of probability p, assuming ideal Clifford operations and counting inputs per run.
Two reductions underpin the results. Any protocol tolerating specified fault patterns can be replaced by a single stabilizer-code projection and Clifford decoding, preserving fault tolerance but not acceptance probability. For targets with rational Pauli expectations, Galois conjugation shows that a fault pattern is harmless exactly when its complement is. These reductions enable exhaustive searches over all input stabilizer codes, using symmetry reduction and exact arithmetic; analytic witness arguments provide bounds at arbitrary suppression order.
Quadratic distillation requires exactly nine inputs for one T state, eight for CS and eight for CCZ, establishing optimality of the existing eight-input CCZ factory. The nine-input T construction accepts ideal inputs with probability 1/128 and has error 227p2+O(p3). General bounds are n≥2d for one T state when d≥2 and n≥2d+1 for rational nonstabilizer targets. A 48-input quartic CCZ construction has leading error 864p4, versus the previously reported 2816p4.
The input-count objective does not measure space-time overhead or expected consumption per accepted output; the nine-input T factory is worse on the latter metric than the previous ten-input protocol. Higher-order optima remain unresolved, including cubic T at 10–15 inputs and cubic CCZ at 10–36. Several exclusions depend on large computer-assisted searches.
Magic-state distillation is a major resource cost in fault-tolerant quantum computing. The cost of a magic-state factory depends strongly on its failure rate, which grows with the number of input magic states. Although symmetry-restricted methods have recently made distance two searches tractable, distance three and above have remained elusive at moderate input counts. We develop symmetry- and AI-assisted methods to search this regime. We present a unified binary-matrix formulation encompassing both triorthogonal-code and direct circuit searches. We show that distance at least three is equivalent to nonzero, pairwise distinct syndromes, separating the choice of syndromes from the search for compatible output gates. We restrict the syndrome search using group symmetry and language-model agents, followed by deterministic solving and independent verification. Our searches yield 699 factory classes, including 564 new ones. These include factories for pure-T states and factories with entangled outputs comprising combinations of T, CS, and CCZ magic states. The pure-T factories [[63, 11, 3]] and [[850, 128, 6]] achieve the lowest overhead exponents we know among protocols with at most 100 and 1000 inputs, respectively, with γ=1.589 and γ=1.057. Our [[1715, 287, 6]] factory, with γ=0.998, is the smallest known pure-T factory with γ<1. We also provide a context directory of search briefs and campaign notes with which readers can train their own agents and tailor the search to their requirements. With these results, we begin constructing an active, open-source repository of magic-state distillation protocols for the quantum community, supplemented by our methods and data, for the practical fault-tolerant quantum computing regime.
Magic-state distillation is one of the leading overheads in fault-tolerant quantum computation. Existing methods for finding distillation factories require a transversal gate to act correctly on the entire codespace, a constraint that limits both generality and search efficiency. We introduce a strictly weaker borrowed-identity condition, requiring only that the distillation circuit act as the identity on a single input state. It applies uniformly across all levels of the Clifford hierarchy and unifies, within a single level, factories that distill different magic states -- for example, the ∣T⟩, ∣CS⟩, and ∣CCZ⟩ factories. A brute-force search over borrowed-identity circuits with two-group symmetry recovers, within the search range, all distance-2 factories known from code-construction approaches, including entangled-output and multi-output factories previously outside the scope of any single numerical search. This unification yields parent circuits that encode multiple factories, so the output magic-state type can be chosen at compile time rather than fixed by a hard-coded design. The framework also extends beyond CSS codes, unifying constructions, including synthillation and non-CSS catalytic factories, previously obtained by disparate approaches.
Magic plays a dual role in quantum computation: it promotes stabilizer dynamics from efficient classical simulability to computational universality, but also challenges fault-tolerant architectures, since non-stabilizer operations are harder to protect against noise. Magic state distillation addresses this issue, yet existing protocols remain largely tailored to specific assumptions about the input or noise model and, more fundamentally, no general information-theoretic theory of optimal magic-state conversion currently exists. Here we develop such a characterization for pure qubit states through universal magic state concentration: a fixed stabilizer protocol that converts a few copies of an unknown pure non-stabilizer qubit state into an exact target magic state. Motivated by the impossibility of exact T-state concentration, we build six- and eight-copy protocols producing an exact CCZ state, with six copies being minimal. Their success probabilities are governed by the linearized order-three stabilizer Rényi entropy M3lin. We show that this connection is structural: for up to nine input copies, M3lin fully determines the success probability of every universal Clifford-invariant stabilizer protocol. Remarkably, this characterization persists asymptotically: our constructions achieve optimal rates among universal single-output protocols and remain optimal up to logarithmic factors among arbitrary stabilizer protocols. As a corollary, we show that any unknown pure non-stabilizer state suffices for universal quantum computation via probabilistic CCZ-state injection. Together, these results identify the stabilizer Rényi entropy as a fundamental operational quantity in magic state distillation.
Magic state distillation is a critical component in leading proposals for fault-tolerant quantum computation. Relatively little is known, however, about how to construct a magic state distillation routine or, more specifically, which stabilizer codes are suitable for the task. While transversality of a non-Clifford gate within a code often leads to efficient distillation routines, it appears to not be a necessary condition. Here we have examined a number of small stabilizer codes and highlight a handful of which displaying interesting, albeit inefficient, distillation behaviour. Many of these distill noisy states right up to the boundary of the known undististillable region, while some distill toward non-stabilizer states that have not previously been considered.
Producing high-fidelity magic states using the smallest possible number of physical qubits and operations stands as a very important challenge to achieve fault-tolerant quantum computation at scale. Besides emerging proposals for alternative methods such as cultivation, magic state distillation remains essential for achieving very low error rates. Known distillation protocols are usually built through quantum codes derived from triorthogonal matrices. Here, exploiting the specific noise structure present in magic state distillation protocols, we show that classical error-correcting codes offer a simpler framework for deriving these protocols. This formulation is particularly well suited to systematic numerical and analytical studies of distillation protocols involving a fixed number of qubits. Specifically, we use a SAT solver to derive a series of no-go theorems that relate key figures of merit, including the number of qubits and the factory distance. In particular, considering the standard implementation as a circuit of Z-diagonal Pauli product rotations followed by measurements, we show that no T-to-T distillation protocol on fewer than eight qubits can exceed distance 3, and no T-to-CCZ protocol distance 2. Our results also include new such distillation protocols with the smallest number of qubits for a given distance in the literature, namely distance 4 and 5 T-to-T protocols supported on 10 and 11 qubits, as well as distance 3 and 4 T-to-CCZ distillation protocols supported on 9 and 10 qubits. Finally, going beyond unitary circuits by recycling qubits through mid-circuit measurement and reinitialization, we obtain an implementation of the distance-5 49T-to-1T protocol on only 5 active qubits.
This thesis contains the results of research projects broadly related to the pursuit of universal fault-tolerant quantum computation. We are interested in questions such as which resources are required to achieve a quantum computational advantage, how to utilize such resources in practice, and how to characterize and control noise throughout a computation. \n \nIn part 1, we cover results pertaining to magic state distillation, one of the leading approaches to implementing universal fault-tolerant quantum computation. Early work in this area focused on determining the region of distillable states for qubit protocols, yet comparatively little is known about which states can be distilled and with what distillable region for d>2. In the first project, we focus on d=3 and present new four-qutrit distillation schemes that improve upon the known distillable region, and achieve distillation tight to the boundary of undistillable states for some classes of states. As a consequence of recent results, this implies that there is a family of quantum states that enable universality if and only if they exhibit contextuality with respect to stabilizer measurements. We also identify a new routine whose fixed point is a magic state with maximal sum-negativity i.e., it is maximally non-stabilizer in a specific sense. In the second project, we return to d=2 and present a number of interesting new distillation routines based on small codes. Many of these distill noisy states right up to the boundary of the known undististillable region, while some distill toward non-stabilizer states that have not previously been considered. \n \nIn part 2, we address the issue of noise characterization. The characterization of noise in a quantum system serves as a foundation towards meeting two important goals. Firstly, we may wish to know about specific sources of noise in order to adapt or correct errors as much as possible. Secondly, we would like a way to verify that noise is below some threshold value in order to meet the criteria of threshold theorems. We consider the case where noise is approximately known to coincide with the generalized damping channel (encompassing the common intrinsic processes of amplitude damping and dephasing), but may contain additional unknown noise sources. We provide methods to accurately obtain the noise parameters, and compare with the results of a randomized benchmarking experiment. Using this information, we show how to make meaningful statements about fault-tolerance threshold theorems by considering the diamond distance.