The Belief-Propagation Decoder
Belief propagation passes probabilistic messages on the check graph to decode general quantum LDPC codes, usually with a post-processing step.
Message passing on the Tanner graph
Belief propagation (BP) is the workhorse decoder for classical low-density parity-check codes and is the natural starting point for quantum LDPC codes. It operates on the Tanner graph, a bipartite graph connecting each qubit to the checks it participates in. Nodes exchange messages estimating the probability that each qubit carries an error, iterating until the estimates converge or a cap is reached. The result is a per-qubit error likelihood from which a correction is read off.
The quantum complication
Plain BP struggles on quantum codes because of degeneracy: many distinct low-weight errors produce the same syndrome and are equally good corrections, so the message-passing iteration can oscillate or get stuck in symmetric traps rather than committing to one. Short cycles in the Tanner graph make this worse. As a result BP alone often fails to reach the code's potential threshold.
- Runs on the qubit-check Tanner graph, passing probability messages.
- Fast and parallel, near-linear per iteration.
- Degeneracy causes stalls that plain BP cannot resolve.
- Almost always paired with a post-processing stage.
BP plus post-processing
The standard fix is BP followed by ordered-statistics decoding (BP+OSD): when BP fails to converge, OSD uses the soft reliabilities BP produced to solve a small linear system that finds a valid correction. This combination decodes a wide range of quantum LDPC codes accurately and is the current default for high-rate codes that do not reduce to a matching problem. Other post-processors include stabilizer inactivation and localized statistics decoding, chosen for speed.
Unlike matching, which is specialized to codes with string-like syndromes such as the surface code, BP-based decoders are general and scale to the sparse, high-rate codes seen as a route to lower overhead. The trade-off is that they are harder to make both fast and reliable in real time, an active area of engineering.