arXiv:2609.40313
Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
William Gay, Fernando Granha Jeronimo, Abhi Shukul
Abstract
In classical coding theory, the quest for explicit codes achieving list decoding capacity has been an important driving force. While random codes are easily shown to achieve capacity, an explicit construction was only discovered decades later in the seminal work [Guruswami and Rudra, STOC 2006]. In quantum coding theory, it is highly desirable that a code family be LDPC. While good quantum codes were known for decades, obtaining the additional LDPC property was elusive. In fact, only very recently that good quantum LDPC codes were discovered in a breakthrough work [Panteleev and Kalachev, STOC 2022]. In this context, a natural question is to ask for an explicit family of quantum codes achieving list decoding capacity while also possessing the important LDPC property. In this work, we provide (to the best of our knowledge) the first explicit constructions of quantum LDPC codes achieving list decoding capacity, namely, with a list decoding radius approaching the quantum Singleton bound with constant list sizes. Furthermore, we provide near-linear time (in the block-length) list decoding algorithms approaching capacity. Our explicit code construction are based on expander graphs via the quantum analogue of Alon-Edmonds-Luby (AEL) amplification [Bergamaschi, Golowich and Gunn, STOC 2024], and this enables the important LDPC property. Our efficient list decoding algorithms are obtained by generalizing the classical expander-based weak-regularity list decoding algorithms [Srivastava and Tulsiani, FOCS 2025] [Jeronimo and Singh, 2025] to suitable instantiations of quantum AEL.
AI Summary
The paper asks whether explicit quantum LDPC codes can be list decoded to a radius approaching the quantum Singleton bound, with constant list size and near-linear decoding time. Previous polynomial-time list decoding of quantum AEL LDPC codes reached only the Johnson radius. For every target rate $R\in(0,1)$ and fixed gaps $\zeta,\xi>0$, it constructs explicit binary CSS families with actual rate $R_N\ge R$, bounded check row and column weights, certified relative distance $\delta_N\ge(1-R_N)/2-\zeta$, and list-decoding radius $\tau_N\ge\delta_N-\xi$. Distance and error weight are measured on constant-size folded blocks, not individual qubits. For either CSS error type, every syndrome admits only constantly many stabilizer cosets containing errors within that radius. A randomized syndrome-input decoder covers all these cosets with probability $1-o(1)$ in $\widetilde O_{R,\zeta,\xi}(N)$ time. The construction combines quantum AEL distance amplification, high-rate quantum Tanner outer codes, constant-size inner CSS codes found by exhaustive search, and constant-degree expanders. Local syndrome lifting avoids a global linear solve. Expander weak regularity generates a constant candidate family; outer syndrome decoding stitches candidates together modulo stabilizers. The rigidity argument requires distance bounds for both logical differences and nonzero inner stabilizers. The asymptotic guarantees hide large parameter-dependent constants: the stated list bound is doubly exponential in polynomial inverse decoding slack, and block sizes and check weights depend on the fixed gaps. Output lists may include extra syndrome-consistent cosets; the decoder does not test whether each contains a low-weight representative.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- SODA 2027, to Appear