TY - GEN
T1 - Explicit Abelian Lifts and Quantum LDPC Codes
AU - Jeronimo, Fernando Granha
AU - Mittal, Tushant
AU - O'Donnell, Ryan
AU - Paredes, Pedro
AU - Tulsiani, Madhur
N1 - Funding Information:
Tushant Mittal: Supported in part by NSF grant CCF-1816372. Ryan O’Donnell: Supported by NSF grant FET-1909310. Pedro Paredes: Supported by NSF grant FET-1909310. Madhur Tulsiani: Supported by NSF grant CCF-1816372.
Funding Information:
Funding This material is based upon work supported by the National Science Foundation under grant numbers listed below. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author and do not necessarily reflect the views of the National Science Foundation (NSF). Fernando Granha Jeronimo: Supported by Grant No. CCF-1900460 and also supported in part by NSF grant CCF-1816372.
Publisher Copyright:
© Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, and Madhur Tulsiani; licensed under Creative Commons License CC-BY 4.0
PY - 2022/1/1
Y1 - 2022/1/1
N2 - For an abelian group H acting on the set [ℓ], an (H, ℓ)-lift of a graph G0 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 (Equation presented), 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 G0 with the following parameters: (i) (Equation presented), for any lift size ℓ ≤ 2nδ where δ = δ(d, ϵ), (ii) (Equation presented), for any lift size ℓ ≤ 2nδ0 for a fixed δ0 > 0, when d ≥ d0(ϵ), or (iii) (Equation presented), 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.
AB - For an abelian group H acting on the set [ℓ], an (H, ℓ)-lift of a graph G0 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 (Equation presented), 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 G0 with the following parameters: (i) (Equation presented), for any lift size ℓ ≤ 2nδ where δ = δ(d, ϵ), (ii) (Equation presented), for any lift size ℓ ≤ 2nδ0 for a fixed δ0 > 0, when d ≥ d0(ϵ), or (iii) (Equation presented), 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.
KW - Expander graphs
KW - Graph lifts
KW - Quantum LDPC codes
KW - Quasi-cyclic LDPC codes
UR - http://www.scopus.com/inward/record.url?scp=85124008307&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85124008307&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2022.88
DO - 10.4230/LIPIcs.ITCS.2022.88
M3 - Conference contribution
AN - SCOPUS:85124008307
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 13th Innovations in Theoretical Computer Science Conference, ITCS 2022
A2 - Braverman, Mark
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 13th Innovations in Theoretical Computer Science Conference, ITCS 2022
Y2 - 31 January 2022 through 3 February 2022
ER -