Quantum Tanner codes and good quantum LDPC codes

Short answer: Quantum Tanner codes are a construction of quantum error-correcting codes from two classical Tanner codes defined on a shared graph structure, and they give asymptotically good quantum low-density parity-check codes. The 2022 FOCS paper by Leverrier and Zemor introduces them with a minimum distance that grows linearly, a 2022 arXiv preprint adds decoders, and a 2024 arXiv preprint generalizes the construction. This is mathematical coding theory, with no hardware involved.

The construction

The FOCS 2022 abstract starts from Tanner codes, which are long error correcting codes made from short codes and a graph, with bits on the edges and parity-check constraints from the short codes enforced at the vertices. Combining good short codes with a spectral expander graph gives the expander codes of Sipser and Spielman, which are asymptotically good classical LDPC codes. Leverrier and Zemor apply this to the left-right Cayley complex central to a recent construction of a locally testable code by Dinur and coauthors. They view the complex as two graphs sharing the same edges, define a Tanner code on each, and obtain two classical codes that together define a quantum code.

The authors describe this as a simplified variant of the Panteleev and Kalachev asymptotically good quantum LDPC code, with improved estimates for its minimum distance. They prove a theorem that simultaneously gives a linearly growing minimum distance for the quantum code and recovers the local testability of the Dinur et al. code.

2022: decoders

A 2022 arXiv preprint introduces sequential and parallel decoders for quantum Tanner codes. When the construction is applied to a sufficiently expanding square complex with robust local codes, the authors say they obtain a family of asymptotically good quantum LDPC codes, and their decoders provably correct arbitrary errors of weight linear in the code length, in linear or logarithmic time respectively. They say the decoders adapt easily to the expander lifted product codes of Panteleev and Kalachev, and that using recent bounds on the robustness of random tensor codes they give a tighter bound on the minimum distance.

2024: a generalization

A 2024 arXiv preprint generalizes quantum Tanner codes, which had been built from groups, Cayley graphs or square complexes made from groups. The authors enlarge this to group actions on finite sets, Schreier graphs and a family of square complexes, which they say is the largest possible in a certain sense, and discuss how this opens the possibility of finding other families of asymptotically good quantum codes.

Limits

These are results about code families and decoding in the abstract setting of error models studied by the authors. The two arXiv works are preprints. None of the abstracts describes an implementation on a quantum device, and practical use would depend on connectivity and noise considerations they do not address.

FAQ

What does asymptotically good mean?

In the abstracts, that the code family has constant rate and a minimum distance growing linearly with the code length, for the construction studied.

Who introduced quantum Tanner codes?

Leverrier and Zemor, in the FOCS 2022 paper.

Can they be decoded efficiently?

The 2022 preprint reports provable decoders for errors of weight linear in the code length, in linear or logarithmic time.

What did the 2024 preprint add?

A broader family of constructions from group actions and Schreier graphs.

Has this been built?

None of the abstracts reports a hardware implementation.