The distillation of magic states is an often-cited technique for enabling universal quantum computing once the error probability for a special subset of gates has been made negligible by other means. We present a routine for magic-state distillation that reduces the required overhead for a range of parameters of practical interest. Each iteration of the routine uses a four-qubit error-detecting code to distill the $+1$ eigenstate of the Hadamard gate at a cost of ten input states per two improved output states. Use of this routine in combination with the $15$ -to- $1$ distillation routine described by Bravyi and Kitaev allows for further improvements in overhead.The distillation of magic states is an often-cited technique for enabling universal quantum computing once the error probability for a special subset of gates has been made negligible by other means. We present a routine for magic-state distillation that reduces the required overhead for a range of parameters of practical interest. Each iteration of the routine uses a four-qubit error-detecting code to distill the $+1$ eigenstate of the Hadamard gate at a cost of ten input states per two improved output states. Use of this routine in combination with the $15$-to-$1$ distillation routine described by Bravyi and Kitaev allows for further improvements in overhead.

Quantum Information and ComputationMar 1, 201369 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.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.3388Physical Review AApr 4, 2013126 citations

Magic state distillation with permutation-invariant codes and a two-qubit example

Heather Leitch, Yingkai Ouyang

Magic states, by allowing non-Clifford gates through gate teleportation, are important building blocks of fault-tolerant quantum computation. Magic state distillation protocols aim to create clean copies of magic states from many noisier copies. However, the prevailing protocols require substantial qubit overhead. We present a distillation protocol based on permutation-invariant gnu codes, as small as two qubits. The two-qubit protocol achieves a 0.5 error threshold and 1/2 distillation rate, surpassing prior schemes for comparable codes. Our protocol furthermore distils magic states with arbitrary magic by varying the position of the ideal input states on the Bloch sphere. We achieve this by departing from the usual magic state distillation formalism, allowing the use of non-Clifford gates in the distillation protocol, and allowing the form of the output state to differ from the input state. Our protocol is compatible for use in tandem with existing magic state distillation protocols to enhance their performance.Magic states, by allowing non-Clifford gates through gate teleportation, are important building blocks of fault-tolerant quantum computation. Magic state distillation protocols aim to create clean copies of magic states from many noisier copies. However, the prevailing protocols require substantial qubit overhead. We present a distillation protocol based on permutation-invariant gnu codes, as small as two qubits. The two-qubit protocol achieves a 0.5 error threshold and 1/2 distillation rate, surpassing prior schemes for comparable codes. Our protocol furthermore distils magic states with arbitrary magic by varying the position of the ideal input states on the Bloch sphere. We achieve this by departing from the usual magic state distillation formalism, allowing the use of non-Clifford gates in the distillation protocol, and allowing the form of the output state to differ from the input state. Our protocol is compatible for use in tandem with existing magic state distillation protocols to enhance their performance.

quant-pharXiv:2603.04310Mar 5, 20260 citations

Towards Low Overhead Magic State Distillation

Anirudh Krishna, Jean–Pierre Tillich

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 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).

arXiv:1811.08461Physical Review LettersAug 16, 201960 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.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.07764Aug 14, 20244 citations

Efficient Magic State Distillation by Zero-Level Distillation

Tomohiro Itogawa, Yugo Takada, Yutaka Hirano +1 more

Magic state distillation (MSD) is an essential element for universal fault-tolerant quantum computing, which distills a high-fidelity magic state from noisy magic states using ideal (error-corrected) Clifford operations. For ideal Clifford operations, it needs to be performed on the logical qubits and hence incurs a large spatiotemporal overhead, which is one of the major bottlenecks for the realization of fault-tolerant quantum computers (FTQCs). Here we propose zero-level distillation, which prepares a high-fidelity logical magic state at the physical level, namely , using physical qubits and nearest-neighbor two-qubit gates on a square lattice. We develop a zero-level distillation circuit and show that distillation can be made even more efficient than the conventional sophisticated approaches with logical level distillations. The key idea involves the Knill -type distillation using the Steane code and its careful mapping to the square-lattice architecture with error detection. The distilled magic state on the Steane-code state is then teleported or converted to surface codes. We numerically find that the error rate of the logical magic state scales as approximately 100 × p 2 in terms of the physical error rate p . For example, with a physical error rate of p = 10 − 4 ( 10 − 3 ), the logical error rate is reduced to p L = 10 − 6 ( 10 − 4 ), resulting in an improvement of 2 (1) orders of magnitude. This contributes to reducing both space and time overhead for early FTQC as well as full-fledged FTQC combined with conventional multilevel distillation protocols.Magic state distillation (MSD) is an essential element for universal fault-tolerant quantum computing, which distills a high-fidelity magic state from noisy magic states using ideal (error-corrected) Clifford operations. For ideal Clifford operations, it needs to be performed on the logical qubits and hence incurs a large spatiotemporal overhead, which is one of the major bottlenecks for the realization of fault-tolerant quantum computers (FTQCs). Here we propose zero-level distillation, which prepares a high-fidelity logical magic state at the physical level, namely , using physical qubits and nearest-neighbor two-qubit gates on a square lattice. We develop a zero-level distillation circuit and show that distillation can be made even more efficient than the conventional sophisticated approaches with logical level distillations. The key idea involves the Knill -type distillation using the Steane code and its careful mapping to the square-lattice architecture with error detection. The distilled magic state on the Steane-code state is then teleported or converted to surface codes. We numerically find that the error rate of the logical magic state scales as approximately 100 × p 2 in terms of the physical error rate p . For example, with a physical error rate of p = 10 − 4 ( 10 − 3 ), the logical error rate is reduced to p L = 10 − 6 ( 10 − 4 ), resulting in an improvement of 2 (1) orders of magnitude. This contributes to reducing both space and time overhead for early FTQC as well as full-fledged FTQC combined with conventional multilevel distillation protocols.

arXiv:2403.03991PRX QuantumMay 22, 202522 citations

+1

eigenstate of the Hadamard gate at a cost of ten input states per two improved output states. Use of this routine in combination with the

15

-to-

1

distillation routine described by Bravyi and Kitaev allows for further improvements in overhead.

{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.

ε

, 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.