Quantum Reed-Muller code[1,2] 

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}\) [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].

Parents

Children

  • \([[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\).

Cousins

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. 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
[14]
Z.-W. Liu and S. Zhou, “Quantum error correction meets continuous symmetries: fundamental trade-offs and case studies”, (2023) arXiv:2111.06360
[15]
S. Nezami and J. Haah, “Classification of small triorthogonal codes”, Physical Review A 106, (2022) arXiv:2107.09684 DOI
[16]
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
BibTeX:
@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:
https://errorcorrectionzoo.org/c/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

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