arXiv:2610.02648
Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound
Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Mary Wootters
Abstract
We show that for any $R,ε>0$ and any prime $p\geq 2$, there exists an infinite family of $p$-ary quantum low-density parity-check (QLDPC) codes, rate $R$, checks of weight $O_ε(1)$, and normalized distance at least $δ_{\mathrm{GV}}(p,R)-ε$. Here, $δ_{\mathrm{GV}}(p,R)$ denotes the quantum Gilbert-Varshamov (GV) bound for $p$-ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.
AI Summary
The paper asks whether quantum LDPC codes can match the rate–distance tradeoff and channel-coding guarantees of random stabilizer codes, despite the commutation constraints and unavoidable low-weight stabilizers that obstruct direct random-coding arguments. For any prime $p$, fixed rate $R\in(0,1)$, and $\varepsilon>0$, it constructs an ensemble of $p$-ary stabilizer codes with constant check weight $O_{\varepsilon,R}(1)$ and relative distance at least $H_{p^2}^{-1}((1-R)/2)-\varepsilon$, with exponentially high probability. Related guarantees approach erasure-channel capacity $1-2\kappa$ and the hashing rate $1-H(\nu)/\log_2p$ for memoryless Pauli noise. The construction starts from existing asymptotically good QLDPC codes and applies quantum Alon–Edmonds–Luby expander-based distance amplification. The key additional analysis controls degeneracy: near-Singleton outer codes can have at most $|L|^\eta$ stabilizers below a specified distance threshold, for arbitrarily small constant $\eta$. Independent random symplectic encodings within constant-size blocks then produce the ensemble. In the simplest model, every fixed Pauli error is a nontrivial undetectable error with probability at most $p^{-N(1-R-\gamma)}$, enabling union-bound proofs of distance and channel guarantees. The construction relies on existing good QLDPC families rather than providing an independent random construction of them. Check weights and alphabet/block sizes depend on the approximation parameters. Efficient decoding is discussed for a constant fraction of adversarial errors, not up to the GV distance or the stated channel limits; the Pauli-channel proof uses a typical-error decoder without an efficiency guarantee.
ChatGPT Sol 5.6 was used to assist with checking proofs, generating figures, performing literature searches, and drafting parts of this manuscript.
Error found: The abstract states an ε-only check-weight bound, whereas the proved locality guarantee allows dependence on the target rate R as well as ε.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.