Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.31115

The limits of magic-state distillation

Llorenç Balada Gaggioli, Jakub Mareček

quant-phSubmitted Oct 22, 2026• Announced Oct 23, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
5 pages, 10 pages of Supplemental Material, 1 figure, 3 tables

Related papers

Symmetry and AI-assisted discovery of magic-state factories

Shubham P. Jain, Adam Wills, Shraddha Singh

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.

quant-pharXiv:2610.06535•Oct 6, 2026•0 citations

Borrowed Identities: Malleable Distillation Factories and a Unified Numerical Search

Shraddha Singh, Craig Gidney, Cody Jones

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\rangle$, $|CS\rangle$, and $|CCZ\rangle$ 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.

quant-pharXiv:2606.28518•Jun 30, 2026•8 citations

Universal magic state concentration

Jacopo Rizzo, Lorenzo Leone

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 $\mathrm{CCZ}$ state, with six copies being minimal. Their success probabilities are governed by the linearized order-three stabilizer Rényi entropy $M^{\mathrm{lin}}_3$. We show that this connection is structural: for up to nine input copies, $M^{\mathrm{lin}}_3$ 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 $\mathrm{CCZ}$-state injection. Together, these results identify the stabilizer Rényi entropy as a fundamental operational quantity in magic state distillation.

quant-pharXiv:2608.13376•Aug 14, 2026•2 citations

Small codes for magic state distillation

Mark Howard, Hillary Dawkins

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.

arXiv:1512.04765•The European Physical Journal D•Mar 1, 2016•9 citations

Exploring the landscape of compact magic-state distillation factories

Hugo Jacinto, Xavier Valcarce, Victor Barizien +2 more

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-$\mathrm{CC}Z$ 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-$\mathrm{CC}Z$ 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.

quant-pharXiv:2606.07734•Jun 9, 2026•10 citations

Topics in Fault-Tolerant Quantum Computation

Hillary Dawkins

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.

•Jan 12, 2017•0 citations
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 ddd, one T state needs n≥2dn\geq2dn≥2d.
How many noisy T states are necessary to distill a target magic state with output error O(pd)O(p^d)O(pd) when arbitrary adaptive, postselected and multistage stabilizer protocols are allowed? The paper studies inputs with independent Z faults of probability ppp, 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/1281/1281/128 and has error 272p2+O(p3)\frac{27}{2}p^2+O(p^3)227​p2+O(p3). General bounds are n≥2dn\geq2dn≥2d for one T state when d≥2d\geq2d≥2 and n≥2d+1n\geq2d+1n≥2d+1 for rational nonstabilizer targets. A 48-input quartic CCZ construction has leading error 864p4864p^4864p4, versus the previously reported 2816p42816p^42816p4.
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γ= 1.589γ=1.589 and γ=1.057γ= 1.057γ=1.057. Our [[1715, 287, 6]] factory, with γ=0.998γ= 0.998γ=0.998, is the smallest known pure-T factory with γ<1γ< 1γ<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⟩|T\rangle∣T⟩, ∣CS⟩|CS\rangle∣CS⟩, and ∣CCZ⟩|CCZ\rangle∣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 TTT-state concentration, we build six- and eight-copy protocols producing an exact CCZ\mathrm{CCZ}CCZ state, with six copies being minimal. Their success probabilities are governed by the linearized order-three stabilizer Rényi entropy M3linM^{\mathrm{lin}}_3M3lin​. We show that this connection is structural: for up to nine input copies, M3linM^{\mathrm{lin}}_3M3lin​ 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\mathrm{CCZ}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 TTT-to-TTT distillation protocol on fewer than eight qubits can exceed distance 3, and no TTT-to-CCZ\mathrm{CC}ZCCZ 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 TTT-to-TTT protocols supported on 10 and 11 qubits, as well as distance 3 and 4 TTT-to-CCZ\mathrm{CC}ZCCZ 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 49T49T49T-to-1T1T1T 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.