EUVIMEDEUVIMED entdecken
Crossref

Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders

Shai Evra, Tali Kaufman, Gilles Zémor

SIAM Journal on Computing · 2024-12 · 53 (6) · FOCS20-276-FOCS20-316

DOI: 10.1137/20m1383689 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 14.06.2022. Verfasst von Shai Evra und 2 weiteren Autor:innen. Die Arbeit wurde bisher 26-mal zitiert (Crossref) und nennt 32 Literaturangaben. Gefördert von: Agence Nationale de la Recherche, Azrieli Foundation, H2020 European Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Constructing quantum low-density parity-check (LDPC) codes with a minimum distance that grows faster than a square root of the length has been a major challenge of the field. With this challenge in mind, we investigate constructions that come from high-dimensional expanders, in particular Ramanujan complexes. These naturally give rise to very unbalanced quantum error correcting codes that have a large $X$-distance but a much smaller $Z$-distance. However, together with a classical expander LDPC code and a tensoring method that generalizes a construction of Hastings and also the Tillich–Zémor construction of quantum codes, we obtain quantum LDPC codes whose minimum distance exceeds the square root of the code length and whose dimension comes close to a square root of the code length. When the ingredient is a 2-dimensional Ramanujan complex, or the 2-skeleton of a 3-dimensional Ramanujan complex, we obtain a quantum LDPC code of minimum distance $n^{1/2}\log^{1/2}n$. We then exploit the expansion properties of the complex to devise the first polynomial-time algorithm that decodes above the square root barrier for quantum LDPC codes. Using a 3-dimensional Ramanujan complex, we also obtain an overall quantum code of minimum distance $n^{1/2}\log n$, which sets a new record for quantum LDPC codes.

Förderung

  • Agence Nationale de la Recherche
  • Azrieli Foundation
  • H2020 European Research Council
  • National Science Foundation

Zitieren

APA

Evra, S., Kaufman, T., & Zémor, G. (2024). Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders. SIAM Journal on Computing, 53(6), FOCS20-276-FOCS20-316. https://doi.org/10.1137/20m1383689

Vancouver

Evra S, Kaufman T, Zémor G. Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using High-Dimensional Expanders. SIAM Journal on Computing. 2024;53(6):FOCS20-276-FOCS20-316. doi:10.1137/20m1383689

BibTeX
@article{Evra2024,
  author = {Evra, Shai and Kaufman, Tali and Zémor, Gilles},
  title = {Decodable Quantum LDPC Codes beyond the $\sqrtn$ Distance Barrier Using High-Dimensional Expanders},
  journal = {SIAM Journal on Computing},
  year = {2024},
  volume = {53},
  number = {6},
  pages = {FOCS20--276--FOCS20--316},
  doi = {10.1137/20m1383689}
}
Kostenlos starten →