Welcome to the Galois-qudit Kingdom.

Also called a $$GF(q)$$- or $$\mathbb{F}_q$$-qudit code. Encodes $$K$$-dimensional Hilbert space into a $$q^n$$-dimensional ($$n$$-qudit) Hilbert space, with canonical qudit states $$|k\rangle$$ labeled by elements $$k$$ of the Galois field $$GF(q)$$ and with $$q$$ being a power of a prime $$p$$. A Galois field can be thought of as a vector space whose basis vectors are the $$m$$ roots of some polynomial and whose coefficients (i.e., field) are $$p$$th roots of unity. Codes can be denoted as $$((n,K))_{GF(q)}$$ or $$((n,K,d))_{GF(q)}$$, whenever the code's distance $$d$$ is defined. This notation differentiates between Galois-qudit and modular-qudit codes, although the same notation, $$((n,K,d))_q$$, is usually used for both. Protection: A convenient and often considered error set is the Galois-qudit analogue of the Pauli string set for qubit codes. For a single Galois qudit, this set consists of products of $$X$$-type and $$Z$$-type operators labeled by elements $$\beta \in GF(q)$$, which act on computational basis states $$|\gamma\rangle$$ for $$\gamma\in GF(q)$$ as \begin{align} X_{\beta}\left|\gamma\right\rangle =\left|\gamma+\beta\right\rangle \,\,\text{ and }\,\,Z_{\beta}\left|\gamma\right\rangle =e^{i\frac{2\pi}{p}\text{tr}(\beta\gamma)}\left|\gamma\right\rangle~, \end{align} where the trace maps elements of the field to elements of $$\mathbb{Z}_p$$ as \begin{align} \text{tr}(\gamma)=\sum_{k=0}^{m-1}\gamma^{p^{k}}~. \end{align} For multiple Galois qudits, error set elements are tensor products of elements of the single-qudit error set. Parent of: Galois-qudit non-stabilizer code. Cousins: Modular-qudit code.
An $$((n,K,d))_{GF(q)}$$ Galois-qudit code whose logical subspace is the joint eigenspace of commuting Galois-qudit Pauli operators forming the code's stabilizer group $$\mathsf{S}$$. Traditionally, the logical subspace is the joint $$+1$$ eigenspace, and the stabilizer group does not contain $$e^{i \phi} I$$ for any $$\phi \neq 0$$. The distance $$d$$ is the minimum weight of a Galois-qudit Pauli string that implements a nontrivial logical operation in the code. Protection: Detects errors on up to $$d-1$$ qudits, and corrects erasure errors on up to $$d-1$$ qudits. Corrects errors on $$\left\lfloor (d-1)/2 \right\rfloor$$ qudits. Parent of: True Galois-qudit stabilizer code.
Approximate quantum code of rate $$R$$ that can tolerate adversarial errors nearly saturating the quantum Singleton bound of $$(1-R)/2$$. The formulation of such codes relies on a notion of quantum list decoding. Sampling a description of this code can be done with an efficient randomized algorithm with $$2^{-\Omega(n)}$$ failure probability. Protection: For any $$\gamma>0$$ and rate $$0<R<1$$, these approximate quantum $$[[n,R \cdot n]]_{GF(q)}$$ codes have constant Galois-qudit dimension $$q=q(\gamma)$$ and correct errors acting on $$(1-R-\gamma) \cdot n/2$$ registers, up to a recovery error of $$2^{-\Omega(n)}$$.
The projection onto a stabilizer code is proportional to an equal sum over all elements of the stabilizer group $$\mathsf{S}$$. Non-stabilizer codes generalize stabilizer codes by modifying the code projection with elements of a subset $$\mathsf{B}\subset\mathsf{S}$$ called the Fourier description (see proof of Thm. 2.7 in Ref. [5]). When $$\mathsf{B}$$ is a subgroup of $$\mathsf{S}$$, then the code reduces to an ordinary stabilizer code. Parents: Galois-qudit code. Parent of: Galois-qudit stabilizer code.
Also called a linear stabilizer code. A $$[[n,k,d]]_{GF(q)}$$ stabilizer code whose stabilizer's symplectic representation forms a linear subspace. In other words, the set of $$q$$-ary vectors representing the stabilizer group is closed under both addition and multiplication by elements of $$GF(q)$$. In contrast, Galois-qudit stabilizer codes admit sets of vectors that are closed under addition only. Protection: Detects errors on up to $$d-1$$ qudits, and corrects erasure errors on up to $$d-1$$ qudits. Parents: Galois-qudit stabilizer code.
Abelian topological code, such as a surface [7][9] or color [8] code, constructed on lattices of Galois qudits. Parents: Galois-qudit CSS code, Topological code. Cousins: Kitaev surface code, Color code.
Stub.
True Galois-qudit stabilizer code constructed from BCH codes via either the Hermitian construction or the Galois-qudit CSS construction. Parents: True Galois-qudit stabilizer code.
An $$[[n,k,d]]_{GF(q)}$$ Galois-qudit true stabilizer code admitting a set of stabilizer generators that are either $$Z$$-type or $$X$$-type Galois-qudit Pauli strings. The stabilizer generator matrix, taking values from $$GF(q)$$, is of the form \begin{align} H=\begin{pmatrix}0 & H_{Z}\\ H_{X} & 0 \end{pmatrix} \label{eq:parityg} \end{align} such that the rows of the two blocks must be orthogonal \begin{align} H_X H_Z^T=0~. \label{eq:commG} \end{align} The above condition guarantees that the $$X$$-stabilizer generators, defined in the symplectic representation as rows of $$H_X$$, commute with the $$Z$$-stabilizer generators associated with $$H_Z$$. Protection: Detects errors on $$d-1$$ qubits, corrects errors on $$\left\lfloor (d-1)/2 \right\rfloor$$ qubits. Parents: True Galois-qudit stabilizer code. Cousin of: Galois-qudit BCH code.
True $$q$$-Galois-qudit stabilizer code constructed from generalized Reed-Solomon (GRS) codes via either the Hermitian construction [24][25][26] or the Galois-qudit CSS construction [23][27]. Parents: True Galois-qudit stabilizer code. Parent of: Galois-qudit RS code.
An $$[[n,k,d]]_{GF(q)}$$ Galois-qudit stabilizer code constructed from a classical code over $$GF(q^2)$$ using the one-to-one correspondence between the Galois-qudit Pauli matrices and elements of the Galois field $$GF(q^2)$$. Parents: True Galois-qudit stabilizer code.
Generalized homological product CSS code Qubit, modular-qudit, or Galois-qudit generalized homological product code of CSS type.
Also called a checkerboard code. CSS variant of the surface code defined on a square lattice that has been rotated 45 degrees such that qubits are on vertices, and both $$X$$- and $$Z$$-type check operators occupy plaquettes in an alternating checkerboard pattern. Protection: The $$[[L^2,1,L]]$$ variant of this family includes the $$[[9,1,3]]$$ surface-17 code, named as such because 8 ancilla qubits are used for check operator measurements alongside the 9 physical qubits. Parent of: Surface-17 code.
A family of $$[[n,k,d]]_{GF(q)}$$ CSS codes approximately correcting errors on up to $$\lfloor (n-1)/2 \rfloor$$ qubits, i.e., with approximate distance approaching the no-cloning bound $$n/2$$. Constructed using a non-degenerate CSS code, such as a polynomial quantum code, and a classical authentication scheme. The code can be viewed as an $$t$$-error tolerant secret sharing scheme. Since the code yields a small logical subspace using large registers that contain both classical and quantum information, it is not useful for practical error correction problems, but instead demonstrates the power of approximate quantum error correction. Protection: Corrects up to $$\lfloor (n-1)/2 \rfloor$$ errors with fidelity exponentially lose to 1. Parents: Galois-qudit CSS code.
Also known as a quantum AG code. Binary quantum Goppa codes are a family of $$[[n,k,d]]_{GF(q)}$$ CSS codes for $$q=2^m$$, generated using classical Goppa codes. Protection: Protects against weight $$t$$ errors where $$0 < t \leq \lfloor \frac{d^*-g-1}{2} \rfloor$$ where $$d^* = \text{deg} G + 2 -2g$$ and $$g$$ is the genus of the function field and $$d \geq n - \lfloor \frac{deg G}{2} \rfloor$$. Parents: Galois-qudit CSS code. Cousins: Classical Goppa code.
CSS code on $$q^m$$-dimensional Galois-qudits that is constructed from folded Reed-Solomon (FRS) codes via the Galois-qudit CSS construction. This code is used to construct Singleton-bound approaching approximate quantum codes. Parents: Galois-qudit CSS code. Parent of: Galois-qudit RS code. Cousins: Folded RS (FRS) code. Cousin of: Singleton-bound approaching AQECC.
Also called a Panteleev-Kalachev (PK) code. Code that utilizes the notion of a lifted product in its construction. Lifted products of certain classical Tanner codes are the first (asymptotically) good QLDPC codes. Protection: Code performance strongly depends on the group $$G$$ used in the product [37]. Cousins: Kitaev surface code, Haah cubic code.
Stub. Parents: Galois-qudit CSS code. Cousins: Skew-cyclic code.
Also called a polynomial code (QPyC). An $$[[n,k,n-k+1]]_{GF(q)}$$ (with $$q>n$$) Galois-qudit CSS code constructed using two Reed-Solomon codes over $$GF(q)$$. Cousin of: Approximate secret-sharing code.
Family of CSS quantum codes based on products of two classical codes which share common symmetries. The balanced product can be understood as taking the usual tensor/hypergraph product and then factoring out the symmetries factored. This reduces the overall number of physical qubits $$n$$, while, under certain circumstances, leaving the number of encoded qubits $$k$$ and the code distance $$d$$ invariant. This leads to a more favourable encoding rate $$k/n$$ and normalized distance $$d/n$$ compared to the tensor/hypergraph product. Protection: Taking balanced products of two classical LDPC codes which have a symmetry group which grows linearly in their block lengths were known to give QLDPC codes with a linear rate and which were conjectured to have linear distance [39]. This conjecture was proved in Ref. [36]. Cousin of: Left-right Cayley complex code.
Stub. Protection: Minimum distance bound obtained using robustness of dual tensor-product codes [41]. Parent of: Rotated surface code.
CSS code constructed from a Ramanujan quantum code and an asymptotically good classical LDPC code using distance balancing. Ramanujan quantum codes are defined using Ramanujan complexes which are simplicial complexes that generalise Ramanujan graphs. Combining the quantum code obtained from a Ramanujan complex and a good classical LDPC code, which can be thought of as coming from a 1-dimensional chain complex, yields a new quantum code that is defined on a 2-dimensional chain complex. This 2-dimensional chain complex is obtained by the co-complex of the product of the 2 co-complexes. The length, dimension and distance of the new quantum code depend on the input codes. Protection: Without distance balancing, a Ramanujan code can have $$d_X =\Omega(\log n)$$ and $$d_Z = \Omega (n)$$. For 2D Ramanujan complexes, distance-balanced codes protect against errors with minimum distance $$d = \Omega(\sqrt{n \log n})$$. For 3D Ramanujan complexes, distance-balanced codes protect against errors with minimum distance $$d= \Omega(\sqrt{n} \log n )$$. Parent of: Tensored-Ramanujan-complex product code.
A $$[[9,1,3]]$$ rotated surface code named for the sum of its 9 data qubits and 8 syndrome qubits. It uses the smallest number of qubits to perform error correction on a surface code with parallel syndrome extraction. Protection: Independent correction of single-qubit $$X$$ and $$Z$$ errors. Correction for some two-qubit $$X$$ and $$Z$$ errors. Parents: Rotated surface code.
Stub. Parents: Balanced product code.
Also called a twisted product code. CSS code constructed by combining a random LDPC code as the base and a cyclic repetition code as the fiber of a fiber bundle. After applying distance balancing, a QLDPC code with distance $$\Omega(n^{3/5}\text{polylog}(n))$$ and rate $$\Omega(n^{-2/5}\text{polylog}(n))$$ is obtained. Parents: Balanced product code. Parent of: Homological product code.
A family of $$[[n,k,d]]$$ CSS codes whose construction is based on two binary linear seed codes $$C_1$$ and $$C_2$$. Protection: The hypergraph product has distance $$d=O(\sqrt{n})$$. The number of encoded logical qubits is $$k=O(k_1k_2)$$ where $$k_1$$ and $$k_2$$ are the dimensions of the classical seed codes $$C_1$$ and $$C_2$$. Parent of: Quantum expander code.
Family of $$G$$-lifted product codes constructed using two random classical Tanner codes defined on expander graphs. For certain parameters, this construction yields the first asymptotically good QLDPC codes. Classical codes resulting from this construction are one of the first two families of $$c^3$$-LTCs. Protection: Code performance strongly depends on $$G$$. Certain nonabelian groups yield asymptotically good QLDPC codes with parameters $$[[n, k = \Theta(n), d = \Theta(n)]]$$ [36]. Abelian groups like $$\mathbb{Z}_{\ell}$$ for $$\ell=\Theta(n / \log n)$$ yield constant-rate codes with parameters $$[[n, k = \Theta(n), d = \Theta(n / \log n)]]$$ [37]; this construction can be derandomized by being reformulated as a balanced product code [39]. Parents: Lifted-product (LP) code. Cousin of: Quantum Tanner code.
Code constructed in a similar way as the Ramanujan-complex product code, but utilizing tensor products of Ramanujan complexes in order to improve code distance from $$\sqrt{n}\log n$$ to $$\sqrt{n}~\text{polylog}(n)$$. The utility of such tensor products comes from the fact that one of the Ramanujan complexes is a collective cosystolic expander as opposed to just a cosystolic expander. Protection: Construction yields explicit QLDPC codes with distance $$\sqrt{n}\log^c n$$ using the $$c$$-tensor-product of Ramanujan complexes. Parents: Ramanujan-complex product code.
CSS code formulated using the homological product of two chain complexes (see CSS-to-homology correspondence). Stub. Protection: Given two codes $$[[n_a, k_a, d_a, w_a]]$$ for $$a\in\{1,2\}$$, where $$w_a$$ denotes the maximum hamming weight of all rows and columns of $$\partial_a$$, the homological product code has parameter $$[[n=n_1 n_2, k=k_1 k_2, d\leq d_1 d_2, w\leq w_1+w_2]]$$. From this formula, and the fact that a randomly selected boundary operator $$\partial$$ yields a CSS code that is good with high probability, we see that the product code has $$k=\Theta(n)$$ and $$w=O(\sqrt{n})$$ with high probability. The main result in [48] is to show that the product code actually has linear distance with high probability as well. To sum up, it is shown that we have a family of $$[[n,k=c_1 n, d=c_2 n, w=c_3 \sqrt{n}]]$$ codes given small enough $$c_1,c_2,c_3$$. Parents: Fiber-bundle code. Parent of: Distance-balanced code, Hypergraph product code. Cousins: Random quantum code.
CSS codes constructed from a hypergraph product of bipartite expander graphs with bounded left and right vertex degrees. For every bipartite graph there is an associated matrix (the parity check matrix) with columns indexed by the left vertices, rows indexed by the right vertices, and 1 entries whenever a left and right vertex are connected. This matrix can serve as the parity check matrix of a classical code. Two bipartite expander graphs can be used to construct a quantum CSS code (the quantum expander code) by using the parity check matrix of one as $$X$$ checks, and the parity check matrix of the other as $$Z$$ checks. Protection: Pauli errors of weight $$\leq t$$, distance scales as $$\Omega(n^{1/2})$$. Parents: Hypergraph product code. Cousins: Expander code.
CSS code constructed from a CSS code and a classical code using a distance-balancing procedure based on a generalized homological product. The initial code is said to be unbalanced, i.e., tailored to noise biased toward either bit- or phase-flip errors, and the procedure can result in a code that is treats both types of errors on a more equal footing. The original distance-balancing procedure [50], later generalized in Ref. [42], can yield QLDPC codes; see Thm. 1 in Ref. [50]. Parents: Homological product code. Cousins: Subsystem qubit stabilizer code.

