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:2512.21874

Magic State Distillation using Asymptotically Good Codes on Qudits

Michael J. Cervia, Henry Lamm, Diyi Liu, Edison M. Murairi, Shuchen Zhu

quant-phSubmitted Dec 26, 2025• Announced Dec 29, 2025• 0 citations
arXivHTMLPDF

Abstract

Qudits offer the potential for low-overhead magic state distillation, although previous results for asymptotically good codes have required qudit dimension $q\gg 100$ or code length $\mathcal{N}\gg 100$. These parameters far exceed experimental demonstrations of qudit platforms, and thus motivate the search for better codes. Using a novel lifting procedure, we construct the first family of good triorthogonal codes on the $\mathbb{F}_{2^{2m}}$ alphabet with $m \geq 3$ that lies above the Tsfasman-Vladut-Zink bound. These codes yield a family of asymptotically good quantum codes with transversal CCZ gates, enabling constant space overhead magic state distillation with qudit dimension as small as $q=64$. Further, we identify a promising code with parameters $[[42,14,6]]_{64}$. Finally, we show that a distilled $|{CCZ}\rangle_{2^{2m}}$ can be reduced to a $|{CCZ}\rangle_{2^n}$ state for arbitrary $n$ with a constant-depth Clifford circuit of at most 9 computational basis measurements, 12 single-qudit and 9 two-qudit Clifford gates.

Comments
15 pages, 2 figures

Related papers

Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates

Louis Golowich, Venkatesan Guruswami

We construct quantum codes that support transversal $CCZ$ gates over qudits of arbitrary prime power dimension $q$ (including $q=2$) such that the code dimension and distance grow linearly in the block length. The only previously known construction with such linear dimension and distance required a growing alphabet size $q$ (Krishna & Tillich, 2019). Our codes imply protocols for magic state distillation with overhead exponent $γ=\log(n/k)/\log(d)\rightarrow 0$ as the block length $n\rightarrow\infty$, where $k$ and $d$ denote the code dimension and distance respectively. It was previously an open question to obtain such a protocol with a contant alphabet size $q$. We construct our codes by combining two modular components, namely, (i) a transformation from classical codes satisfying certain properties to quantum codes supporting transversal $CCZ$ gates, and (ii) a concatenation scheme for reducing the alphabet size of codes supporting transversal $CCZ$ gates. For this scheme we introduce a quantum analogue of multiplication-friendly codes, which provide a way to express multiplication over a field in terms of a subfield. We obtain our asymptotically good construction by instantiating (i) with algebraic-geometric codes, and applying a constant number of iterations of (ii). We also give an alternative construction with nearly asymptotically good parameters ($k,d=n/2^{O(\log^*n)}$) by instantiating (i) with Reed-Solomon codes and then performing a superconstant number of iterations of (ii).

arXiv:2408.09254•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•8 citations

Constant-Overhead Magic State Distillation

Adam Wills, Min-Hsiu Hsieh, Hayata Yamasaki

Magic state distillation is a crucial yet resource-intensive process in fault-tolerant quantum computation. The protocol's overhead, defined as the number of input magic states required per output magic state with an error rate below $ε$, typically grows as $\mathcal{O}(\log^γ(1/ε))$. Achieving smaller overheads, i.e., smaller exponents $γ$, is highly desirable; however, all existing protocols require polylogarithmically growing overheads with some $γ> 0$, and identifying the smallest achievable exponent $γ$ for distilling magic states of qubits has remained challenging. To address this issue, we develop magic state distillation protocols for qubits with efficient, polynomial-time decoding that achieve an $\mathcal{O}(1)$ overhead, meaning the optimal exponent $γ= 0$; this improves over the previous best of $γ\approx 0.678$ due to Hastings and Haah. In our construction, we employ algebraic geometry codes to explicitly present asymptotically good quantum codes for $2^{10}$-dimensional qudits that support transversally implementable logical gates in the third level of the Clifford hierarchy. The use of asymptotically good codes with non-vanishing rate and relative distance leads to the constant overhead. These codes can be realised by representing each $2^{10}$-dimensional qudit as a set of $10$ qubits, using stabiliser operations on qubits. The $10$-qubit magic states distilled with these codes can be converted to and from conventional magic states for the controlled-controlled-$Z$ ($CCZ$) and $T$ gates on qubits with only a constant overhead loss, making it possible to achieve constant-overhead distillation of such standard magic states for qubits. These results resolve the fundamental open problem in quantum information theory concerning the construction of magic state distillation protocols with the optimal exponent.

