Description
CSS code obtained by applying the generalized distance-balancing/product construction of Ref. [2] to a Ramanujan-complex quantum code and an asymptotically good classical LDPC code.
Ramanujan quantum codes are defined using LSV Ramanujan complexes, which are simplicial complexes that generalize Ramanujan graphs [3,4]. The auxiliary classical code is viewed as a 1-dimensional chain complex, and the output code is defined on the co-complex of the product of the two co-complexes. Using a 2D LSV complex yields a QLDPC family with \(K=\Omega(\sqrt{n/\log n})\) and \(D=\Omega(\sqrt{n \log n})\), while using a 3D LSV complex yields \(K=\Omega(\sqrt{n}/\log n)\) and \(D=\Omega(\sqrt{n}\log n)\).
Protection
The unbalanced component code from a 2D LSV complex can have \(d_X=\Omega(\log n)\) and \(d_Z=\Omega(n)\), while one from a 3D LSV complex can have \(d_X=\Omega(\log^2 n)\) and \(d_Z=\Omega(n)\) [2]. After distance balancing, the resulting HDX family has minimum distance \(D=\Omega(\sqrt{n \log n})\) in the 2D case and \(D=\Omega(\sqrt{n}\log n)\) in the 3D case.Rate
For 2D LSV complexes, the rate is of order \(\Omega(1/\sqrt{n \log n})\), with minimum distance \(D=\Omega(\sqrt{n \log n})\). For 3D LSV complexes, the rate is \(\Omega(1/(\sqrt{n}\log n))\), with minimum distance \(D=\Omega(\sqrt{n}\log n)\).Decoding
For HDX codes built from 2D LSV complexes, \(X\)-error decoding reduces to polynomial-time cycle-code decoding on the 1-skeleton together with decoding of the auxiliary classical LDPC code [2].For the 2D construction, \(Z\)-errors of linear weight admit a local decoder based on coboundary expansion; replacing the component complex by the 2-skeleton of a 3D LSV complex preserves 2D-type asymptotic parameters while giving linear-time \(Z\)-decoding with unit-weight local corrections [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].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.
Primary Hierarchy
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