Quantum Reed-Muller code[1,2] 


A CSS code formed from a classical Reed-Muller (RM) code or its punctured/shortened versions. Such codes often admit transversal logical gates in the Clifford hierarchy.

Ordinary, punctured, or shortened RM codes can be used to construct quantum Reed-Muller codes. For example, the original construction [1] uses a general RM\((r,m)\) code for the \(X\)-type stabilizers, and an RM\((r-1,m)\) code for the \(Z\)-type stabilizers.

Non-CSS codes can be derived from such codes by modifying the \(X\)-type stabilizers [1].


Detects errors on \(d-1\) qubits, corrects errors on \(\left\lfloor (d-1)/2 \right\rfloor\) qubits.


\(\frac{k}{n}\), where \(k = 2^r - {r \choose t} + 2 \sum_{i=0}^{t-1} {r \choose i}\). Additionally, CSS codes formed from binary Reed-Muller codes achieve channel capacity on erasure channels [3].


The family constructed out of shortened RM codes with parameters \([[\sum_{i=w+1}^m \binom{m}{i}, \sum_{i=0}^{w} \binom{m}{i}, \sum_{i=w+1}^{r+1} \binom{r+1}{i}]]\) for integers \(m > 2r\) and \(r > w \geq 0\) yields protocols with an exponent of \(\gamma < 0.678\), with the fewest resource protocol with \(\gamma < 1\) requiring a code with parameters \(\{r,w,m\} = \{19,14,3r+1\}\) such that \(n \approx 2^{58}\) qubits [4; Corr. 1]. This refutes a conjecture that no protocol could achieve \(\gamma < 1\) [5].

Transversal Gates

The \([[2^m,{m \choose r}, 2^{\min(r,m-r)}]]\) family, where \(r\) divides \(m\), admits diagonal gates in the form of \(Z\)-rotations by angle \(\pi/2^{m/r}\) [79][6; Exam. 8 and Thm. 19].The family constructed out of shortened RM codes with parameters \([[\sum_{i=w+1}^m \binom{m}{i}, \sum_{i=0}^{w} \binom{m}{i}, \sum_{i=w+1}^{r+1} \binom{r+1}{i}]]\) for integers \(m > 2r\) and \(r > w \geq 0\) admits a transversal gate at the \(\nu\)th level in the hierarchy whenever \(m > \nu r\) [4; Thm. 1].

Fault Tolerance

Gate switching protocol for universal computation [10].



  • \([[2^D,D,2]]\) hypercube code — \([[2^D,D,2]]\) hypercube codes are special cases of the \([[2^m,{m \choose r}, 2^r]]\) quantum Reed-Muller codes for \(m=D\) and \(r=1\) [79][6; Exam. 8].
  • \([[2^r-1,1,3]]\) simplex code — \([[2^r-1,1,3]]\) simplex codes are special cases of the \([[\sum_{i=w+1}^m \binom{m}{i}, \sum_{i=0}^{w} \binom{m}{i}, \sum_{i=w+1}^{r+1} \binom{r+1}{i}]]\) quantum RM codes for \(w=r=0\) and \(m=r-1\) [4; Thm. 1].
  • \([[2^r-1, 2^r-2r-1, 3]]\) quantum Hamming code — \([[2^r-1, 2^r-2r-1, 3]]\) quantum Hamming codes are quantum Reed-Muller codes because Hamming and simplex codes are both punctured RM codes.
  • \([[2^{2r-1}-1,1,2^r-1]]\) quantum punctured Reed-Muller code — The \([[2^{2r-1}-1,1,2^r-1]]\) quantum punctured Reed-Muller codes are special cases of the \([[\sum_{i=w+1}^m \binom{m}{i}, \sum_{i=0}^{w} \binom{m}{i}, \sum_{i=w+1}^{r+1} \binom{r+1}{i}]]\) family for \(m \to 2r-1\), \(w \to 0\), and \(r \to r-1\).



A. Steane, “Quantum Reed-Muller Codes”, (1996) arXiv:quant-ph/9608026
L. Zhang and I. Fuss, “Quantum Reed-Muller Codes”, (1997) arXiv:quant-ph/9703045
S. Kumar, R. Calderbank, and H. D. Pfister, “Reed-muller codes achieve capacity on the quantum erasure channel”, 2016 IEEE International Symposium on Information Theory (ISIT) (2016) DOI
M. B. Hastings and J. Haah, “Distillation with Sublogarithmic Overhead”, Physical Review Letters 120, (2018) arXiv:1709.03543 DOI
S. Bravyi and J. Haah, “Magic-state distillation with low overhead”, Physical Review A 86, (2012) arXiv:1209.2426 DOI
N. Rengaswamy et al., “On Optimality of CSS Codes for Transversal T”, IEEE Journal on Selected Areas in Information Theory 1, 499 (2020) arXiv:1910.09333 DOI
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
E. T. Campbell and M. Howard, “Unifying Gate Synthesis and Magic State Distillation”, Physical Review Letters 118, (2017) arXiv:1606.01906 DOI
J. Haah and M. B. Hastings, “Codes and Protocols for DistillingT, controlled-S, and Toffoli Gates”, Quantum 2, 71 (2018) arXiv:1709.02832 DOI
J. T. Anderson, G. Duclos-Cianci, and D. Poulin, “Fault-Tolerant Conversion between the Steane and Reed-Muller Quantum Codes”, Physical Review Letters 113, (2014) arXiv:1403.2734 DOI
C. Vuillot and N. P. Breuckmann, “Quantum Pin Codes”, IEEE Transactions on Information Theory 68, 5955 (2022) arXiv:1906.11394 DOI
S. A. Aly, A. Klappenecker, and P. K. Sarvepalli, “Quantum Convolutional Codes Derived From Reed-Solomon and Reed-Muller Codes”, (2007) arXiv:quant-ph/0701037
P. K. Sarvepalli, A. Klappenecker, and M. Rötteler, “Asymmetric quantum codes: constructions, bounds and performance”, Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 465, 1645 (2009) DOI
Z.-W. Liu and S. Zhou, “Quantum error correction meets continuous symmetries: fundamental trade-offs and case studies”, (2023) arXiv:2111.06360
S. Nezami and J. Haah, “Classification of small triorthogonal codes”, Physical Review A 106, (2022) arXiv:2107.09684 DOI
B. Audoux and A. Couvreur, “On tensor products of CSS Codes”, (2018) arXiv:1512.07081
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: quantum_reed_muller

Cite as:
“Quantum Reed-Muller code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/quantum_reed_muller
@incollection{eczoo_quantum_reed_muller, title={Quantum Reed-Muller code}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/quantum_reed_muller} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

“Quantum Reed-Muller code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/quantum_reed_muller

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/stabilizer/rm/quantum_reed_muller.yml.