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:1811.08461 · Physical Review Letters

Towards Low Overhead Magic State Distillation

Anirudh Krishna, Jean–Pierre Tillich

Published Aug 16, 2019• 74 citations
arXivHTMLPDF

Abstract

Magic-state distillation is a resource intensive subroutine for quantum computation. The ratio of noisy input states to output states with an error rate at most ε scales as O(log^{γ}(1/ε)) [S. Bravyi and J. Haah, Magic-state distillation with low overhead, Phys. Rev. A 86, 052329 (2012)10.1103/PhysRevA.86.052329]. In a breakthrough paper, Hastings and Haah [Distillation with Sublogarithmic Overhead, Phys. Rev. Lett. 120, 050504 (2018)10.1103/PhysRevLett.120.050504] showed that it is possible to construct distillation routines with a sublogarithmic overhead, achieving γ≈0.6779 and falsifying a conjecture that γ is lower bounded by 1. They then ask whether γ can be made arbitrarily close to 0. We answer this question in the affirmative for magic-state distillation routines using qudits of prime dimension (d dimensional quantum systems for prime d).

DOI
10.1103/physrevlett.123.070507

Related papers

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•4 citations

Distillation with Sublogarithmic Overhead

Matthew B. Hastings, Jeongwan Haah

It has been conjectured that, for any distillation protocol for magic states for the $T$ gate, the number of noisy input magic states required per output magic state at output error rate $\ensuremath{\epsilon}$ is $\mathrm{\ensuremath{\Omega}}[\mathrm{log}(1/\ensuremath{\epsilon})]$. We show that this conjecture is false. We find a family of quantum error correcting codes of parameters $⟦\ensuremath{\sum}_{i=w+1}^{m}(\genfrac{}{}{0}{}{m}{i}),\ensuremath{\sum}_{i=0}^{w}(\genfrac{}{}{0}{}{m}{i}),\ensuremath{\sum}_{i=w+1}^{r+1}(\genfrac{}{}{0}{}{r+1}{i})⟧$ for any integers $m>2r$, $r>w\ensuremath{\ge}0$, by puncturing quantum Reed-Muller codes. When $m>\ensuremath{\nu}r$, our code admits a transversal logical gate at the $\ensuremath{\nu}$th level of Clifford hierarchy. In a distillation protocol for magic states at the level $\ensuremath{\nu}=3$ ($T$ gate), the ratio of input to output magic states is $O\mathbf{(}{\mathrm{log}}^{\ensuremath{\gamma}}(1/\ensuremath{\epsilon})\mathbf{)}$, where $\ensuremath{\gamma}=\mathrm{log}(n/k)/\mathrm{log}(d)<0.678$ for some $m$, $r$, $w$. The smallest code in our family for which $\ensuremath{\gamma}<1$ is on $\ensuremath{\approx}{2}^{58}$ qubits.

arXiv:1709.03543•Physical Review Letters•Jan 31, 2018•67 citations

Asymptotic magic state distillation with almost linear rate

Koki Ehara, Ryuji Takagi

The overhead exponent -- characterizing the scaling of the number of noisy magic states with respect to the target distillation error -- has been a central quantity to benchmark magic state distillation protocols. On the other hand, a related but less investigated quantity motivated by an information-theoretic viewpoint is the asymptotic distillation rate, the largest ratio of output to input magic states such that error vanishes asymptotically. These two quantities are tightly related in the specific case -- the overhead exponent is zero if and only if the asymptotic distillation rate is linear. However, their relationship in other regimes has been unclear. Here, we show that their quantitative relation is generally not robust, by presenting a family of magic state distillation protocols with an overhead exponent not close to zero -- in fact, larger than one -- that still achieves the asymptotic rate arbitrarily close to the linear rate. This implies that the distillation rate is not constrained by the overhead exponent within the sublinear rate regime. Notably, our protocol is based on error checking by measurements of logical Clifford operators, which underlies the recent magic state cultivation protocol, suggesting the potential of this mechanism for asymptotic magic state distillation.

quant-pharXiv:2605.30108•May 29, 2026•0 citations

Low Overhead Qutrit Magic State Distillation

Shiroman Prakash, Tanay Saha

