Galois-qudit RS code

Galois-qudit RS code [1]

Alternative Names: Galois-qudit polynomial code (QPyC).

Description

A Galois-qudit CSS code family (with $n\leq q$) constructed using two RS codes over $\mathbb{F}_q$.

Let $C_1$ be a $[n,k_1,d_1]_q$ RS code and $C_2^\perp$ be a $[n,k_1-k_2,d_2]_q$ RS code, modified such that $C_2^\perp \subseteq C_1$ and $0\le k_2 \le k_1 \le n$. Then, a Galois-qudit RS code is a pure $[[n,k_2,d]]_q$ Galois-qudit CSS code with $d=\min(n-k_1+1,k_1-k_2+1)$. The code is the span of the basis codewords over $\mathbb{F}_q$, \begin{align} |\overline{\beta_0,\cdots,\beta_{k_2-1}}\rangle = \sum_{(\beta_{k_2},\cdots,\beta_{k_1-1})\in \mathbb{F}_q^{k_1-k_2}} \bigotimes_{i=1}^{n} \left| \sum_{j=0}^{k_1-1} \beta_j \alpha_i^j \right\rangle,\tag*{$(1)$} \end{align}where $(\alpha_1, \cdots, \alpha_n)$ are $n$ distinct points chosen for code $C_1$ from $\mathbb{F}_q\setminus \{0\}$, so that $n<q$ [2].

Logical states can instead be labeled by the $k_2$ highest-degree coefficients, with the superposition running over the $k_1-k_2$ lowest-degree ones. Inverting the evaluation points and applying single-Galois-qudit multiplication gates maps the code above onto a code of this form with the same parameters. This second form also allows zero as an evaluation point, so that $n\leq q$. The case $n=q$, for which the evaluation points exhaust $\mathbb{F}_q$, is constructed from extended GRS codes.

Protection

Galois-qudit RS codes can be adapted for insertion and deletion noise [3].

Magic

Punctured RS codes can be used for magic-state distillation with a spacetime overhead of $(\log \frac{1}{\epsilon})^{\gamma}$, with the magic-state scaling exponent $\gamma \to 0$ with decreasing $\epsilon$ [4].

Transversal and Permutation-Based Gates

There exists an order $[[n,\Theta(n),\Theta(n)]]_{n^2}$ punctured RS code family that admits (weakly) transversal $CCZ_{n^2}$ gates for any three logical qudits [5]. This code can be treated as a qubit code by decomposing each Galois qudit into a Kronecker product of several qubits; see [2,6,8–10][7; Sec. 5.3]. This yields a qubit code family that is asymptotically good up to poly-logarithmic factors [5].Galois-qudit RS codes can be concatenated with quantum multiplication-friendly codes to yield CSS codes over a constant prime-power alphabet $q$ admitting a transversal $CCZ_q$ gate (and, for $q \geq 5$, also a transversal $U_q$ gate) with nearly linear code dimension and distance, $k,d = \Omega(n/2^{O(\log^* n)})$, where $\log^* n$ is the iterated logarithm (the number of times $\log$ must be applied to $n$ before the result is $\leq 1$) [9].

Fault Tolerance

The original prime-field construction admits a fault-tolerant universal gate set beyond the standard transversal gates for qudit CSS codes [1]. Generalized NOT, SUM, SWAP, scalar multiplication, and phase gates are implemented transversally. A logical Fourier transform is implemented by weighted physical Fourier transforms followed by code switching: a length-$m$ degree-$d$ code is mapped to the corresponding Fourier-dual code of degree $m-d-1$. A transversal product gate $|a\rangle|b\rangle|c\rangle \mapsto |a\rangle|b\rangle|c+ab\rangle$ maps into a degree-$2d$ code, after which degree reduction switches back to the original degree.Aharonov and Ben-Or performed the code switching needed for their Fourier and product gates using concatenation and degree reduction [1]. The same switching between Galois-qudit RS codes of different degree can also be implemented by teleportation using encoded Bell states. This uses the transversal SUM gate between the two codes, with the lower-degree code serving as the control.Magic-state distillation with punctured Galois-qudit RS codes, combined with constant-rate QLTCs, yields fault-tolerant quantum computation with constant space overhead and time overhead that is logarithmic up to subpolylogarithmic factors [4], improving over previous schemes [11,12]. Recursively applying one fixed distillation circuit, based on a punctured $[[3q/4,q/4,\lfloor q/12\rfloor+1]]_q$ Galois-qudit RS code with $q=2^\ell$ [13; Lemma 7.1], removes the subpolylogarithmic factor [13; Thm. 7.8].

