Expander LP code[1] 

Description

Family of \(G\)-lifted product codes constructed using two random classical Tanner codes defined on expander graphs [2]. For certain parameters, this construction yields the first asymptotically good QLDPC codes. Classical codes resulting from this construction are one of the first two families of \(c^3\)-LTCs.

An expander lifted-product code family is constructed as follows. First, take the Cayley graph of a finite group \(G\). Second, take the double cover of the graph, resulting in a graph that satisfies the requirements of participating in a \(G\)-lifted product (i.e., the resulting graph is a free \({\mathbb{F}}_q G\)-module). Third, create a Tanner code out of the graph, in which parity-check supports are defined by the graph, and bitstrings satisfying a particular parity check are defined to be the codewords of a small classical code (chosen to be a random code in the construction). Fourth, take the \(G\)-lifted product of two copies of the Tanner code.

The small classical codes used in the construction of good QLDPC codes are required to have a certain product-expansion property (Lemma 10 in Ref. [1]); it is proven that random codes satisfy said property in the thermodynamic limit.

Protection

Code performance strongly depends on \(G\). Certain non-Abelian groups yield asymptotically good QLDPC codes with parameters \([[n, k = \Theta(n), d = \Theta(n)]]\) [1]. Abelian groups like \(\mathbb{Z}_{\ell}\) for \(\ell=\Theta(n / \log n)\) yield constant-rate codes with parameters \([[n, k = \Theta(n), d = \Theta(n / \log n)]]\) [3]; this construction can be derandomized by being reformulated as a balanced product code [4].

Rate

Expander lifted-product codes for non-Abelian groups include the first examples [1] of (asymptotically) good QLDPC codes, i.e., codes with asymptotically constant rate and linear distance. Expander LP codes for Abelian groups like \(\mathbb{Z}_{\ell}\) for \(\ell=\Theta(n / \log n)\) yield constant-rate codes with parameters \([[n, k = \Theta(n), d = \Theta(n / \log n)]]\) [3]; this construction can be derandomized by being reformulated as a balanced product code [4].Other explicit versions of codes with such parameters have been developed [5].

Decoding

Linear-time decoder [6].Logarithmic-time subroutine [7].

Notes

Construction outlined in talk by R. O'Donnell.Popular summary in Quanta Magazine.

Parent

Cousins

  • Good QLDPC code — Lifted products of certain classical Tanner codes are the first asymptotically good QLDPC codes.
  • \(q\)-ary linear LTC — Classical codes resulting from the expander lifted-product construction are one of the first two families of \(c^3\)-LTCs [1].
  • Tanner code — Expander lifted-product codes are products of regular \(q\)-ary Tanner codes defined on expander graphs [2].
  • Random code — Expander lifted-product codes are quantum CSS codes that utilize short classical codes in their construction which need to satisfy some properties (Ref. [1], Lemma 10). It is shown that such codes exist, but they are not explicitly constructed. Such codes can be obtained by repeated random sampling or by performing a search of all codes of desired length. Nevertheless, since the length of the desired short codes does not scale with \(n\), this construction is effectively explicit.
  • Topological code — Expander lifted-product codes are expected to realize topological quantum spin glass order [8].
  • Quantum Tanner code — Quantum Tanner codes are an attempt to construct asymptotically good QLDPC codes that are similar to but simpler than expander lifted-product codes; see Ref. [6] for connection between the codes.
  • Abelian LP code — Expander LP codes for Abelian groups like \(\mathbb{Z}_{\ell}\) for \(\ell=\Theta(n / \log n)\) yield constant-rate codes with parameters \([[n, k = \Theta(n), d = \Theta(n / \log n)]]\) [3]; this construction can be derandomized by being reformulated as a balanced product code [4]. Other explicit versions of codes with such parameters have been developed [5].

References

[1]
P. Panteleev and G. Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes”, (2022) arXiv:2111.03654
[2]
S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
[3]
P. Panteleev and G. Kalachev, “Quantum LDPC Codes With Almost Linear Minimum Distance”, IEEE Transactions on Information Theory 68, 213 (2022) arXiv:2012.04068 DOI
[4]
N. P. Breuckmann and J. N. Eberhardt, “Balanced Product Quantum Codes”, IEEE Transactions on Information Theory 67, 6653 (2021) arXiv:2012.09271 DOI
[5]
F. G. Jeronimo, T. Mittal, R. O’Donnell, P. Paredes, and M. Tulsiani, “Explicit Abelian Lifts and Quantum LDPC Codes”, (2021) arXiv:2112.01647
[6]
A. Leverrier and G. Zémor, “Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes”, (2022) arXiv:2206.07571
[7]
A. Leverrier and G. Zémor, “Decoding quantum Tanner codes”, (2022) arXiv:2208.05537
[8]
B. Placke, T. Rakovszky, N. P. Breuckmann, and V. Khemani, “Topological Quantum Spin Glass Order and its realization in qLDPC codes”, (2024) arXiv:2412.13248
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: expander_lifted_product

Cite as:
“Expander LP code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/expander_lifted_product
BibTeX:
@incollection{eczoo_expander_lifted_product, title={Expander LP code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/expander_lifted_product} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/expander_lifted_product

Cite as:

“Expander LP code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/expander_lifted_product

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qudits_galois/stabilizer/qldpc/balanced_product/lp/matrix/expander_lifted_product.yml.