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
Rate
Decoding
Notes
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
- 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