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:2107.09684 · Physical Review A

Classification of small triorthogonal codes

Sepehr Nezami, Jeongwan Haah

Published Jul 28, 2022• 15 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.106.012437

Related papers

Classification of Generalised Triorthogonal Codes through Length 54

Adam Wills, Shubham P. Jain, Shraddha Singh

Magic state distillation is a widely considered primitive in fault-tolerant quantum computation for the preparation of high-fidelity non-Clifford resources. The most commonly considered class of such protocols are generalised triorthogonal codes; these distil $n$ noisy input $\mathrm{T}$ states into purified third-level diagonal magic states. Extensive prior work has searched this space of protocols, often using heuristic methods that do not guarantee optimality. Existing classification work is limited to protocols distilling $k$ output $\mathrm{T}$ states with $n+k\leq 38$ (Nezami and Haah, Phys. Rev. A 106, 012437 (2022)). In this work, we significantly expand this classification to all protocols with lengths $n\leq 54$. We restrict to distance $d\geq 3$ to keep the classification to a sensible size, and because efficient searches are well understood at distance $2$ (Singh et al., arXiv:2606.28518). Moreover, our results are complementary to synthillation (Campbell and Howard, Phys. Rev. A 95, 022316 (2017)), which can distil third-level states from $\mathrm{T}$ states, but only at distance $2$. Under optimality in terms of input count, space footprint, and distance for a given output, we find $74$ optimal generalised triorthogonal protocols in our range, $65$ of which are new to the literature. To achieve our classification, we extend the classification of unital triorthogonal spaces of Nezami and Haah from length $38$ to $54$ using a directional derivative method. Using these as the stabiliser spaces, we add logical rows that satisfy the triorthogonality constraints to create full protocols.

quant-pharXiv:2609.30860•Sep 28, 2026•0 citations

Cyclic triorthogonal codes in prime dimension

Shiroman Prakash

We study cyclic triorthogonal codes in prime dimension $p$, on which a transversal third-level diagonal gate acts as a logical non-Clifford gate. For odd $p$, we use a definition of triorthogonality that does not require self-orthogonality. For cyclic codes of length coprime to $p$, triorthogonality reduces to a sumset condition on the spectral support, which makes exhaustive search feasible: for two natural constructions, we enumerate all maximal codes of this kind for $p=3$ up to length $121$ and $p=5,7$ up to length $96$. For qubits, we prove that a cyclic code of odd length is triply even if and only if it is classically triorthogonal, giving a complete description of triply-even cyclic codes, and we determine all such codes up to length $763$. For qudits, we find codes such as $[[19,1,3]]_3$ and $[[7,1,3]]_7$, which improve on the shortest Reed-Muller and Reed-Solomon codes in both overhead exponent and distillation threshold. The latter is the first member of an infinite family of $[[p,1,2\lfloor p/6\rfloor+1]]_p$ codes.

quant-pharXiv:2610.08012•Oct 7, 2026•0 citations

On Constructing and Decoding Quantum Triorthogonal Codes

Alessio Baldelli, Olai Å. Mostad, Hsuan-Yin Lin +2 more

Triorthogonal codes are a basic ingredient in magic-state distillation, as they enable transversal implementation of logical $\mathsf{T}$ gates. As a non-Clifford operation, the $\mathsf{T}$ gate enables universal fault-tolerant quantum computation when combined with Clifford operations. We derive an existence criterion for even-weight triorthogonal generator matrices with a target dual minimum distance. The criterion combines triorthogonality constraints with MacWilliams identities via Krawtchouk-polynomial conditions on the dual weight distribution, yielding an integer linear programming formulation for the construction problem. We find novel nontrivial triorthogonal codes (degenerate and non-degenerate) that are not necessarily constructed from triply even binary linear codes. By imposing automorphism-group constraints, the formulation also recovers the known [[49,1,5]] and [[95,1,7]] triorthogonal codes. We also evaluate the performance of the obtained high-distance triorthogonal codes over the dephasing channel using different decoding methods, showing that automorphism ensemble decoding (AED) and guessing random additive-noise decoding (GRAND) are promising options.

quant-pharXiv:2605.24519•May 26, 2026•0 citations

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

Jeongwan Haah, Matthew B. Hastings

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.

arXiv:1709.02832•Quantum•Jun 7, 2018•78 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•0 citations

Short qudit triorthogonal codes from doubling

Shiroman Prakash, K. L. Ramya

We construct short triorthogonal codes for qudits of odd prime dimension by generalizing doubling, which combines a triorthogonal code with a code admitting a transversal phase gate, and raises the distance by up to two. This gives codes with parameters $[[28,1,4]]_3$, $[[37,1,5]]_3$, $[[72,1,6]]_3$, $[[118,1,8]]_3$, $[[33,1,5]]_5$ and $[[20,1,4]]_7$, each shorter than the cyclic, concatenated and Reed-Muller codes of the same distance, and a doubling construction of the $[[15,1,3]]_3$ code. When the columns of a generator matrix are regarded as charged points, triorthogonality becomes the vanishing of multipole moments up to octupole order, and doubling becomes a double layer of opposite charges; this picture explains why inputs with nontrivial coefficients can give shorter codes. We also show by exhaustive search that the shortest codes of distance three have length $11$ for $p=5$ and length $7$ for $p=7$. Combined with high-rate distance-two codes, the new codes reduce the cost of qutrit magic state distillation by up to an order of magnitude in regimes with high input noise.

