Description
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 [3,4]. 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 )\).
Rate
For 2D Ramanujan complexes, the rate is of order \(\Omega(\sqrt{ \frac{1}{n \log n} })\), with minimum distance \(d = \Omega(\sqrt{n \log n}) \). For 3D, the rate is \( \Omega(\frac{1}{\sqrt{n}\log n}) \) with minimum distance \(d \geq \sqrt{n} \log n \).
Decoding
For 2D simplicial complexes, cycle code decoder admitting a polynomial-time decoding algorithm can be used [2].
Notes
Codes were first to break a 20-year record set by the Freedman-Meyer-Luo code for the lower bound on scaling of the minimum distance [5].
Parent
- Tensor-product HDX code — Ramanujan codes result from a tensor product of a classical-code and a quantum-code chain complex.
Cousins
- Distance-balanced code — Ramanujan tensor-product constructions use distance balancing to increase distance.
- Hypergraph product (HGP) code — Ramanujan codes utilize the hypergraph product with a twist, which is an automorphism on one of the complexes in the tensor product, in order to increase distance [5].
- Freedman-Meyer-Luo code — Ramanujan codes broke 20-year record on minimum code distance set by Freedman-Meyer-Luo codes.
References
- [1]
- T. Kaufman, D. Kazhdan, and A. Lubotzky, “Isoperimetric Inequalities for Ramanujan Complexes and Topological Expanders”, (2014) arXiv:1409.1397
- [2]
- S. Evra, T. Kaufman, and G. Zémor, “Decodable quantum LDPC codes beyond the \(\sqrt{n}\) distance barrier using high dimensional expanders”, (2020) arXiv:2004.07935
- [3]
- A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
- [4]
- G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI
- [5]
- N. P. Breuckmann and J. N. Eberhardt, “Quantum Low-Density Parity-Check Codes”, PRX Quantum 2, (2021) arXiv:2103.06309 DOI
Page edit log
- Victor V. Albert (2022-01-03) — most recent
- Xiaozhen Fu (2021-12-12)
Cite as:
“High-dimensional expander (HDX) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ramanujan_tensor_product