Quantum LDPC codes achieve capacity with fast list decoding
Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time
Information Theory
Summary
Quantum computers need error-correcting codes to protect information, but these codes must be both good and efficient. The authors describe a new family of quantum codes that are explicit, have low-density parity checks (making them simpler to work with), and achieve the theoretical best error tolerance. They also provide algorithms that can quickly decode these codes even when many errors occur. Their approach builds on recent advances in using special graphs and amplifying properties from classical codes to quantum ones.
What this means in practice
- •For quantum hardware engineers: Implement quantum error correction schemes that tolerate high error rates with efficient decoding, improving quantum processor reliability.
- •For code design teams: Develop new quantum LDPC codes for communication systems requiring explicit, capacity-approaching codes with fast decoding algorithms.
Authors
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.