An Efficient Decoder for a Linear Distance Quantum LDPC Code

Recent developments have shown the existence of quantum low-density parity check (qLDPC) codes with constant rate and linear distance. A natural question concerns the efficient decodability of these codes. In this paper, we present a linear time decoder for the recent quantum Tanner codes construction of asymptotically good qLDPC codes, which can correct all errors of weight up to a constant fraction of the blocklength. Our decoder is an iterative algorithm which searches for corrections within constant-sized regions. At each step, the corrections are found by reducing a locally defined and efficiently computable cost function which serves as a proxy for the weight of the remaining error.

Authors

• Shouzhen Gu
• Christopher A. Pattison
• Eugene Tang

Keywords

• Quantum error correction
• decoding algorithm
• expander graphs
• quantum low-density parity-check codes
• robust error-correcting codes