Maximum-Likelihood Decoding
The optimal decoder picks the logical class with the highest total probability, correcting the equivalence class of errors rather than one error.
Degeneracy changes the goal
In a quantum code many distinct physical errors act identically on the encoded state because they differ by a stabilizer. These form an equivalence class, or coset. The right question is not which single error is most likely, but which logical coset is most likely, since any member of the correct coset yields a successful correction. This is maximum-likelihood decoding.
Summing over a coset
For a given syndrome there are typically four cosets, corresponding to the trivial logical operator and the logical X, Z, and Y. The optimal decoder computes the total probability of each coset by summing the probabilities of all errors in it, then applies a correction from the most probable coset. This coset sum is what makes optimal decoding computationally expensive.
- Errors differing by a stabilizer are equivalent, forming a coset.
- Optimal decoding compares coset probabilities, not single-error probabilities.
- This is generally computationally hard in the worst case.
- Degeneracy lets the code beat the nondegenerate Hamming bound.
Minimum-weight decoding, which picks the single lowest-weight error, is a common approximation to maximum-likelihood decoding. They agree when one error dominates its coset, but diverge when many comparable-weight errors add up, which is exactly the regime where the optimal decoder wins. Tensor-network decoders approximate the true coset sum.
Because exact maximum-likelihood decoding is intractable at scale, practical machines use fast approximations (matching, union-find, belief propagation) and reserve optimal decoding for setting the accuracy benchmark. The gap between a fast decoder and the optimal one is a direct measure of how much performance is left on the table.