Finite-Degree Quantum LDPC Codes Reaching the Gilbert-Varshamov Bound

Abstract

We construct asymptotically good nested Calderbank-Shor-Steane (CSS) code pairs from Hsu-Anastasopoulos codes and MacKay-Neal codes. For fixed balanced triples with even component degrees and $j_Z\ge4$, we prove that the coding rate stays bounded away from zero and that the relative distances on both sides stay bounded away from zero with probability tending to one as the blocklength grows. Moreover, within an explicit low-degree search window, we prove that all 56 balanced triples in that window with even common row degree, column degree at least four, and positive design quantum rate attain the classical Gilbert-Varshamov (GV) bound on both constituent sides, and consequently the CSS GV bound at fixed finite degree.

The paper asks whether fixed, small-degree sparse-graph constructions can yield positive-rate CSS codes reaching the CSS Gilbert–Varshamov (GV) distance benchmark. It constructs nested pairs from punctured Hsu–Anastasopoulos- and MacKay–Neal-type codes, using independent sparse matrices $A_Z,A_\Delta,B$ and the stack $A_X=[A_Z;A_\Delta]$. In the homogeneous balanced regime, $j_X+j_Z=k$ and $j_\Delta=k-2j_Z$. For fixed even component degrees with $4\le j_Z<k/2$, both constituent classical codes—and consequently both CSS logical distances—have linear distance with high probability. Actual rates converge in probability to their design values, with quantum rate $R_Q\to1-2j_Z/k$. Stronger distance guarantees cover all 56 triples satisfying even $10\le k\le30$, $4\le j_Z\le10$, and $j_Z<k/2$, including 24 odd-$j_Z$ cases: for every fixed $\delta<\mathrm h^{-1}(j_Z/k)$, both logical distances exceed $\delta n$ with probability tending to one. This reaches the CSS GV benchmark at the limiting rate, without identifying the exact asymptotic distance. The proofs use exact configuration-model weight enumerators, pairing bounds for small supports, and entropy/convexity reductions for linear weights, supplemented by exact-rational scalar certification. The stacked MN ensemble is analyzed directly. Guarantees are probabilistic rather than deterministic code-selection algorithms. Crucially, bounded degree applies to extended graphs with hidden variables; the visible stabilizer-check matrices are generally dense, so standard quantum-LDPC sparsity is not established. No efficient decoder or large-girth theorem is provided, and GV attainment outside the certified window remains conjectural.