We show that using qutrits rather than qubits leads to a substantial reduction in the overhead cost associated with an approach to fault-tolerant quantum computing known as magic state distillation. We construct a family of [[9m−k,k,2]]3 triorthogonal qutrit error-correcting codes for any positive integers m and k with k≤3m−2 that are suitable for magic state distillation. In magic state distillation, the number of ancillae required to produce a magic state with target error rate ϵ is O(logγ⁡ϵ−1) , where the yield parameter γ characterizes the overhead cost. For k=3m−2 , our codes have γ=log2⁡(2+63m−2) , which tends to 1 as m→∞ . Moreover, the [[20,7,2]]3 qutrit code that arises from our construction when m=3 already has a yield parameter of 1.51 which outperforms all known qubit triorthogonal codes of size less than a few hundred qubits.

arXiv:2403.06228•Quantum•Jun 12, 2025•10 citations

Magic State Distillation using Asymptotically Good Codes on Qudits

Michael J. Cervia, Henry Lamm, Diyi Liu +2 more

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.

quant-pharXiv:2512.21874•Dec 29, 2025•11 citations

Multilevel distillation of magic states for quantum computing

Cody Jones

We develop a procedure for distilling magic states used in universal quantum computing that requires substantially fewer initial resources than prior schemes. Our distillation circuit is based on a family of concatenated quantum codes that possess a transversal Hadamard operation, enabling each of these codes to distill the eigenstate of the Hadamard operator. A crucial result of this design is that low-fidelity magic states can be consumed to purify other high-fidelity magic states to even higher fidelity, which we call multilevel distillation. When distilling in the asymptotic regime of infidelity $\ensuremath{\epsilon}\ensuremath{\rightarrow}0$ for each input magic state, the number of input magic states consumed on average to yield an output state with infidelity $O({\ensuremath{\epsilon}}^{{2}^{r}})$ approaches ${2}^{r}+1$, which comes close to saturating the conjectured bound in another investigation [Bravyi and Haah, Phys. Rev. A 86, 052329 (2012)]. We show numerically that there exist multilevel protocols such that the average number of magic states consumed to distill from error rate ${\ensuremath{\epsilon}}_{\mathrm{in}}=0.01$ to ${\ensuremath{\epsilon}}_{\mathrm{out}}$ in the range ${10}^{\ensuremath{-}5}$--${10}^{\ensuremath{-}40}$ is about $14{\mathrm{log}}_{10}(1/{\ensuremath{\epsilon}}_{\mathrm{out}})\ensuremath{-}40$; the efficiency of multilevel distillation dominates all other reported protocols when distilling Hadamard magic states from initial infidelity 0.01 to any final infidelity below ${10}^{\ensuremath{-}7}$. These methods are an important advance for magic-state distillation circuits in high-performance quantum computing and provide insight into the limitations of nearly resource-optimal quantum error correction.

