Description
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].
Protection
Detects errors on \(d-1\) qubits, corrects errors on \(\left\lfloor (d-1)/2 \right\rfloor\) qubits.
Rate
\(\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].
Magic
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}\) [7–9][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].
Parents
- Quantum pin code — Quantum Reed-Muller codes are special cases of quantum pin codes [11; Sec. II.D]
- Prime-qudit RM code — Prime-qudit RM codes reduce to quantum RM codes when \(q=p=2\).
Children
- \([[2^D,D,2]]\) hypercube quantum code — \([[2^D,D,2]]\) hypercube quantum codes are special cases of the \([[2^m,{m \choose r}, 2^r]]\) quantum Reed-Muller codes for \(m=D\) and \(r=1\) [7–9][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\).
Cousins
- Reed-Muller (RM) code
- Quantum convolutional code — Quantum convolutional codes can be derived from quantum Reed-Muller codes [12].
- EA qubit stabilizer code — EA versions of quantum RM codes and their quantum tensor-product variants can be constructed [13].
- Quantum tensor-product code — EA versions of quantum RM codes and their quantum tensor-product variants can be constructed [13].
- Asymmetric quantum code — Asymmetric quantum RM codes have been constructed [14; Lemma 4.1].
- Covariant block quantum code — Quantum RM codes are approximately covariant and nearly saturate certain covariance-performance bounds [15].
- Triorthogonal code — Classification of triorthogonal codes yields a connection to Reed-Muller polynomials [16].
- Generalized homological-product qubit CSS code — Iterative tensor-product codes can be constructed out of quantum Reed-Muller codes [17].
References
- [1]
- A. Steane, “Quantum Reed-Muller Codes”, (1996) arXiv:quant-ph/9608026
- [2]
- L. Zhang and I. Fuss, “Quantum Reed-Muller Codes”, (1997) arXiv:quant-ph/9703045
- [3]
- 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
- [4]
- M. B. Hastings and J. Haah, “Distillation with Sublogarithmic Overhead”, Physical Review Letters 120, (2018) arXiv:1709.03543 DOI
- [5]
- S. Bravyi and J. Haah, “Magic-state distillation with low overhead”, Physical Review A 86, (2012) arXiv:1209.2426 DOI
- [6]
- 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
- [7]
- 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
- [8]
- E. T. Campbell and M. Howard, “Unifying Gate Synthesis and Magic State Distillation”, Physical Review Letters 118, (2017) arXiv:1606.01906 DOI
- [9]
- J. Haah and M. B. Hastings, “Codes and Protocols for DistillingT, controlled-S, and Toffoli Gates”, Quantum 2, 71 (2018) arXiv:1709.02832 DOI
- [10]
- 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
- [11]
- C. Vuillot and N. P. Breuckmann, “Quantum Pin Codes”, IEEE Transactions on Information Theory 68, 5955 (2022) arXiv:1906.11394 DOI
- [12]
- 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
- [13]
- P. J. Nadkarni et al., “Entanglement-assisted Quantum Reed-Muller Tensor Product Codes”, Quantum 8, 1329 (2024) arXiv:2303.08294 DOI
- [14]
- 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
- [15]
- Z.-W. Liu and S. Zhou, “Quantum error correction meets continuous symmetries: fundamental trade-offs and case studies”, (2023) arXiv:2111.06360
- [16]
- S. Nezami and J. Haah, “Classification of small triorthogonal codes”, Physical Review A 106, (2022) arXiv:2107.09684 DOI
- [17]
- B. Audoux and A. Couvreur, “On tensor products of CSS Codes”, (2018) arXiv:1512.07081
Page edit log
- Victor V. Albert (2024-03-14) — most recent
- Benjamin Quiring (2021-12-16)
- Victor V. Albert (2021-12-03)
Cite as:
“Quantum Reed-Muller code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/quantum_reed_muller