Expander LP code[1]
Description
Family of \(G\)-lifted product codes constructed using two classical expander codes, equivalently two regular Tanner codes defined on the same expander graph [2]. For certain parameters, this construction yields the first asymptotically good QLDPC codes. Classical codes resulting from the same lifted-product complexes are one of the first two families of \(c^3\)-LTCs [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 two Tanner codes on that graph, in which parity-check supports are defined by the graph and the local constraints are specified by two short classical codes (chosen randomly in the original proof). Fourth, take the \(G\)-lifted product of those two Tanner codes.
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]. For cyclic Abelian groups \(G=\mathbb{Z}_{\ell}\) with \(\ell=\Theta(n/\log n)\), quasi-cyclic expander LP codes yield families with parameters \([[n,k=\Theta(\log n),d=\Theta(n/\log n)]]\) [3].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. For cyclic Abelian groups \(G=\mathbb{Z}_{\ell}\) with \(\ell=\Theta(n/\log n)\), quasi-cyclic expander LP codes yield families with parameters \([[n,k=\Theta(\log n),d=\Theta(n/\log n)]]\) [3]. Related balanced-product reformulations and other explicit Abelian LP constructions appear in [4,5].Gates
Certain qubit 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].
- Expander code— Expander LP codes are lifted products of expander codes with different local codes [1].
- 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— For cyclic groups \(G=\mathbb{Z}_{\ell}\) with \(\ell=\Theta(n/\log n)\), quasi-cyclic expander LP codes yield families with parameters \([[n,k=\Theta(\log n),d=\Theta(n/\log n)]]\) [3]. Related balanced-product reformulations and other explicit Abelian LP constructions appear in [4,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”, (2025) 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