Asymptotically good Quantum and locally testable classical LDPC codes
Pavel Panteleev, Gleb Kalachev
2022Year
214Citations
42Top-tier citations
Abstract
We study classical and quantum LDPC codes of constant rate obtained by the lifted product construction over non-abelian groups. We show that the obtained families of quantum LDPC codes are asymptotically good, which proves the qLDPC conjecture. Moreover, we show that the produced classical LDPC codes are also asymptotically good and locally testable with constant query and soundness parameters, which proves a well-known conjecture in the field of locally testable codes.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Cited by top-tier papers42
- Quantum Tanner codesAnthony Leverrier, Gilles ZémorFOCS 2022 · 121 citations
- Good Quantum LDPC Codes with Linear Time DecodersIrit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas VidickSTOC 2023 · 83 citations
- NLTS Hamiltonians from Good Quantum CodesAnurag Anshu, Nikolas P. Breuckmann, Chinmay NirkheSTOC 2023 · 50 citations
- An Efficient Decoder for a Linear Distance Quantum LDPC CodeShouzhen Gu, Christopher A. Pattison, Eugene TangSTOC 2023 · 27 citations
- Explicit Lossless Vertex ExpandersJun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner et al.FOCS 2025 · 21 citations
Builds on4
- Fiber bundle codes: breaking the n1/2 polylog(n) barrier for Quantum LDPC codesMatthew B. Hastings, Jeongwan Haah, Ryan O'DonnellSTOC 2021 · 74 citations
- Decodable quantum LDPC codes beyond the square root distance barrier using high dimensional expandersShai Evra, Tali Kaufman, Gilles ZémorFOCS 2020 · 33 citations
- New cosystolic expanders from tensors imply explicit Quantum LDPC codes with Ω(√n logk n) distanceTali Kaufman, Ran J. TesslerSTOC 2021 · 15 citations
- Locally testable codes with constant rate, distance, and localityIrit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky et al.STOC 2022 · 4 citations
Related papers
- Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable CodesIrit Dinur, Ting-Chun Lin, Thomas VidickFOCS 2024 · 4 citations
- Robust Local Testability of Tensor Products of Constant-Rate Algebraic Geometry CodesSumegha Garg, Akash Kumar SenguptaFOCS 2025
- Maximally Extendable Product Codes are Good Coboundary ExpandersGleb Kalachev, Pavel PanteleevFOCS 2025 · 14 citations
- Quantum Fault Tolerance with Constant-Space and Logarithmic-Time OverheadsQuynh T. Nguyen, Christopher A. PattisonSTOC 2025 · 5 citations
- Decoding Quasi-Cyclic Quantum LDPC CodesLouis Golowich, Venkatesan GuruswamiFOCS 2024 · 1 citation
