Decoding from Syndromes

A syndrome is a diagnosis, not a cure. Decoding is the classical step that turns the measured syndrome into a concrete recovery operation — which Pauli to apply, to which qubit, to undo the error. For small codes the decoder is a simple lookup table; for large codes it is a nontrivial algorithm in its own right.

The decoding problem

After syndrome extraction we hold a classical bitstring $s$ . Several different physical errors can produce the same syndrome, so the decoder must pick the most likely one. Under the standard assumption that errors are independent and rare, "most likely" means lowest weight — the fewest single-qubit faults consistent with $s$ . This is minimum-weight decoding.

The bit-flip lookup table

For the three-qubit bit-flip code the two stabilizers $Z_0Z_1$ and $Z_1Z_2$ give a 2-bit syndrome, and each single-qubit $X$ error maps to a distinct value:

\begin{aligned} (s_1,s_2) = (0,0) &\;\Rightarrow\; \text{no error} \\ (s_1,s_2) = (1,0) &\;\Rightarrow\; X \text{ on qubit } 0 \\ (s_1,s_2) = (1,1) &\;\Rightarrow\; X \text{ on qubit } 1 \\ (s_1,s_2) = (0,1) &\;\Rightarrow\; X \text{ on qubit } 2 \end{aligned}

The middle qubit participates in both parity checks, so flipping it trips both bits; the outer qubits each sit in only one check. The recovery is to apply $X$ to the named qubit, which exactly inverts the error.

Degeneracy and the limit

The table only covers errors of weight 0 or 1. A weight-2 error, say $X_0 X_1$ , produces the same syndrome $(0,1)$ as the single error $X_2$ . The minimum-weight decoder will "correct" it as $X_2$ , leaving $X_0 X_1 X_2 = X_L$ — a logical error. This is unavoidable: a distance-3 code guarantees correction only up to one error. Pushing the residual logical error rate down requires a larger-distance code, which is the whole point of the families in the coming lessons.

Decoders for big codes

For the surface code the syndrome is a 2-D grid of parity checks, and minimum-weight decoding becomes a minimum-weight perfect matching problem on a graph — solvable in polynomial time, and the workhorse of today's experiments. The lookup-table idea you implement here is the same principle, just small enough to enumerate by hand.

Try it

Implement decode(s1, s2) returning the index of the qubit to flip (or $-1$ for no error). The grader feeds it the syndrome $(1,1)$ and checks that you return qubit $1$ .

Run your code to see the quantum state.

When the decoder is correct the returned value is 1, matching the middle-qubit error that trips both parity checks.