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].Gates
Expander LP codes can admit a cup product structure and can thus have logical gates in the Clifford hierarchy implemented by constant-depth Clifford circuits [6].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 [9].
- 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. [7] 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].
Primary Hierarchy
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]
- N. P. Breuckmann, M. Davydova, J. N. Eberhardt, and N. Tantivasadakarn, “Cups and Gates I: Cohomology invariants and logical quantum operations”, (2024) arXiv:2410.16250
- [7]
- 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
- [8]
- A. Leverrier and G. Zémor, “Decoding quantum Tanner codes”, (2022) arXiv:2208.05537
- [9]
- 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