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(n^{1/2}\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

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.

Zoo code information

Internal code ID: ramanujan_tensor_product

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: ramanujan_tensor_product

Cite as:
“Ramanujan-complex product 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={Ramanujan-complex product code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/ramanujan_tensor_product} }
Permanent link:
https://errorcorrectionzoo.org/c/ramanujan_tensor_product

References

[1]
Shai Evra, Tali Kaufman, and Gilles Zémor, “Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders”. 2004.07935
[2]
N. P. Breuckmann and J. N. Eberhardt, “Quantum Low-Density Parity-Check Codes”, PRX Quantum 2, (2021). DOI; 2103.06309

Cite as:

“Ramanujan-complex product 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/properties/qldpc/ramanujan_tensor_product.yml.