Syndrome Decoding

Syndrome Decoding

Syndrome decoding is the classical algorithm that interprets the syndrome (the parity check outcomes; larger codes call these stabilizer measurements) and identifies the most likely error to correct. It is the "brain" of a quantum error correcting system, running on classical hardware adjacent to the quantum processor.

The syndrome and parity check matrix:

For a code with parity check matrix H, the syndrome s is computed as:

s = H · e (mod 2)

where e is the error vector (1 where an error occurred, 0 elsewhere). The syndrome doesn't tell you the exact error: only the equivalence class: any error e' with H·e' = s has the same syndrome as e.

Syndrome table (lookup decoding):

For small codes, the simplest decoder is a lookup table mapping each syndrome to the most likely error:

For small codes (distance 3, 5 qubits), this works perfectly. For large codes, the table has $2^{n-k}$ entries: exponential in n.

Minimum-weight perfect matching (MWPM):

For the surface code, a 2D code you will meet later in this track, syndrome measurements mark "defects" (stabilizers that measured -1). A Z error creates two X-defects; an X error creates two Z-defects. MWPM finds the minimum-weight set of error chains that connects all defect pairs: