arXiv:2610.00525
Good Quantum Locally Testable Codes from Lossless Cubical Complexes
Itay Cohen, Itai Leigh, Assaf Reiner, Amnon Ta-Shma, Elad Tzalik
Abstract
Sipser and Spielman constructed LDPC codes from either bipartite \emph{spectral} expanders or one-sided \emph{lossless} expanders. In higher dimensions, \emph{spectral} expansion similarly played a central role in the constructions of asymptotically good classical LTCs and qLDPC codes by Dinur, Evra, Livne, Lubotzky, and Mozes and by Panteleev and Kalachev. Alternatively, Lin and Hsieh constructed classical LTCs and qLDPC codes from two-dimensional \emph{lossless} cubical complexes. In this work we develop the higher-dimensional \emph{lossless} approach. We do not construct the required high-dimensional lossless cubical complexes; rather, we investigate what their existence would imply. We associate with a high-dimensional cubical complex a \emph{level chain complex}, whose chain groups are supported on the level sets of the Boolean cube rather than on its cells. Our main technical contribution is a clean local-to-global theorem for this structure: suitable one-dimensional lossless expansion in the directional graphs implies small-set coboundary expansion of the global level complex. As a consequence, sufficiently imbalanced, two-sided lossless four-dimensional cubical complexes give rise to asymptotically good quantum locally testable codes. We expect the local-to-global principle developed here to have further applications.
AI Summary
The paper studies whether one-dimensional lossless expansion can supply the higher-dimensional homological expansion needed for asymptotically good quantum locally testable codes (qLTCs), without auxiliary local codes. Its coding result is conditional: the required cubical complexes are not constructed, and their existence is unknown even non-explicitly. The framework uses a cube-decorated graph with vertex blocks $V_I$, indexed by $I\subseteq[k]$, and unique square completion. Its “level complex” places cochains on $V_r=\bigsqcup_{|I|=r}V_I$, rather than on cubical cells; adjacency defines coboundary maps satisfying $\delta^2=0$. Under directional lossless expansion and degree/loss imbalance conditions, every sufficiently small locally minimal level-$r$ cochain satisfies $\|\delta f\|\geq(m_{k,r-1}-O_k(\varepsilon_\star^{1/2^r}))\|f\|$, where $\varepsilon_\star=\sum_i\varepsilon_i$ and $m_{k,r-1}>0$ depends only on dimension and level. The proof decomposes a cochain into pieces supported in upward links using recursively defined heavy vertices. Lossless expansion and imbalance control overlaps and cancellations; link expansion follows by comparison with complete multipartite simplicial complexes. In dimension four, applying expansion in both orientations yields CSS codes on $V_2$ with constant rate, relative distance, check weight, and testability soundness. Degree ratios $\mu_1,\mu_2\geq4$ and $\mu_3,\mu_4\leq1/4$ guarantee rate greater than $0.1$. A greedy decoder corrects a constant fraction of errors in linear time, with degree-dependent constants. The paper distinguishes this conditional route from a concurrent unconditional good-qLTC construction and reports that a natural arithmetic candidate fails two-sided losslessness.
We used ChatGPT 5.4-6 and Codex to assist with drafting and editing the manuscript, refining the exposition, and checking mathematical calculations.
Error found: The standalone link-expansion theorem omits the neighborhood-size hypothesis required to invoke directional losslessness, and is false when the stipulated lossless-expansion ranges contain no nonempty sets.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 44 pages, 5 figures; cleaned up misplaced editorial comments