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. 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 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].

Decoding

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

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 \(q\)-ary 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; see Ref. [5] for connection between the 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
[5]: Anthony Leverrier and Gilles Zémor, “Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes”. 2206.07571
[6]: Anthony Leverrier and Gilles Zémor, “Decoding quantum Tanner codes”. 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 lifted-product code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/expander_lifted_product

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/quantum/qudits_galois/qldpc/expander_lifted_product.yml.