High-dimensional expander (HDX) 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 [2,3]. 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 [4].

Parents

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 [4].
  • 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]
A. Lubotzky, R. Phillips, and P. Sarnak, “Ramanujan graphs”, Combinatorica 8, 261 (1988) DOI
[3]
G. Davidoff, P. Sarnak, and A. Valette, Elementary Number Theory, Group Theory and Ramanujan Graphs (Cambridge University Press, 2001) DOI
[4]
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)

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/tree/main/codes/quantum/qubits/stabilizer/qldpc/ramanujan_tensor_product.yml.