quant-pharXiv:2610.29457•Oct 22, 2026•0 citations
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≤38n+k\ensuremath{\le}38n+k\ensuremath≤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≤38n+k\ensuremath{\le}38n+k\ensuremath≤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.
Magic state distillation is a widely considered primitive in fault-tolerant quantum computation for the preparation of high-fidelity non-Clifford resources. The most commonly considered class of such protocols are generalised triorthogonal codes; these distil nnn noisy input T\mathrm{T}T states into purified third-level diagonal magic states. Extensive prior work has searched this space of protocols, often using heuristic methods that do not guarantee optimality. Existing classification work is limited to protocols distilling kkk output T\mathrm{T}T states with n+k≤38n+k\leq 38n+k≤38 (Nezami and Haah, Phys. Rev. A 106, 012437 (2022)). In this work, we significantly expand this classification to all protocols with lengths n≤54n\leq 54n≤54. We restrict to distance d≥3d\geq 3d≥3 to keep the classification to a sensible size, and because efficient searches are well understood at distance 222 (Singh et al., arXiv:2606.28518). Moreover, our results are complementary to synthillation (Campbell and Howard, Phys. Rev. A 95, 022316 (2017)), which can distil third-level states from T\mathrm{T}T states, but only at distance 222. Under optimality in terms of input count, space footprint, and distance for a given output, we find 747474 optimal generalised triorthogonal protocols in our range, 656565 of which are new to the literature. To achieve our classification, we extend the classification of unital triorthogonal spaces of Nezami and Haah from length 383838 to 545454 using a directional derivative method. Using these as the stabiliser spaces, we add logical rows that satisfy the triorthogonality constraints to create full protocols.
We study cyclic triorthogonal codes in prime dimension ppp, on which a transversal third-level diagonal gate acts as a logical non-Clifford gate. For odd ppp, we use a definition of triorthogonality that does not require self-orthogonality. For cyclic codes of length coprime to ppp, triorthogonality reduces to a sumset condition on the spectral support, which makes exhaustive search feasible: for two natural constructions, we enumerate all maximal codes of this kind for p=3p=3p=3 up to length 121121121 and p=5,7p=5,7p=5,7 up to length 969696. For qubits, we prove that a cyclic code of odd length is triply even if and only if it is classically triorthogonal, giving a complete description of triply-even cyclic codes, and we determine all such codes up to length 763763763. For qudits, we find codes such as [[19,1,3]]3[[19,1,3]]_3[[19,1,3]]3​ and [[7,1,3]]7[[7,1,3]]_7[[7,1,3]]7​, which improve on the shortest Reed-Muller and Reed-Solomon codes in both overhead exponent and distillation threshold. The latter is the first member of an infinite family of [[p,1,2⌊p/6⌋+1]]p[[p,1,2\lfloor p/6\rfloor+1]]_p[[p,1,2⌊p/6⌋+1]]p​ codes.
Triorthogonal codes are a basic ingredient in magic-state distillation, as they enable transversal implementation of logical T\mathsf{T}T gates. As a non-Clifford operation, the T\mathsf{T}T gate enables universal fault-tolerant quantum computation when combined with Clifford operations. We derive an existence criterion for even-weight triorthogonal generator matrices with a target dual minimum distance. The criterion combines triorthogonality constraints with MacWilliams identities via Krawtchouk-polynomial conditions on the dual weight distribution, yielding an integer linear programming formulation for the construction problem. We find novel nontrivial triorthogonal codes (degenerate and non-degenerate) that are not necessarily constructed from triply even binary linear codes. By imposing automorphism-group constraints, the formulation also recovers the known [[49,1,5]] and [[95,1,7]] triorthogonal codes. We also evaluate the performance of the obtained high-distance triorthogonal codes over the dephasing channel using different decoding methods, showing that automorphism ensemble decoding (AED) and guessing random additive-noise decoding (GRAND) are promising options.
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.
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.
We construct short triorthogonal codes for qudits of odd prime dimension by generalizing doubling, which combines a triorthogonal code with a code admitting a transversal phase gate, and raises the distance by up to two. This gives codes with parameters [[28,1,4]]3[[28,1,4]]_3[[28,1,4]]3​, [[37,1,5]]3[[37,1,5]]_3[[37,1,5]]3​, [[72,1,6]]3[[72,1,6]]_3[[72,1,6]]3​, [[118,1,8]]3[[118,1,8]]_3[[118,1,8]]3​, [[33,1,5]]5[[33,1,5]]_5[[33,1,5]]5​ and [[20,1,4]]7[[20,1,4]]_7[[20,1,4]]7​, each shorter than the cyclic, concatenated and Reed-Muller codes of the same distance, and a doubling construction of the [[15,1,3]]3[[15,1,3]]_3[[15,1,3]]3​ code. When the columns of a generator matrix are regarded as charged points, triorthogonality becomes the vanishing of multipole moments up to octupole order, and doubling becomes a double layer of opposite charges; this picture explains why inputs with nontrivial coefficients can give shorter codes. We also show by exhaustive search that the shortest codes of distance three have length 111111 for p=5p=5p=5 and length 777 for p=7p=7p=7. Combined with high-rate distance-two codes, the new codes reduce the cost of qutrit magic state distillation by up to an order of magnitude in regimes with high input noise.