An efficient decoder for a linear distance quantum LDPC code

DOI10.1145/3564246.3585169MaRDI QIDQ6401991zbMATH OpenWikidataFDO

Authors S. Gu, Christopher A. Pattison, Eugene Tang

Publication date 13 June 2022

Full work available at URL https://doi.org/10.1145/3564246.3585169

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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.

Cited in

(3)

• Pseudorandom linear codes are list-decodable to capacity
• Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes
• When can an expander code correct (n) errors in O(n) time?

This page was built for publication: An efficient decoder for a linear distance quantum LDPC code

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6401991)