Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR22-088 | 15th June 2022 17:35

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

RSS-Feed




TR22-088
Authors: Anthony Leverrier, Gilles Zémor
Publication: 15th June 2022 17:56
Downloads: 145
Keywords: 


Abstract:

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 Product codes of Panteleev and Kalachev, and show that our decoder can be adapted to the latter. The decoding algorithm alternates between sequential and parallel procedures and converges in linear time.



ISSN 1433-8092 | Imprint