Cousins

Folded quantum RS (FQRS) code— A FQRS code with no extra grouping ($m=1$) reduces to a Galois-qudit RS code that is CSS.
Reed-Solomon (RS) code— Galois-qudit RS codes are CSS codes constructed from RS codes.
Extended GRS code— Galois-qudit RS codes of length $n=q$, whose evaluation points exhaust $\mathbb{F}_q$, are constructed from extended GRS codes.
Quantum maximum-distance-separable (MDS) code— A Galois-qudit RS code is a quantum MDS code when $n-k_1=k_1-k_2$.
Concatenated quantum code— Recursive concatenations of Galois-qudit RS codes can be asymptotically good [14].
Asymmetric quantum code (AQC)— Asymmetric Galois-qudit RS codes have been constructed [15,17][16; Sec. 17.3].
Perfect-tensor code— AME states for even $n$ are examples of quantum MDS codes with no logical qubits [18–20]. MDS RS codes can yield perfect tensors via the CSS and Hermitian constructions [21] (see also Refs. [22,23]).
Quantum tensor-product code— Product codes constructed from a self-orthogonal and an arbitrary RS code yield an RS code [24].
Approximate secret-sharing code— Polynomial codes can be used for a specific construction of this code.

Member of code lists

Primary Hierarchy

Quantum Domain

Galois-qudit Kingdom

Galois-qudit codeQECC Quantum

Galois-qudit USt code

Galois-qudit stabilizer codeStabilizer Hamiltonian-based QECC Quantum

True Galois-qudit stabilizer code

Quantum AG code

Galois-qudit GRS code

Parents

Galois-qudit GRS code

Galois-qudit quantum RM codeStabilizer Hamiltonian-based QECC Quantum

Galois-qudit RS codes are the Galois-qudit RM codes from the CSS construction with $m=1$ whose two GRM codes are punctured to the same $n$ evaluation points. For $m=1$, GRM codes are extended RS codes [25]. Every Galois-qudit RS code takes this form when its logical states are labeled by the highest-degree coefficients, possibly after inverting the evaluation points and applying single-Galois-qudit multiplication gates.

Galois-qudit RS code

Children

Prime-qudit RS code

Galois-qudit RS codes for prime-dimensional qudits are prime-qudit RS codes.

$[[3,1,2]]_4$ three-Galois-quartrit code

The $[[3,1,2]]_4$ code is constructed from the shortened RS$_4$ code [26].

References

