ITCS'22
Joint work with Fernando G. Jeronimo, Ryan O'Donnell, Pedro Paredes, and Madhur Tulsiani.
arXiv
Video
Abstract
BibTeX
@InProceedings{JMOPT22,
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)},
year = {2022},
volume = {215},
publisher = {Schloss Dagstuhl --
Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.ITCS.2022.88},
eprint = {2112.01647}
}
For an abelian group \(H\) acting on the set \([\ell]\), an
\( (H,\ell) \)-lift of a graph \(G_0 \) is a graph obtained by replacing each
vertex by \(\ell\) 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 \(\widetilde{\Omega}(N^{3/5})\),
and in those by Panteleev and Kalachev [IEEE Trans. Inf. Theory 2021] of distance
\(\Omega(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 \leqslant \mathrm{Sym}(\ell)\), constant degree \(d \ge 3\) and
\(\epsilon > 0\), we construct explicit \(d\)-regular expander graphs \(G\)
obtained from an \((H,\ell)\)-lift of a (suitable) base \(n\)-vertex
expander \(G_0\) with the following parameters:
- (i) \(\lambda(G) \le 2\sqrt{d-1} + \epsilon\), for any lift size \(\ell \le 2^{n^{\delta}}\) where \(\delta=\delta(d,\epsilon)\),
- (ii) \(\lambda(G) \le \epsilon \cdot d\), for any lift size \(\ell \le 2^{n^{\delta_0}}\) for a fixed \(\delta_0 > 0\), when \(d \ge d_0(\epsilon)\), or
- (iii) \(\lambda(G) \le \widetilde{O}(\sqrt{d})\), for lift size ``exactly'' \(\ell = 2^{\Theta(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.