An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise

Understand

Fault-tolerant quantum computers must be designed in conjunction with classical co-processors that decode quantum error correction measurement information in real-time.

• In this work, we introduce the belief propagation plus ordered Tanner forest (BP+OTF) algorithm as an almost-linear time decoder for quantum low-density parity-check codes.
• The OTF post-processing stage removes qubits from the decoding graph until it has a tree-like structure.
• Provided that the resultant loop-free OTF graph supports a subset of qubits that can generate the syndrome, BP decoding is then guaranteed to converge.