Expander LP code

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

Lifted-product (LP) code

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.
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.
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 et al., “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

Page edit log

Victor V. Albert (2022-04-26) — most recent
Victor V. Albert (2022-01-19)
Pavel Panteleev (2021-11-30)

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/lp/matrix/expander_lifted_product.yml.