Expander lifted-product code

Expander lifted-product code[1]

Description

Family of \(G\)-lifted product codes constructed using two random classical Tanner codes defined on expander graphs. For certain parameters, this construction yields the first asymptotically good QLDPC codes [1].

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 nonabelian 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)]]\) [2]; this construction can be derandomized by being reformulated as a balanced product code [3].

Rate

Expander lifted-product codes include the first examples [1] of (asymptotically) good QLDPC codes, i.e., codes with asymptotically constant rate and linear distance. The existence of such codes proves the QLDPC conjecture [4]. Another notable family encodes \(k \in \Theta(n^\alpha \log n)\) logical qubits with distance \(d \in \Omega(n^{1 - \alpha} / \log n)\) for any number of physical qubits \(n\) and any real parameter \(0 \leq \alpha < 1\) [2].

Notes

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

Parent

Lifted-product (LP) code — Lifted products of certain classical Tanner codes are the first asymptotically good QLDPC codes.

Cousins

Tanner code — Expander lifted-product codes are products of Tanner codes defined on expander graphs.
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.

References

[1]: Pavel Panteleev and Gleb Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes”. 2111.03654
[2]: P. Panteleev and G. Kalachev, “Quantum LDPC Codes With Almost Linear Minimum Distance”, IEEE Transactions on Information Theory 68, 213 (2022). DOI; 2012.04068
[3]: N. P. Breuckmann and J. N. Eberhardt, “Balanced Product Quantum Codes”, IEEE Transactions on Information Theory 67, 6653 (2021). DOI; 2012.09271
[4]: N. P. Breuckmann and J. N. Eberhardt, “Quantum Low-Density Parity-Check Codes”, PRX Quantum 2, (2021). DOI; 2103.06309

Cite as:

“Expander lifted-product 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/tree/main/codes/quantum/properties/qldpc/expander_lifted_product.yml.