Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with quantum LDPC code:
TR22-029 | 27th February 2022
Anthony Leverrier, Gilles Zémor

Quantum Tanner codes

Revisions: 2

Tanner codes are long error correcting codes obtained from short codes and a graph, with bits on the edges and parity-check constraints from the short codes enforced at the vertices of the graph. Combining good short codes together with a spectral expander graph yields the celebrated expander codes of Sipser ... more >>>

TR22-088 | 15th June 2022
Anthony Leverrier, Gilles Zémor

Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes

Revisions: 1

We introduce and analyse an efficient decoder for the quantum Tanner codes that can correct adversarial errors of linear weight. Previous decoders for quantum low-density parity-check codes could only handle adversarial errors of weight $O(\sqrt{n \log n})$. We also work on the link between quantum Tanner codes and the Lifted ... more >>>

TR23-178 | 16th November 2023
Louis Golowich, Tali Kaufman

NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes

Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22).

In ... more >>>

ISSN 1433-8092 | Imprint