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:1709.02832 · Quantum

Codes and Protocols for Distilling T , controlled- S , and Toffoli Gates

Jeongwan Haah, Matthew B. Hastings

Published Jun 7, 2018• 78 citations
arXivHTMLPDF

Abstract

We present several different codes and protocols to distill T , controlled- S , and Toffoli (or C C Z ) gates. One construction is based on codes that generalize the triorthogonal codes, allowing any of these gates to be induced at the logical level by transversal T . We present a randomized construction of generalized triorthogonal codes obtaining an asymptotic distillation efficiency γ → 1 . We also present a Reed-Muller based construction of these codes which obtains a worse γ but performs well at small sizes. Additionally, we present protocols based on checking the stabilizers of C C Z magic states at the logical level by transversal gates applied to codes; these protocols generalize the protocols of. Several examples, including a Reed-Muller code for T -to-Toffoli distillation, punctured Reed-Muller codes for T -gate distillation, and some of the check based protocols, require a lower ratio of input gates to output gates than other known protocols at the given order of error correction for the given code size. In particular, we find a 512 T-gate to 10 Toffoli gate code with distance 8 as well as triorthogonal codes with parameters [ [ 887 , 137 , 5 ] ] , [ [ 912 , 112 , 6 ] ] , [ [ 937 , 87 , 7 ] ] with very low prefactors in front of the leading order error terms in those codes.

DOI
10.22331/q-2018-06-07-71

Related papers

Magic-state distillation with low overhead

Sergey B. Bravyi, Jeongwan Haah

We propose a family of error-detecting stabilizer codes with an encoding rate of $1/3$ that permit a transversal implementation of the gate $T=\mathrm{exp}(\ensuremath{-}i\ensuremath{\pi}Z/8)$ on all logical qubits. These codes are used to construct protocols for distilling high-quality ``magic'' states $T\left|+\right\ensuremath{\rangle}$ by Clifford group gates and Pauli measurements. The distillation overhead scales as $O({\mathrm{log}}^{\ensuremath{\gamma}}(1/\ensuremath{\epsilon}))$, where $\ensuremath{\epsilon}$ is the output accuracy and $\ensuremath{\gamma}={\mathrm{log}}_{2}(3)\ensuremath{\approx}1.6$. To construct the desired family of codes, we introduce the notion of a triorthogonal matrix, a binary matrix in which any pair and any triple of rows have even overlap. Any triorthogonal matrix gives rise to a stabilizer code with a transversal $T$ gate on all logical qubits, possibly augmented by Clifford gates. A powerful numerical method for generating triorthogonal matrices is proposed. Our techniques lead to a twofold overhead reduction for distilling magic states with accuracy $\ensuremath{\epsilon}\ensuremath{\sim}{10}^{\ensuremath{-}12}$ compared with previously known protocols.

arXiv:1209.2426•Physical Review A•Nov 27, 2012•344 citations

Transversal Toffoli-gate in Hybrid-code System

Dawei Jiao, Mahdi Bayanifar, Alexei Ashikhmin +1 more

We study the transversality of the Toffoli gate in a hybrid-code system that employs two quantum error correction codes with special structure. We find that a system using a triorthogonal code with its paired code supports a fully transversal implementation of the Toffoli gate. Through circuit-level analysis, we prove the transversality of the Toffoli operation in this system. Based on this hybrid-code framework, we propose a Toffoli state distillation protocol that does not rely on pre-distilled $\mathbf{T}$-gate magic states. In our approach, the Toffoli state is directly distilled layer by layer within the hybrid-code system using only transversal operations. Numerical simulations demonstrate that our method uses approximately 50\% fewer qubit resources than previously reported protocols.

quant-pharXiv:2511.09265•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Nov 13, 2025•0 citations

Classification of small triorthogonal codes

Sepehr Nezami, Jeongwan Haah

Triorthogonal codes are a class of quantum error-correcting codes used in magic state distillation protocols. We classify all triorthogonal codes with $n+k\ensuremath{\le}38$, where $n$ is the number of physical qubits and $k$ is the number of logical qubits of the code. We find 38 distinguished triorthogonal subspaces, and we show that every triorthogonal code with $n+k\ensuremath{\le}38$ descends from one of these subspaces through elementary operations such as puncturing and deleting qubits. Specifically, we associate each triorthogonal code with a Reed-Muller polynomial of weight $n+k$, and we classify the Reed-Muller polynomials of low weight using the results of Kasami, Tokura, and Azumi [IEEE Trans. Inf. Theory 16, 752 (1970); Inf. Contr. 30, 380 (1976)] and an extensive computerized search. In an Appendix independent of the main text, we improve a magic state distillation protocol by reducing the time variance due to stochastic Clifford corrections.

