Explicit Abelian Lifts and Quantum LDPC Codes
Explicit Abelian Lifts and Quantum LDPC Codes
复制标题
DOI：
10.4230/lipics.itcs.2022.88
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
F. G. Jeronimo;Tushant Mittal;R. O'Donnell;Pedro Paredes;Madhur Tulsiani
中科院分区：
文献类型：
--
作者：
F. G. Jeronimo;Tushant Mittal;R. O'Donnell;Pedro Paredes;Madhur Tulsiani
对于作用在集合$[\ell]$上的阿贝尔群$H$，图$G_0$的$（H，\ell）$-提升是通过将每个顶点替换为$\ell$副本，将每条边替换为对应于$H$中元素作用的匹配而得到的图。在这项工作中，我们显示了以下明确的结构，通过阿贝尔升降机获得的扩张。每（传递）阿贝尔群H \leqslane\text{Sym}（\ell）$，常度d \ge 3$和d\ge 0$，我们构造了由一个（H，\ell）$-提升得到的显d$-正则扩张图G$（合适的）基$n$-顶点扩展器$G_0$，参数如下：（i）$\lambda（G）\le 2\sqrt{d-1} + \delta $，对于任何电梯尺寸$\ell \le 2^{n^{\delta}}$，其中$\delta=\delta（d，\n）$，（ii）$\lambda（G）\le\cdot d$，对于任何升力大小$\ell \le 2^{n^{\delta_0}}$对于固定的$\delta_0>0$，当$d \ge d_0 $\lambda（G）\le \widetilde{O}（\sqrt{d}）$，对于提升大小“精确”$\ell = 2^{\Theta（n）}$。作为推论，我们得到了显式量子提升产品码的Panteleev和Kalachev几乎线性距离（也在很宽的参数范围内）和显式的经典准循环LDPC码与广泛的循环大小。通过将Mohanty、奥唐纳和Paredes [STOC 2020]的2美元升举技术扩展到更大的阿贝尔升举尺寸（作为简化其构造的副产品），获得了上述项目$（i）$和$（ii）$。这是通过提供跟踪功率方法中产生的特殊行走的新编码来完成的，仔细“压缩”深度优先搜索穿越。结果$（iii）$是通过Agarwal等人的一个更简单的证明。[SIAM J.离散数学2019]以扩展中的polylog因子为代价。
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$. In this work, we show the following explicit constructions of expanders obtained via abelian lifts. For every (transitive) abelian group $H \leqslant \text{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.