License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.88
URN: urn:nbn:de:0030-drops-156846
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15684/
Jeronimo, Fernando Granha ;
Mittal, Tushant ;
O'Donnell, Ryan ;
Paredes, Pedro ;
Tulsiani, Madhur
Explicit Abelian Lifts and Quantum LDPC Codes
Abstract
For an abelian group H acting on the set [?], an (H,?)-lift of a graph G₀ is a graph obtained by replacing each vertex by ? copies, and each edge by a matching corresponding to the action of an element of H.
Expanding graphs obtained via abelian lifts, form a key ingredient in the recent breakthrough constructions of quantum LDPC codes, (implicitly) in the fiber bundle codes by Hastings, Haah and O'Donnell [STOC 2021] achieving distance Ω̃(N^{3/5}), and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance Ω(N/log(N)). However, both these constructions are non-explicit. In particular, the latter relies on a randomized construction of expander graphs via abelian lifts by Agarwal et al. [SIAM J. Discrete Math 2019].
In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group H ⩽ Sym(?), constant degree d ≥ 3 and ε > 0, we construct explicit d-regular expander graphs G obtained from an (H,?)-lift of a (suitable) base n-vertex expander G₀ with the following parameters:
ii) λ(G) ≤ 2√{d-1} + ε, for any lift size ? ≤ 2^{n^{δ}} where δ = δ(d,ε),
iii) λ(G) ≤ ε ⋅ d, for any lift size ? ≤ 2^{n^{δ₀}} for a fixed δ₀ > 0, when d ≥ d₀(ε), or
iv) λ(G) ≤ Õ(√d), for lift size "exactly" ? = 2^{Θ(n)}. As corollaries, we obtain explicit quantum lifted product codes of Panteleev and Kalachev of almost linear distance (and also in a wide range of parameters) and explicit classical quasi-cyclic LDPC codes with wide range of circulant sizes.
Items (i) and (ii) above are obtained by extending the techniques of Mohanty, O'Donnell and Paredes [STOC 2020] for 2-lifts to much larger abelian lift sizes (as a byproduct simplifying their construction). This is done by providing a new encoding of special walks arising in the trace power method, carefully "compressing" depth-first search traversals. Result (iii) is via a simpler proof of Agarwal et al. [SIAM J. Discrete Math 2019] at the expense of polylog factors in the expansion.
BibTeX - Entry
@InProceedings{jeronimo_et_al:LIPIcs.ITCS.2022.88,
author = {Jeronimo, Fernando Granha and Mittal, Tushant and O'Donnell, Ryan and Paredes, Pedro and Tulsiani, Madhur},
title = {{Explicit Abelian Lifts and Quantum LDPC Codes}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {88:1--88:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15684},
URN = {urn:nbn:de:0030-drops-156846},
doi = {10.4230/LIPIcs.ITCS.2022.88},
annote = {Keywords: Graph lifts, expander graphs, quasi-cyclic LDPC codes, quantum LDPC codes}
}
|
Keywords: |
|
Graph lifts, expander graphs, quasi-cyclic LDPC codes, quantum LDPC codes |
|
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
25.01.2022 |
