Triorthogonal code[1]
Description
Qubit CSS code whose \(X\)-type logicals and stabilizer generators form a triorthogonal matrix (defined below) in the symplectic representation.
An \(m \times n\) binary matrix is triorthogonal if its rows \(r_1, \ldots, r_m\) satisfy \(|r_i \cdot r_j| = 0\) and \(|r_i \cdot r_j \cdot r_k| = 0\) with binary addition and multiplication. The triorthogonal CSS code associated with the matrix is constructed by mapping nonzero entries in even-weight rows to \(X\) operators, and \(Z\) operators for each row in the orthogonal complement.
See [2; Appx. D][3; Sec. 2.3] for generalized versions of triorthogonality.
Protection
Weight \(t\) Pauli errors, where \(t\) depends on the family. For example, Ref. [1] provides a family of distance \(2\) codes.Encoding
Encoder for magic states for the code constructed in [1].Transversal Gates
Transversal action of \(T\) gates on all qubits, followed by a particular pattern of \(CZ\) and \(S\) gates, will realize a logical \(T\) gate [1; Lemma 2]. When an additional condition on logical-\(X\) operators is satisfied, the \(CZ\) and \(S\) gates are no longer necessary [4; Thm. 14].Triorthogonality is necessary but not sufficient for physical transversal \(T\) gates on each qubit to realize the identity logical gate [4; Thm. 12].Certain codes realize controlled-controlled-\(Z\) gates [5], realized via physical \(CCZ\) gates on three code blocks.Fault Tolerance
Universal fault-tolerant gates can be performed without magic-state distillation [5,6].Notes
Reference [7] presents a classification of triorthogonal codes up to \(n + k \leq 38\) by associating each triorthogonal code with a Reed-Muller polynomial.Cousins
- Quantum Reed-Muller code— Classification of triorthogonal codes yields a connection to Reed-Muller polynomials [7].
- Self-dual linear code— Self-dual binary codes can be used to construct triorthogonal codes [8].
- CSS-T code— Triorthogonal and CSS-T codes overlap, but neither is a subset of the other [9]. CSS-T codes reduce to triorthogonal codes when the logical action of the physical transversal \(T\) gate is a logical \(T\) gate on all encoded qubits. Triorthogonality is necessary for physical transversal \(T\) gates on each qubit to realize the identity logical gate [4; Thm. 12]. The \(X\)-type stabilizer generator matrix for a CSS-T code is always triorthogonal [10; Corr. 5].
- Binary dihedral PI code— There exist binary dihedral PI codes that have distance 5 (7, 9, 11, 13) and encode in 27 (49, 73, 107, 147) qubits, all realizing transversal \(T\) gates.
- Generalized quantum divisible code— Triorthogonal codes are stabilizer codes, while generalized quantum divisible codes are CSS codes. Every level-three generalized divisible code is a triorthogonal code, but whether the converse is true or false is not known [11; Sec. VI.C].
- Quantum rainbow code— Hypergraph products of color codes yield quantum rainbow codes with growing distance and transversal gates in the Clifford hierarchy. In particular, utilizing this construction for quasi-hyperbolic color codes [12] yields an \([[n,O(n),O(\log n)]]\) triorthogonal code family with magic-state yield parameter \(\gamma\to 0\) [13].
- \([[23, 1, 7]]\) Quantum Golay code— A \([[95,1,7]]\) triorthogonal code with a transversal \(T\) gate can be obtained from the qubit Golay code via the doubling transformation [14].
- Quantum quadratic-residue (QR) code— Qubit quantum QR codes are doubly even and admit transversal implementations of the single-qubit Clifford group [9]. They yield a family of high-distance triorthogonal and weak triply even codes via the doubling transformation [9]; such codes admit transversal implementations of the \(T\) gate.
- Quantum AG code— By defining a generalization of triorthogonal matrices to Galois qudits of dimension \(q=2^m\), one can construct an asymptotically good family of quantum AG codes that admits a diagonal transversal gate at the third level of the Clifford hierarchy and attains a zero magic-state yield parameter, \(\gamma = 0\) [15]. This code can be treated as a qubit code by decomposing each Galois qudit into a Kronecker product of \(m\) qubits; see [16,18–20][17; Sec. 5.3]. Two other such asymptotically good families exist [19,20], admitting a different diagonal gate at the third level of the Clifford hierarchy.
Primary Hierarchy
Parents
\(k\)-orthogonal codes reduce to triorthogonal codes for \(k=3\).
Prime-qudit triorthogonal codes reduce to triorthogonal codes when \(p=2\).
Triorthogonal code
Children
The \([[15, 1, 3]]\) code is a triorthogonal code [7].
References
- [1]
- S. Bravyi and J. Haah, “Magic-state distillation with low overhead”, Physical Review A 86, (2012) arXiv:1209.2426 DOI
- [2]
- E. T. Campbell and M. Howard, “Unified framework for magic state distillation and multiqubit gate synthesis with reduced resource cost”, Physical Review A 95, (2017) arXiv:1606.01904 DOI
- [3]
- J. Haah and M. B. Hastings, “Codes and Protocols for DistillingT, controlled-S, and Toffoli Gates”, Quantum 2, 71 (2018) arXiv:1709.02832 DOI
- [4]
- N. Rengaswamy, R. Calderbank, M. Newman, and H. D. Pfister, “On Optimality of CSS Codes for Transversal T”, IEEE Journal on Selected Areas in Information Theory 1, 499 (2020) arXiv:1910.09333 DOI
- [5]
- A. Paetznick and B. W. Reichardt, “Universal Fault-Tolerant Quantum Computation with Only Transversal Gates and Error Correction”, Physical Review Letters 111, (2013) arXiv:1304.3709 DOI
- [6]
- D. Banfield, H. Leitch, and A. Kay, “Implementing Clifford Gates on Stabilizer Codes via Measurement”, (2025) arXiv:2210.14074
- [7]
- S. Nezami and J. Haah, “Classification of small triorthogonal codes”, Physical Review A 106, (2022) arXiv:2107.09684 DOI
- [8]
- M. Shi, H. Lu, J.-L. Kim, and P. Sole, “Triorthogonal Codes and Self-dual Codes”, (2024) arXiv:2408.09685
- [9]
- S. P. Jain and V. V. Albert, “Transversal Clifford and T-gate codes of short length and high distance”, (2025) arXiv:2408.12752
- [10]
- E. Camps-Moreno, H. H. López, G. L. Matthews, D. Ruano, R. San-José, and I. Soprunov, “An algebraic characterization of binary CSS-T codes and cyclic CSS-T codes for quantum fault tolerance”, Quantum Information Processing 23, (2024) arXiv:2312.17518 DOI
- [11]
- J. Haah, “Towers of generalized divisible quantum codes”, Physical Review A 97, (2018) arXiv:1709.08658 DOI
- [12]
- G. Zhu, S. Sikander, E. Portnoy, A. W. Cross, and B. J. Brown, “Non-Clifford and parallelizable fault-tolerant logical gates on constant and almost-constant rate homological quantum LDPC codes via higher symmetries”, (2024) arXiv:2310.16982
- [13]
- T. R. Scruby, A. Pesah, and M. Webster, “Quantum Rainbow Codes”, (2024) arXiv:2408.13130
- [14]
- M. Sullivan, “Code conversion with the quantum Golay code for a universal transversal gate set”, Physical Review A 109, (2024) arXiv:2307.14425 DOI
- [15]
- A. Wills, M.-H. Hsieh, and H. Yamasaki, “Constant-Overhead Magic State Distillation”, (2024) arXiv:2408.07764
- [16]
- A. Ashikhmin and E. Knill, “Nonbinary quantum stabilizer codes”, IEEE Transactions on Information Theory 47, 3065 (2001) DOI
- [17]
- A. Niehage, “Quantum Goppa Codes over Hyperelliptic Curves”, (2005) arXiv:quant-ph/0501074
- [18]
- D. Gottesman. Surviving as a quantum computer in a classical world (2024) URL
- [19]
- Q. T. Nguyen, “Good binary quantum codes with transversal CCZ gate”, (2024) arXiv:2408.10140
- [20]
- L. Golowich and V. Guruswami, “Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates”, (2024) arXiv:2408.09254
Page edit log
- Victor V. Albert (2024-07-29) — most recent
- Shubham P. Jain (2024-07-29)
- Narayanan Rengaswamy (2024-07-29)
- Victor V. Albert (2021-12-16)
- Benjamin Quiring (2021-12-16)
Cite as:
“Triorthogonal code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/quantum_triorthogonal