Metraipolis › archive › dc_f899eb99a62d

Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time — arXiv:2609.40313

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.40313
License (as archived)
CC0-1.0
Archived
2026-10-07T14:40:52.630Z
SHA-256 of the archived text
5f246eed46191cedb3b2e9fead94ddf53307790fdd4d0342109565b710aa9349
Stable URL of this page
https://metraipolis.com/documento/dc_f899eb99a62d

How to cite

Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time — arXiv:2609.40313 — arXiv (en), https://arxiv.org/abs/2609.40313 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f899eb99a62d (Metraipolis archive dc_f899eb99a62d, sha256 5f246eed46191cedb3b2e9fead94ddf53307790fdd4d0342109565b710aa9349)
BibTeX
@misc{dcf899eb99a62d,
  title = {Explicit Capacity-Achieving Quantum LDPC Codes List Decodable in Near-linear Time — arXiv:2609.40313},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40313},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f899eb99a62d; sha256 5f246eed46191cedb3b2e9fead94ddf53307790fdd4d0342109565b710aa9349},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40313. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in math.IT).
Categorie arXiv: Quantum Physics (quant-ph) ; Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.40313 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:14:20.810Z dalla pagina https://arxiv.org/catchup/math.IT/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).