arXiv:2408.07764•Aug 14, 2024•4 citations

Good Binary Quantum Codes with Transversal CCZ Gate

Quynh T. Nguyen

We give an asymptotically good family of quantum CSS codes on qubits with a transversal CCZ gate, meaning that the parallel logical CCZ on all logical qubits is performed by parallel physical CCZs on (a subset of) physical qubits. The construction is based on the observation that any classical code satisfying a multiplication property can be used to construct a quantum CSS code with transversal (qudit) CCZ. To obtain a constant-rate and linear-distance family, we then instantiate this construction with a classical good family of algebraic-geometry codes on a non-binary, but constant-sized, alphabet. Finally, we use a technique from the arithmetic secret sharing literature to reduce the alphabet to binary. As a corollary, the constructed code family provides a magic state distillation scheme with constant space overhead.

arXiv:2408.10140•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•8 citations

Magic state distillation with low space overhead and optimal asymptotic input count

Jeongwan Haah, Matthew B. Hastings, David Poulin +1 more

We present an infinite family of protocols to distill magic states for T -gates that has a low space overhead and uses an asymptotic number of input magic states to achieve a given target error that is conjectured to be optimal. The space overhead, defined as the ratio between the physical qubits to the number of output magic states, is asymptotically constant, while both the number of input magic states used per output state and the T -gate depth of the circuit scale linearly in the logarithm of the target error δ (up to log ⁡ log ⁡ 1 / δ ). Unlike other distillation protocols, this protocol achieves this performance without concatenation and the input magic states are injected at various steps in the circuit rather than all at the start of the circuit. The protocol can be modified to distill magic states for other gates at the third level of the Clifford hierarchy, with the same asymptotic performance. The protocol relies on the construction of weakly self-dual CSS codes with many logical qubits and large distance, allowing us to implement control-SWAPs on multiple qubits. We call this code the "inner code". The control-SWAPs are then used to measure properties of the magic state and detect errors, using another code that we call the "outer code". Alternatively, we use weakly-self dual CSS codes which implement controlled Hadamards for the inner code, reducing circuit depth. We present several specific small examples of this protocol.

arXiv:1703.07847•Quantum•Oct 3, 2017•71 citations

Asymptotically good binary triorthogonal codes and higher-level transversal gates

Rodrigo San-José

For each level of the Clifford hierarchy from the third level onward, we construct explicit asymptotically good binary CSS codes for which a strongly transversal diagonal rotation, followed by a correction from the preceding level, implements the corresponding logical rotation. We achieve this using algebraic geometry codes over binary extension fields and performing an alphabet reduction that translates orthogonality conditions over the extension field to binary overlap conditions. In particular, we obtain the first asymptotically good family of binary triorthogonal codes. We also give a stronger construction with worse parameters for which the strongly transversal physical rotation implements the desired logical rotation, with no subsequent correction. Finally, adapting an error-correction-based distillation protocol, our binary $T$-gate families yield direct constant-overhead $T$-state block distillation from noisy $T$-state inputs under sufficiently weak input noise and ideal stabilizer operations.

cs.ITCross-listedarXiv:2609.08203•Sep 9, 2026•0 citations

Sublogarithmic distillation in all prime dimensions using punctured Reed-Muller codes

Tanay Saha, Shiroman Prakash

Magic state distillation is a leading but costly approach to fault-tolerant quantum computation, and it is important to explore all possible ways of minimizing its overhead cost. The number of ancillae required to produce a magic state within a target error rate $ε$ is $O(\log^γ (ε^{-1}))$ where $γ$ is known as the yield parameter. Hastings and Haah derived a family of distillation protocols with sublogarithmic overhead (i.e., $γ< 1$) based on punctured Reed-Muller codes. Building on work by Campbell \textit{et al.} and Krishna-Tillich, which suggests that qudits of dimension $p>2$ can significantly reduce overhead, we generalize their construction to qudits of arbitrary prime dimension $p$. We find that, in an analytically tractable puncturing scheme, the number of qudits required to achieve sublogarithmic overhead decreases drastically as $p$ increases, and the asymptotic yield parameter approaches $\frac{1}{\ln p}$ as $p \to \infty$. We also perform a small computational search for optimal puncture locations, which results in several interesting triorthogonal codes, including a $[[519,106,5]]_5$ code with $γ=0.99$.