arXiv:2107.09684•Physical Review A•Jul 28, 2022•15 citations

Improved Quantum Codes with Transversal T Gates

Adam Wills

In this work, we study quantum CSS codes with transversal $T$ gates. Here, $T$ gate transversality is meant in the strongest sense; the application of physical $T$ to every physical qubit yields logical $T$ on every logical qubit, without Clifford corrections. Despite the importance of the $T$ gate in fault-tolerant quantum computation, the parameters of asymptotic families of such codes have not been improved since the work of Hastings and Haah in 2017, and Haah in 2018. In this work, we significantly broaden the achievable parameters of quantum code families with transversal $T$ gates, both expanding the regime of achievable polynomial rate and distance, and constructing such codes with constant rate and growing distance; this is the first time the latter has been achieved, even when allowing Clifford corrections after the transversal $T$ gate. These are also the first codes achieving $γ\to 0$ for a code with a transversal $T$ gate, where $γ$ is the overhead exponent of magic state distillation. To do this, we develop a framework of divisible decreasing monomial codes, punctured at a downward-closed set on the Boolean hypercube to create logical qubits. We prove a closed-form expression for the distance of such a code punctured at such a set, which may be of independent interest. We first instantiate this with an explicit construction based on weighted Reed-Muller codes, puncturing at low Hamming-weight points, and then with a randomised construction, where a small random set of points is protected from the puncturing to save quantum code distance, achieving improved parameters.

quant-pharXiv:2608.24000•Aug 26, 2026•0 citations

Classical Coding Problem from Transversal T Gates

Narayanan Rengaswamy, Robert Calderbank, Michael Newman +1 more

Universal quantum computation requires the implementation of a logical non-Clifford gate. In this paper, we characterize all stabilizer codes whose code subspaces are preserved under physical T and T†gates. For example, this could enable magic state distillation with non-CSS codes and, thus, provide better parameters than CSS-based protocols. However, among non-degenerate stabilizer codes that support transversal T, we prove that CSS codes are optimal. We also show that triorthogonal codes are, essentially, the only family of CSS codes that realize logical transversal T via physical transversal T. Using our algebraic approach, we reveal new purely-classical coding problems that are intimately related to the realization of logical operations via transversal T. Decreasing monomial codes are also used to construct a code that realizes logical CCZ. Finally, we use Ax's theorem to characterize the logical operation realized on a family of quantum Reed-Muller codes. This result is generalized to finer angle Z-rotations in https://arxiv.org/abs/1910.09333.

