Decoding Quantum Tanner Codes

We introduce sequential and parallel decoders for quantum Tanner codes. When the Tanner code construction is applied to a sufficiently expanding square complex with robust local codes, we obtain a family of asymptotically good quantum low-density parity-check codes. In this case, our decoders provably correct arbitrary errors of weight linear in the code length, respectively in linear or logarithmic time. The same decoders are easily adapted to the expander lifted product codes of Panteleev and Kalachev. Along the way, we exploit recently established bounds on the robustness of random tensor codes to give a tighter bound on the minimum distance of quantum Tanner codes.

Automated summary

We present sequential and parallel decoders for quantum Tanner codes, which can correct arbitrary errors of weight linear in the code length, respectively in linear or logarithmic time. By applying the Tanner code construction to an expanding square complex with robust local codes, we obtain a family of asymptotically good quantum low-density parity-check codes. Additionally, the same decoders can be easily adapted to the expander lifted product codes of Panteleev and Kalachev. We also provide a tighter bound on the minimum distance of quantum Tanner codes by exploiting recently established bounds on the robustness of random tensor codes.