[1]
D. Aharonov and M. Ben-Or, “Fault-Tolerant Quantum Computation With Constant Error Rate”, (1999) arXiv:quant-ph/9906129
[2]
D. Gottesman, Surviving as a Quantum Computer in a Classical World (2024) URL
[3]
M. Hagiwara, “Quantum Deletion Codes Derived From Quantum Reed-Solomon Codes”, (2023) arXiv:2306.13399
[4]
Q. T. Nguyen and C. A. Pattison, “Quantum fault tolerance with constant-space and logarithmic-time overheads”, (2025) arXiv:2411.03632
[5]
Z. He, V. Vaikuntanathan, A. Wills, and R. Y. Zhang, “Quantum Codes with Addressable and Transversal Non-Clifford Gates”, (2025) arXiv:2502.01864
[6]
A. Ashikhmin and E. Knill, “Nonbinary quantum stabilizer codes”, IEEE Transactions on Information Theory 47, 3065 (2001) DOI
[7]
A. Niehage, “Quantum Goppa Codes over Hyperelliptic Curves”, (2005) arXiv:quant-ph/0501074
[8]
Q. T. Nguyen, “Good binary quantum codes with transversal CCZ gate”, (2024) arXiv:2408.10140
[9]
L. Golowich and V. Guruswami, “Asymptotically Good Quantum Codes with Transversal Non-Clifford Gates”, (2024) arXiv:2408.09254
[10]
M. Heinrich, “On stabiliser techniques and their application to simulation and certification of quantum devices”, PhD thesis, Universität zu Köln, 2021.
[11]
H. Yamasaki and M. Koashi, “Time-Efficient Constant-Space-Overhead Fault-Tolerant Quantum Computation”, Nature Physics 20, 247 (2024) arXiv:2207.08826 DOI
[12]
S. Yoshida, S. Tamiya, and H. Yamasaki, “Concatenate codes, save qubits”, npj Quantum Information 11, (2025) arXiv:2402.09606 DOI
[13]
Z. Han and Z.-W. Liu, “Purely-logarithmic-time- and constant-space-overhead fault-tolerant quantum computation”, (2026) arXiv:2609.28461
[14]
Z. Li, L.-J. Xing, and X.-M. Wang, “A family of asymptotically good quantum codes based on code concatenation”, (2008) arXiv:0901.0042
[15]
G. G. La Guardia, R. Palazzo, and C. Lavor, “Nonbinary quantum Reed-Solomon codes”, International Journal of Pure and Applied Mathematics 65(1), 55-63 (2010)
[16]
S. A. Aly, “On Quantum and Classical Error Control Codes: Constructions and Applications”, (2008) arXiv:0812.5104
[17]
G. G. La Guardia, “Asymmetric quantum Reed-Solomon and generalized Reed-Solomon codes”, Quantum Information Processing 11, 591 (2011) DOI
[18]
A. J. Scott, “Multipartite entanglement, quantum-error-correcting codes, and entangling power of quantum evolutions”, Physical Review A 69, (2004) arXiv:quant-ph/0310137 DOI
[19]
Z. Raissi, C. Gogolin, A. Riera, and A. Acín, “Optimal quantum error correcting codes from absolutely maximally entangled states”, Journal of Physics A: Mathematical and Theoretical 51, 075301 (2018) arXiv:1701.03359 DOI
[20]
D. Alsina and M. Razavi, “Absolutely maximally entangled states, quantum-maximum-distance-separable codes, and quantum repeaters”, Physical Review A 103, (2021) arXiv:1907.11253 DOI
[21]
M. GRASSL, T. BETH, and M. RÖTTELER, “ON OPTIMAL QUANTUM CODES”, International Journal of Quantum Information 02, 55 (2004) arXiv:quant-ph/0312164 DOI
[22]
M. Marcolli, “Holographic Codes on Bruhat–Tits buildings and Drinfeld Symmetric Spaces”, (2018) arXiv:1801.09623
[23]
M. Heydeman, M. Marcolli, S. Parikh, and I. Saberi, “Nonarchimedean Holographic Entropy from Networks of Perfect Tensors”, (2018) arXiv:1812.04057
[24]
M. Grassl and M. Rotteler, “Quantum block and convolutional codes from self-orthogonal product codes”, Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. 1018 (2005) arXiv:quant-ph/0703181 DOI
[25]
P. K. Sarvepalli and A. Klappenecker, “Nonbinary Quantum Reed-Muller Codes”, (2005) arXiv:quant-ph/0502001
[26]
J. M. Koh, A. Gong, A. C. Diaconu, D. B. Tan, A. A. Geim, M. J. Gullans, N. Y. Yao, M. D. Lukin, and S. Majidy, “Entangling logical qubits without physical operations”, (2026) arXiv:2601.20927

Page edit log

Victor V. Albert (2026-11-06) — most recent
Victor V. Albert (2026-09-23)
Victor V. Albert (2026-09-22)
Victor V. Albert (2026-06-08)
Victor V. Albert (2022-01-10)
Qingfeng (Kee) Wang (2021-12-20)

Cite as:

“Galois-qudit RS code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/galois_polynomial, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qudits_galois/stabilizer/evaluation/rs/galois_polynomial.yml.