arXiv:2001.04887•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2020•17 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
We present several different codes and protocols to distill T , controlled- S , and Toffoli (or C C Z ) gates. One construction is based on codes that generalize the triorthogonal codes, allowing any of these gates to be induced at the logical level by transversal T . We present a randomized construction of generalized triorthogonal codes obtaining an asymptotic distillation efficiency γ → 1 . We also present a Reed-Muller based construction of these codes which obtains a worse γ but performs well at small sizes. Additionally, we present protocols based on checking the stabilizers of C C Z magic states at the logical level by transversal gates applied to codes; these protocols generalize the protocols of. Several examples, including a Reed-Muller code for T -to-Toffoli distillation, punctured Reed-Muller codes for T -gate distillation, and some of the check based protocols, require a lower ratio of input gates to output gates than other known protocols at the given order of error correction for the given code size. In particular, we find a 512 T-gate to 10 Toffoli gate code with distance 8 as well as triorthogonal codes with parameters [ [ 887 , 137 , 5 ] ] , [ [ 912 , 112 , 6 ] ] , [ [ 937 , 87 , 7 ] ] with very low prefactors in front of the leading order error terms in those codes.
We propose a family of error-detecting stabilizer codes with an encoding rate of 1/31/31/3 that permit a transversal implementation of the gate $T=\mathrm{exp}(\ensuremath{-}i\ensuremath{\pi}Z/8)$ on all logical qubits. These codes are used to construct protocols for distilling high-quality ``magic'' states $T\left|+\right\ensuremath{\rangle}$ by Clifford group gates and Pauli measurements. The distillation overhead scales as $O({\mathrm{log}}^{\ensuremath{\gamma}}(1/\ensuremath{\epsilon}))$, where $\ensuremath{\epsilon}$ is the output accuracy and $\ensuremath{\gamma}={\mathrm{log}}_{2}(3)\ensuremath{\approx}1.6$. To construct the desired family of codes, we introduce the notion of a triorthogonal matrix, a binary matrix in which any pair and any triple of rows have even overlap. Any triorthogonal matrix gives rise to a stabilizer code with a transversal TTT gate on all logical qubits, possibly augmented by Clifford gates. A powerful numerical method for generating triorthogonal matrices is proposed. Our techniques lead to a twofold overhead reduction for distilling magic states with accuracy $\ensuremath{\epsilon}\ensuremath{\sim}{10}^{\ensuremath{-}12}$ compared with previously known protocols.
We study the transversality of the Toffoli gate in a hybrid-code system that employs two quantum error correction codes with special structure. We find that a system using a triorthogonal code with its paired code supports a fully transversal implementation of the Toffoli gate. Through circuit-level analysis, we prove the transversality of the Toffoli operation in this system. Based on this hybrid-code framework, we propose a Toffoli state distillation protocol that does not rely on pre-distilled T\mathbf{T}T-gate magic states. In our approach, the Toffoli state is directly distilled layer by layer within the hybrid-code system using only transversal operations. Numerical simulations demonstrate that our method uses approximately 50\% fewer qubit resources than previously reported protocols.
Triorthogonal codes are a class of quantum error-correcting codes used in magic state distillation protocols. We classify all triorthogonal codes with $n+k\ensuremath{\le}38$, where nnn is the number of physical qubits and kkk is the number of logical qubits of the code. We find 38 distinguished triorthogonal subspaces, and we show that every triorthogonal code with $n+k\ensuremath{\le}38$ descends from one of these subspaces through elementary operations such as puncturing and deleting qubits. Specifically, we associate each triorthogonal code with a Reed-Muller polynomial of weight n+kn+kn+k, and we classify the Reed-Muller polynomials of low weight using the results of Kasami, Tokura, and Azumi [IEEE Trans. Inf. Theory 16, 752 (1970); Inf. Contr. 30, 380 (1976)] and an extensive computerized search. In an Appendix independent of the main text, we improve a magic state distillation protocol by reducing the time variance due to stochastic Clifford corrections.
In this work, we study quantum CSS codes with transversal TTT gates. Here, TTT gate transversality is meant in the strongest sense; the application of physical TTT to every physical qubit yields logical TTT on every logical qubit, without Clifford corrections. Despite the importance of the TTT gate in fault-tolerant quantum computation, the parameters of asymptotic families of such codes have not been improved since the work of Hastings and Haah in 2017, and Haah in 2018. In this work, we significantly broaden the achievable parameters of quantum code families with transversal TTT gates, both expanding the regime of achievable polynomial rate and distance, and constructing such codes with constant rate and growing distance; this is the first time the latter has been achieved, even when allowing Clifford corrections after the transversal TTT gate. These are also the first codes achieving γ→0γ\to 0γ→0 for a code with a transversal TTT gate, where γγγ is the overhead exponent of magic state distillation. To do this, we develop a framework of divisible decreasing monomial codes, punctured at a downward-closed set on the Boolean hypercube to create logical qubits. We prove a closed-form expression for the distance of such a code punctured at such a set, which may be of independent interest. We first instantiate this with an explicit construction based on weighted Reed-Muller codes, puncturing at low Hamming-weight points, and then with a randomised construction, where a small random set of points is protected from the puncturing to save quantum code distance, achieving improved parameters.
Universal quantum computation requires the implementation of a logical non-Clifford gate. In this paper, we characterize all stabilizer codes whose code subspaces are preserved under physical T and T†gates. For example, this could enable magic state distillation with non-CSS codes and, thus, provide better parameters than CSS-based protocols. However, among non-degenerate stabilizer codes that support transversal T, we prove that CSS codes are optimal. We also show that triorthogonal codes are, essentially, the only family of CSS codes that realize logical transversal T via physical transversal T. Using our algebraic approach, we reveal new purely-classical coding problems that are intimately related to the realization of logical operations via transversal T. Decreasing monomial codes are also used to construct a code that realizes logical CCZ. Finally, we use Ax's theorem to characterize the logical operation realized on a family of quantum Reed-Muller codes. This result is generalized to finer angle Z-rotations in https://arxiv.org/abs/1910.09333.
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.