## References

[1]
J. Bierbrauer and Y. Edel, “Quantum twisted codes”, Journal of Combinatorial Designs 8, 174 (2000). DOI
[2]
Avanti Ketkar et al., “Nonbinary stabilizer codes over finite fields”. quant-ph/0508070
[3]
A. Ashikhmin and E. Knill, “Nonbinary quantum stabilizer codes”, IEEE Transactions on Information Theory 47, 3065 (2001). DOI
[4]
Thiago Bergamaschi, Louis Golowich, and Sam Gunn, “Approaching the Quantum Singleton Bound with Approximate Error Correction”. 2212.09935
[5]
V. Arvind, Piyush P Kurur, and K. R. Parthasarathy, “Nonstabilizer Quantum Codes from Abelian Subgroups of the Error Group”. quant-ph/0210097
[6]
D. Gottesman. Surviving as a quantum computer in a classical world
[7]
S. S. Bullock and G. K. Brennen, “Qudit surface codes and gauge theory with finite cyclic groups”, Journal of Physics A: Mathematical and Theoretical 40, 3481 (2007). DOI; quant-ph/0609070
[8]
P. Sarvepalli, “Topological color codes over higher alphabet”, 2010 IEEE Information Theory Workshop (2010). DOI
[9]
Iryna Andriyanova, Denise Maurice, and Jean-Pierre Tillich, “New constructions of CSS codes obtained by moving to higher alphabets”. 1202.3338
[10]
Andrew Cross et al., “Quantum Locally Testable Code with Exotic Parameters”. 2209.11405
[11]
Salah Aly, Andreas Klappenecker, and Pradeep Kiran Sarvepalli, “Primitive Quantum BCH Codes over Finite Fields”. quant-ph/0501126
[12]
Salah A. Aly, Andreas Klappenecker, and Pradeep Kiran Sarvepalli, “On Quantum and Classical BCH Codes”. quant-ph/0604102
[13]
S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, “On Quantum and Classical BCH Codes”, IEEE Transactions on Information Theory 53, 1183 (2007). DOI
[14]
R. Li et al., “Hermitian dual containing BCH codes and Construction of new quantum codes”, Quantum Information and Computation 13, 21 (2013). DOI
[15]
G. G. La Guardia, “Constructions of new families of nonbinary quantum codes”, Physical Review A 80, (2009). DOI
[16]
X. Zhao et al., “Hermitian dual-containing constacyclic BCH codes and related quantum codes of length $\frac{q^{2m}-1}{q+1}$”. 2007.13309
[17]
A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist”, Physical Review A 54, 1098 (1996). DOI; quant-ph/9512032
[18]
A. M. Steane, “Error Correcting Codes in Quantum Theory”, Physical Review Letters 77, 793 (1996). DOI
[19]
“Multiple-particle interference and quantum error correction”, Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences 452, 2551 (1996). DOI; quant-ph/9601029
[20]
E. Knill, “Group Representations, Error Bases and Quantum Codes”. quant-ph/9608049
[21]
M. GRASSL, T. BETH, and M. RÖTTELER, “ON OPTIMAL QUANTUM CODES”, International Journal of Quantum Information 02, 55 (2004). DOI; quant-ph/0312164
[22]
J.-L. Kim and J. Walker, “Nonbinary quantum error-correcting codes from algebraic curves”, Discrete Mathematics 308, 3115 (2008). DOI
[23]
Dorit Aharonov and Michael Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”. quant-ph/9906129
[24]
Lingfei Jin and Chaoping Xing, “A Construction of New Quantum MDS Codes”. 1311.3009
[25]
X. Liu, L. Yu, and H. Liu, “New quantum codes from Hermitian dual-containing codes”, International Journal of Quantum Information 17, 1950006 (2019). DOI
[26]
L. Jin et al., “Application of Classical Hermitian Self-Orthogonal MDS Codes to Quantum MDS Codes”, IEEE Transactions on Information Theory 56, 4735 (2010). DOI
[27]
Z. Li, L.-J. Xing, and X.-M. Wang, “Quantum generalized Reed-Solomon codes: Unified framework for quantum maximum-distance-separable codes”, Physical Review A 77, (2008). DOI; 0812.4514
[28]
H. Bombin and M. A. Martin-Delgado, “Optimal resources for topological two-dimensional stabilizer codes: Comparative study”, Physical Review A 76, (2007). DOI; quant-ph/0703272
[29]
Jonas T. Anderson, “Homological Stabilizer Codes”. 1107.3502
[30]
A. A. Kovalev and L. P. Pryadko, “Improved quantum hypergraph-product LDPC codes”, 2012 IEEE International Symposium on Information Theory Proceedings (2012). DOI; 1202.0928
[31]
Y. Tomita and K. M. Svore, “Low-distance surface codes under realistic quantum noise”, Physical Review A 90, (2014). DOI; 1404.3747
[32]
Claude Crepeau, Daniel Gottesman, and Adam Smith, “Approximate Quantum Error-Correcting Codes and Secret Sharing Schemes”. quant-ph/0503139
[33]
Annika Niehage, “Quantum Goppa Codes over Hyperelliptic Curves”. quant-ph/0501074
[34]
A. Niehage, “Nonbinary Quantum Goppa Codes Exceeding the Quantum Gilbert-Varshamov Bound”, Quantum Information Processing 6, 143 (2006). DOI
[35]
P. Panteleev and G. Kalachev, “Degenerate Quantum LDPC Codes With Good Finite Length Performance”, Quantum 5, 585 (2021). DOI; 1904.02703
[36]
Pavel Panteleev and Gleb Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes”. 2111.03654
[37]
P. Panteleev and G. Kalachev, “Quantum LDPC Codes With Almost Linear Minimum Distance”, IEEE Transactions on Information Theory 68, 213 (2022). DOI; 2012.04068
[38]
H. Q. Dinh et al., “A class of skew cyclic codes and application in quantum codes construction”, Discrete Mathematics 344, 112189 (2021). DOI
[39]
N. P. Breuckmann and J. N. Eberhardt, “Balanced Product Quantum Codes”, IEEE Transactions on Information Theory 67, 6653 (2021). DOI; 2012.09271
[40]
Anthony Leverrier and Gilles Zémor, “Quantum Tanner codes”. 2202.13641
[41]
Anthony Leverrier and Gilles Zémor, “Decoding quantum Tanner codes”. 2208.05537
[42]
Shai Evra, Tali Kaufman, and Gilles Zémor, “Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders”. 2004.07935
[43]
Irit Dinur et al., “Good Quantum LDPC Codes with Linear Time Decoders”. 2206.07750
[44]
Matthew B. Hastings, Jeongwan Haah, and Ryan O'Donnell, “Fiber Bundle Codes: Breaking the $N^{1/2} \operatorname{polylog}(N)$ Barrier for Quantum LDPC Codes”. 2009.03921
[45]
J.-P. Tillich and G. Zemor, “Quantum LDPC Codes With Positive Rate and Minimum Distance Proportional to the Square Root of the Blocklength”, IEEE Transactions on Information Theory 60, 1193 (2014). DOI; 0903.0566
[46]
Tali Kaufman and Ran J. Tessler, “New Cosystolic Expanders from Tensors Imply Explicit Quantum LDPC Codes with $Ω(\sqrt{n}\log^kn)$ Distance”. 2008.09495
[47]
M. H. Freedman and M. B. Hastings, “Quantum Systems on Non-$k$-Hyperfinite Complexes: A Generalization of Classical Statistical Mechanics on Expander Graphs”. 1301.1363
[48]
Sergey Bravyi and Matthew B. Hastings, “Homological Product Codes”. 1311.0885
[49]
A. Leverrier, J.-P. Tillich, and G. Zemor, “Quantum Expander Codes”, 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (2015). DOI; 1504.00822
[50]
M. B. Hastings, “Weight Reduction for Quantum Codes”. 1611.03790