arXiv:1210.3388•Physical Review A•Apr 4, 2013•144 citations
Magic-state distillation is a resource intensive subroutine for quantum computation. The ratio of noisy input states to output states with an error rate at most ε scales as O(log^{γ}(1/ε)) [S. Bravyi and J. Haah, Magic-state distillation with low overhead, Phys. Rev. A 86, 052329 (2012)10.1103/PhysRevA.86.052329]. In a breakthrough paper, Hastings and Haah [Distillation with Sublogarithmic Overhead, Phys. Rev. Lett. 120, 050504 (2018)10.1103/PhysRevLett.120.050504] showed that it is possible to construct distillation routines with a sublogarithmic overhead, achieving γ≈0.6779 and falsifying a conjecture that γ is lower bounded by 1. They then ask whether γ can be made arbitrarily close to 0. We answer this question in the affirmative for magic-state distillation routines using qudits of prime dimension (d dimensional quantum systems for prime d).
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.
It has been conjectured that, for any distillation protocol for magic states for the TTT gate, the number of noisy input magic states required per output magic state at output error rate $\ensuremath{\epsilon}$ is $\mathrm{\ensuremath{\Omega}}[\mathrm{log}(1/\ensuremath{\epsilon})]$. We show that this conjecture is false. We find a family of quantum error correcting codes of parameters $⟦\ensuremath{\sum}_{i=w+1}^{m}(\genfrac{}{}{0}{}{m}{i}),\ensuremath{\sum}_{i=0}^{w}(\genfrac{}{}{0}{}{m}{i}),\ensuremath{\sum}_{i=w+1}^{r+1}(\genfrac{}{}{0}{}{r+1}{i})⟧$ for any integers m>2rm>2rm>2r, $r>w\ensuremath{\ge}0$, by puncturing quantum Reed-Muller codes. When $m>\ensuremath{\nu}r$, our code admits a transversal logical gate at the $\ensuremath{\nu}$th level of Clifford hierarchy. In a distillation protocol for magic states at the level $\ensuremath{\nu}=3$ (TTT gate), the ratio of input to output magic states is $O\mathbf{(}{\mathrm{log}}^{\ensuremath{\gamma}}(1/\ensuremath{\epsilon})\mathbf{)}$, where $\ensuremath{\gamma}=\mathrm{log}(n/k)/\mathrm{log}(d)<0.678$ for some mmm, rrr, www. The smallest code in our family for which $\ensuremath{\gamma}<1$ is on $\ensuremath{\approx}{2}^{58}$ qubits.
The overhead exponent -- characterizing the scaling of the number of noisy magic states with respect to the target distillation error -- has been a central quantity to benchmark magic state distillation protocols. On the other hand, a related but less investigated quantity motivated by an information-theoretic viewpoint is the asymptotic distillation rate, the largest ratio of output to input magic states such that error vanishes asymptotically. These two quantities are tightly related in the specific case -- the overhead exponent is zero if and only if the asymptotic distillation rate is linear. However, their relationship in other regimes has been unclear. Here, we show that their quantitative relation is generally not robust, by presenting a family of magic state distillation protocols with an overhead exponent not close to zero -- in fact, larger than one -- that still achieves the asymptotic rate arbitrarily close to the linear rate. This implies that the distillation rate is not constrained by the overhead exponent within the sublinear rate regime. Notably, our protocol is based on error checking by measurements of logical Clifford operators, which underlies the recent magic state cultivation protocol, suggesting the potential of this mechanism for asymptotic magic state distillation.
We show that using qutrits rather than qubits leads to a substantial reduction in the overhead cost associated with an approach to fault-tolerant quantum computing known as magic state distillation. We construct a family of [[9m−k,k,2]]3 triorthogonal qutrit error-correcting codes for any positive integers m and k with k≤3m−2 that are suitable for magic state distillation. In magic state distillation, the number of ancillae required to produce a magic state with target error rate ϵ is O(logγ⁡ϵ−1) , where the yield parameter γ characterizes the overhead cost. For k=3m−2 , our codes have γ=log2⁡(2+63m−2) , which tends to 1 as m→∞ . Moreover, the [[20,7,2]]3 qutrit code that arises from our construction when m=3 already has a yield parameter of 1.51 which outperforms all known qubit triorthogonal codes of size less than a few hundred qubits.
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 develop a procedure for distilling magic states used in universal quantum computing that requires substantially fewer initial resources than prior schemes. Our distillation circuit is based on a family of concatenated quantum codes that possess a transversal Hadamard operation, enabling each of these codes to distill the eigenstate of the Hadamard operator. A crucial result of this design is that low-fidelity magic states can be consumed to purify other high-fidelity magic states to even higher fidelity, which we call multilevel distillation. When distilling in the asymptotic regime of infidelity $\ensuremath{\epsilon}\ensuremath{\rightarrow}0$ for each input magic state, the number of input magic states consumed on average to yield an output state with infidelity $O({\ensuremath{\epsilon}}^{{2}^{r}})$ approaches 2r+1{2}^{r}+12r+1, which comes close to saturating the conjectured bound in another investigation [Bravyi and Haah, Phys. Rev. A 86, 052329 (2012)]. We show numerically that there exist multilevel protocols such that the average number of magic states consumed to distill from error rate ${\ensuremath{\epsilon}}_{\mathrm{in}}=0.01$ to ${\ensuremath{\epsilon}}_{\mathrm{out}}$ in the range ${10}^{\ensuremath{-}5}$--${10}^{\ensuremath{-}40}$ is about $14{\mathrm{log}}_{10}(1/{\ensuremath{\epsilon}}_{\mathrm{out}})\ensuremath{-}40$; the efficiency of multilevel distillation dominates all other reported protocols when distilling Hadamard magic states from initial infidelity 0.01 to any final infidelity below ${10}^{\ensuremath{-}7}$. These methods are an important advance for magic-state distillation circuits in high-performance quantum computing and provide insight into the limitations of nearly resource-optimal quantum error correction.