Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound
Abstract
We show that for any R,ε>0 and any prime p≥ 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 δGV(p,R)−ε. Here, δ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.
Related
- Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound
- Optimal Average Success Probabilities of Binary (n,n−1) and (n,n−2) Quantum Random Access Codes
- From Random Quantum Codes to Explicit qLDPC Codes via Local Properties
- Quantum Message Passing Convergence and Vanishing Block-Error Probability for Random LDPC Codes
- Polynomial-Time Constructions of Asymptotically Good Random Access Codes from Linear Codes
BibTeX
@misc{mittal2026random,
title = {{Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound}},
author = {Tushant Mittal and Shashank Srivastava and Madhur Tulsiani and Mary Wootters},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02648},
eprint = {2610.02648},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02648},
}
RIS
TY - UNPB
TI - Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound
AU - Tushant Mittal
AU - Shashank Srivastava
AU - Madhur Tulsiani
AU - Mary Wootters
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02648
UR - https://arxiv.org/abs/2610.02648
AB - We show that for any R,ε>0 and any prime p≥ 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 δ_GV(p,R)−ε. Here, δ_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.
ER -