Decoders for quantum LDPC codes

[Fe-r-oz]

Is your feature request related to a problem? Please describe.

The paper, Fast Erasure Decoder for Hypergraph Product Codes, introduces several specific decoders for quantum LDPC codes. Specifically, It presents an efficient decoder aimed at correcting 'erasures' or 'detectable qubit loss' in hypergraph product (HGP) codes. By treating erased qubits as uniformly random mixed states, it transform the erasure correction problem into one of error correction. Numerical simulations demonstrate that the proposed Pruned Peeling + VH decoder achieves a logical error rate comparable to the maximum likelihood (ML) decoder, with a probabilistic variant operating in O($N^{1.5}$) bit operations, where $N$ is the code length.

Describe the solution you’d like

The aforementioned paper provides the algorithmic implementations of the first four decoders and compares the performance of these decoders with Maximum Likelihood (ML) decoder (see Fig 4). Overall, the following specific decoders for quantum LDPC codes are highlighted in the paper:

• Classical Peeling decoder (Algorithm 1)
• Pruned Peeling decoder (Algorithm 2)
• Vertical-Horizontal (VH) (Algorithm 3)
• Pruned Peeling + VH
• Viderman decoder for quantum LDPC codes
• Generalization of Union-Find decoder for quantum LDPC codes
• Small-Set Flip decoder for HGP codes

In addition, the python implementation of the Pruned Peeling and VH decoder is also provided by the paper here: https://github.com/Nicholas-Connolly/Pruned-Peeling-and-VH-Decoder

The numerical simulations demonstrate that Pruned Peeling + VH decoder offers near-optimal performance and can be implemented with O($N^2$) complexity. This decoder can also serve as a subroutine to enhance decoders like the BP-OSD decoder, Union-Find decoder, or Viderman's decoder.

Describe alternatives you’ve considered

To be added soon.

Additional context

A closely related paper, Toward a Union-Find decoder for quantum LDPC codes provides algorithmic implementation of UF decoder for quantum LDPC codes (Algorithm 1, page 9). The performance of this generalized version of UF decoder for quantum LDPC codes is compared with Belief Propagation (BP) decoder. Notably, the paper demonstrates that the decoder reliably corrects errors up to a certain weight for various quantum LDPC codes, including toric, hyperbolic, and quantum expander codes in dimensions $D ≥ 3$. Also, it notes that both the Renormalization Group (RG) decoder and decoders based on local rules are impractical/unfeasible, leading the authors to propose the generalized UF decoder for quantum LDPC codes as a more feasible solution.