arXiv:2510.10852•Physical Review A•Mar 9, 2026•0 citations
Qudits offer the potential for low-overhead magic state distillation, although previous results for asymptotically good codes have required qudit dimension q≫100q\gg 100q≫100 or code length N≫100\mathcal{N}\gg 100N≫100. These parameters far exceed experimental demonstrations of qudit platforms, and thus motivate the search for better codes. Using a novel lifting procedure, we construct the first family of good triorthogonal codes on the F22m\mathbb{F}_{2^{2m}}F22m​ alphabet with m≥3m \geq 3m≥3 that lies above the Tsfasman-Vladut-Zink bound. These codes yield a family of asymptotically good quantum codes with transversal CCZ gates, enabling constant space overhead magic state distillation with qudit dimension as small as q=64q=64q=64. Further, we identify a promising code with parameters [[42,14,6]]64[[42,14,6]]_{64}[[42,14,6]]64​. Finally, we show that a distilled ∣CCZ⟩22m|{CCZ}\rangle_{2^{2m}}∣CCZ⟩22m​ can be reduced to a ∣CCZ⟩2n|{CCZ}\rangle_{2^n}∣CCZ⟩2n​ state for arbitrary nnn with a constant-depth Clifford circuit of at most 9 computational basis measurements, 12 single-qudit and 9 two-qudit Clifford gates.
We construct quantum codes that support transversal CCZCCZCCZ gates over qudits of arbitrary prime power dimension qqq (including q=2q=2q=2) such that the code dimension and distance grow linearly in the block length. The only previously known construction with such linear dimension and distance required a growing alphabet size qqq (Krishna & Tillich, 2019). Our codes imply protocols for magic state distillation with overhead exponent γ=log⁡(n/k)/log⁡(d)→0γ=\log(n/k)/\log(d)\rightarrow 0γ=log(n/k)/log(d)→0 as the block length n→∞n\rightarrow\inftyn→∞, where kkk and ddd denote the code dimension and distance respectively. It was previously an open question to obtain such a protocol with a contant alphabet size qqq. We construct our codes by combining two modular components, namely, (i) a transformation from classical codes satisfying certain properties to quantum codes supporting transversal CCZCCZCCZ gates, and (ii) a concatenation scheme for reducing the alphabet size of codes supporting transversal CCZCCZCCZ gates. For this scheme we introduce a quantum analogue of multiplication-friendly codes, which provide a way to express multiplication over a field in terms of a subfield. We obtain our asymptotically good construction by instantiating (i) with algebraic-geometric codes, and applying a constant number of iterations of (ii). We also give an alternative construction with nearly asymptotically good parameters (k,d=n/2O(log⁡∗n)k,d=n/2^{O(\log^*n)}k,d=n/2O(log∗n)) by instantiating (i) with Reed-Solomon codes and then performing a superconstant number of iterations of (ii).
Magic state distillation is a crucial yet resource-intensive process in fault-tolerant quantum computation. The protocol's overhead, defined as the number of input magic states required per output magic state with an error rate below εεε, typically grows as O(log⁡γ(1/ε))\mathcal{O}(\log^γ(1/ε))O(logγ(1/ε)). Achieving smaller overheads, i.e., smaller exponents γγγ, is highly desirable; however, all existing protocols require polylogarithmically growing overheads with some γ>0γ> 0γ>0, and identifying the smallest achievable exponent γγγ for distilling magic states of qubits has remained challenging. To address this issue, we develop magic state distillation protocols for qubits with efficient, polynomial-time decoding that achieve an O(1)\mathcal{O}(1)O(1) overhead, meaning the optimal exponent γ=0γ= 0γ=0; this improves over the previous best of γ≈0.678γ\approx 0.678γ≈0.678 due to Hastings and Haah. In our construction, we employ algebraic geometry codes to explicitly present asymptotically good quantum codes for 2102^{10}210-dimensional qudits that support transversally implementable logical gates in the third level of the Clifford hierarchy. The use of asymptotically good codes with non-vanishing rate and relative distance leads to the constant overhead. These codes can be realised by representing each 2102^{10}210-dimensional qudit as a set of 101010 qubits, using stabiliser operations on qubits. The 101010-qubit magic states distilled with these codes can be converted to and from conventional magic states for the controlled-controlled-ZZZ (CCZCCZCCZ) and TTT gates on qubits with only a constant overhead loss, making it possible to achieve constant-overhead distillation of such standard magic states for qubits. These results resolve the fundamental open problem in quantum information theory concerning the construction of magic state distillation protocols with the optimal exponent.
We give an asymptotically good family of quantum CSS codes on qubits with a transversal CCZ gate, meaning that the parallel logical CCZ on all logical qubits is performed by parallel physical CCZs on (a subset of) physical qubits. The construction is based on the observation that any classical code satisfying a multiplication property can be used to construct a quantum CSS code with transversal (qudit) CCZ. To obtain a constant-rate and linear-distance family, we then instantiate this construction with a classical good family of algebraic-geometry codes on a non-binary, but constant-sized, alphabet. Finally, we use a technique from the arithmetic secret sharing literature to reduce the alphabet to binary. As a corollary, the constructed code family provides a magic state distillation scheme with constant space overhead.
We present an infinite family of protocols to distill magic states for T -gates that has a low space overhead and uses an asymptotic number of input magic states to achieve a given target error that is conjectured to be optimal. The space overhead, defined as the ratio between the physical qubits to the number of output magic states, is asymptotically constant, while both the number of input magic states used per output state and the T -gate depth of the circuit scale linearly in the logarithm of the target error δ (up to log ⁡ log ⁡ 1 / δ ). Unlike other distillation protocols, this protocol achieves this performance without concatenation and the input magic states are injected at various steps in the circuit rather than all at the start of the circuit. The protocol can be modified to distill magic states for other gates at the third level of the Clifford hierarchy, with the same asymptotic performance. The protocol relies on the construction of weakly self-dual CSS codes with many logical qubits and large distance, allowing us to implement control-SWAPs on multiple qubits. We call this code the "inner code". The control-SWAPs are then used to measure properties of the magic state and detect errors, using another code that we call the "outer code". Alternatively, we use weakly-self dual CSS codes which implement controlled Hadamards for the inner code, reducing circuit depth. We present several specific small examples of this protocol.
For each level of the Clifford hierarchy from the third level onward, we construct explicit asymptotically good binary CSS codes for which a strongly transversal diagonal rotation, followed by a correction from the preceding level, implements the corresponding logical rotation. We achieve this using algebraic geometry codes over binary extension fields and performing an alphabet reduction that translates orthogonality conditions over the extension field to binary overlap conditions. In particular, we obtain the first asymptotically good family of binary triorthogonal codes. We also give a stronger construction with worse parameters for which the strongly transversal physical rotation implements the desired logical rotation, with no subsequent correction. Finally, adapting an error-correction-based distillation protocol, our binary TTT-gate families yield direct constant-overhead TTT-state block distillation from noisy TTT-state inputs under sufficiently weak input noise and ideal stabilizer operations.
Magic state distillation is a leading but costly approach to fault-tolerant quantum computation, and it is important to explore all possible ways of minimizing its overhead cost. The number of ancillae required to produce a magic state within a target error rate εεε is O(log⁡γ(ε−1))O(\log^γ (ε^{-1}))O(logγ(ε−1)) where γγγ is known as the yield parameter. Hastings and Haah derived a family of distillation protocols with sublogarithmic overhead (i.e., γ<1γ< 1γ<1) based on punctured Reed-Muller codes. Building on work by Campbell \textit{et al.} and Krishna-Tillich, which suggests that qudits of dimension p>2p>2p>2 can significantly reduce overhead, we generalize their construction to qudits of arbitrary prime dimension ppp. We find that, in an analytically tractable puncturing scheme, the number of qudits required to achieve sublogarithmic overhead decreases drastically as ppp increases, and the asymptotic yield parameter approaches 1ln⁡p\frac{1}{\ln p}lnp1​ as p→∞p \to \inftyp→∞. We also perform a small computational search for optimal puncture locations, which results in several interesting triorthogonal codes, including a [[519,106,5]]5[[519,106,5]]_5[[519,106,5]]5​ code with γ=0.99γ=0.99γ=0.99.