High-dimensional expander (HDX) code[1,2] 

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 \(\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

Child

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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: ramanujan_tensor_product

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
BibTeX:
@incollection{eczoo_ramanujan_tensor_product, title={High-dimensional expander (HDX) code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/ramanujan_tensor_product} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/ramanujan_tensor_product

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/stabilizer/qldpc/homological/ramanujan_tensor_product.yml.