Explicit Abelian Lifts and Quantum LDPC Codes

Fernando Granha Jeronimo, Tushant Mittal, Ryan O'Donnell, Pedro Paredes, Madhur Tulsiani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


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 ℓ ≤ 2 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.

Original languageEnglish (US)
Title of host publication13th Innovations in Theoretical Computer Science Conference, ITCS 2022
EditorsMark Braverman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772174
StatePublished - Jan 1 2022
Externally publishedYes
Event13th Innovations in Theoretical Computer Science Conference, ITCS 2022 - Berkeley, United States
Duration: Jan 31 2022Feb 3 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference13th Innovations in Theoretical Computer Science Conference, ITCS 2022
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software


  • Expander graphs
  • Graph lifts
  • Quantum LDPC codes
  • Quasi-cyclic LDPC codes


Dive into the research topics of 'Explicit Abelian Lifts and Quantum LDPC Codes'. Together they form a unique fingerprint.

Cite this