Asymptotically good Quantum and locally testable classical LDPC codes

By Pavel Panteleev, Gleb Kalachev. Symposium on the Theory of Computing, 2021

480 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/973afb39e5eee258d32988f8f4b31f77fe124cf4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

The future of quantum computing with superconducting qubits (2022, background): “A recent breakthrough result 52 demonstrated the existence of so-called good quantum LDPC codes that combine a constant encoding rate k/n (which can be arbitrarily close to 1) and a linear distance d ≥ cn for some constant c > 0.”
High-threshold and low-overhead fault-tolerant quantum memory (2023, methodology): “The latter were shown 39,40 to be asymptotically ‘good’ in the sense of offering a constant encoding rate and linear distance: a parameter quantifying the number of correctable errors.”
Quantum error mitigation (2022, background): “There is ongoing theoretical research to find alternative codes with a more favourable overhead, and recent progress gives reasons to be optimistic (Breuckmann and Eberhardt, 2021; Dinur et al. , 2022; Gottesman, 2014; Panteleev and Kalachev, 2022).”