Toward a Union-Find Decoder for Quantum LDPC Codes

Quantum LDPC codes are a promising direction for low overhead quantum computing. In this paper, we propose a generalization of the Union-Find decoder as a decoder for quantum LDPC codes. We prove that this decoder corrects all errors with weight up to An(alpha) for some A, alpha > 0, where n is the code length, for different classes of quantum LDPC codes such as toric codes and hyperbolic codes in any dimension D >= 3 and quantum expander codes. To prove this result, we introduce a notion of covering radius which measures the spread of an error from its syndrome. We believe this notion could find application beyond the decoding problem. We also perform numerical simulations, which show that our Union-Find decoder outperforms the belief propagation decoder in the low error rate regime in the case of a quantum LDPC code with length 3600.

Automated summary

In this paper, a generalization of the Union-Find decoder for quantum LDPC codes is proposed. It is proven that this decoder corrects all errors with weight up to An(alpha) for different classes of quantum LDPC codes. The notion of covering radius is introduced to measure the spread of errors, and numerical simulations show that the Union-Find decoder outperforms the belief propagation decoder in the low error rate regime for a quantum LDPC code with length 3600.