Ramanujan-complex product code[1]
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. 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 \(\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 [1].
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 [2].
Parent
- Generalized homological product CSS code — Ramanujan codes result from a tensor product of a classical-code and a quantum-code chain complex.
Child
Cousins
- Distance-balanced code — Ramanujan tensor-product constructions use distance balancing to increase distance.
- Freedman-Meyer-Luo code — Ramanujan codes broke 20-year record on minimum code distance set by Freedman-Meyer-Luo codes.
References
- [1]
- 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
- [2]
- 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:
“Ramanujan-complex product code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/ramanujan_tensor_product