Union-Find Decoder

The almost-linear-time decoder of Delfosse and Nickerson, run step by step. Qubits are the edges of a decoding graph and checks are its vertices; an error chain is visible only through the defects at its ends. The decoder first turns the Pauli problem into an erasure problem: every odd cluster of defects grows by half an edge per round and clusters that meet are merged with a union-find forest, until every cluster is neutral. Then the peeling decoder reads the correction off a spanning forest of the grown region, leaf by leaf. Use the planar surface code with distance, error and erasure controls, or load your own parity-check matrix.

defect $s_v=1$ check $s_v=0$ boundary vertex error $e$ (hidden from the decoder) erased qubit half-edge growth front grown edge (erasure $\mathcal E$), cluster colour cluster root spanning forest (blue ring: its root) 3 peeling order correction $\hat e$
1 / 1

1 · Instance

5
0.08
0.00

2 · Run the decoder

Each odd cluster (odd number of defects and no boundary vertex) grows by half an edge along every edge leaving it. An edge that becomes fully grown joins the erasure $\mathcal E$ and union merges the clusters at its two ends. Odd clusters now: ; rounds so far: .
Every cluster is now neutral: even, or touching a boundary. The fully grown edges form the erasure $\mathcal E$, and Lemma 1 of Delfosse and Nickerson guarantees that a correction with the observed syndrome lies inside it. Hand $\mathcal E$ to the peeling decoder.
A spanning forest $F$ of $\mathcal E$ was grown from the boundary vertices (or from the cluster root when there is none). Vertices are peeled in reverse order of discovery, so each one is a leaf when its turn comes: if the leaf is a defect, its pendant edge goes into $\hat e$ and the defect moves to the parent; otherwise the edge is set to 0.
The correction $\hat e$ is complete and reproduces the syndrome. On the surface code the residual $e \oplus \hat e$ is a closed chain: a product of stabilizers if it crosses the left boundary an even number of times, a logical error if it crosses it an odd number of times.
An odd cluster has swallowed its whole connected component and cannot reach a boundary: no correction with this syndrome exists in this graph. This cannot happen for a syndrome produced by an actual error.
$$\text{grow while } \exists\, C:\ \perp\notin C\ \ \wedge\ \ \textstyle\sum_{v\in C} s_v \equiv 1 \pmod 2$$
$$\forall\, C:\ \ \perp\in C\ \ \lor\ \ \textstyle\sum_{v\in C} s_v \equiv 0 \pmod 2 \quad\Longrightarrow\quad \exists\, \hat e \subseteq \mathcal E:\ \partial \hat e = s$$
$$\text{leaf } u \text{ with pendant edge } \{u,w\}:\qquad \hat e_{uw} \leftarrow s_u,\quad s_w \leftarrow s_w \oplus s_u,\quad s_u \leftarrow 0$$
$$\partial(e \oplus \hat e) = \mathbf 0,\qquad \text{logical error} \iff \big|(e \oplus \hat e) \cap \partial_{\mathrm{L}}\big| \equiv 1 \pmod 2$$
$$s \notin \operatorname{im} H$$

Syndrome $s = He \bmod 2$

Union-find clusters

Disjoint-set arrays (roots in yellow)

Parity-check matrix $H \in \mathbb F_2^{\,m\times n}$

Show $H$ (one column per qubit, one row per check)
Column $j$ is qubit $Q_j$ and defines an edge: weight 2 gives the edge $\{C_a, C_b\}$, weight 1 gives the edge $\{C_a, \perp\}$ (the $\partial$ row names the boundary vertex). Red columns carry the error $e$, yellow ones the correction $\hat e$.

Step log

How the Union-Find decoder works

1. The decoding graph

Qubits sit on the edges of a graph $G = (V, E)$ and checks on its vertices; here the vertices are the $X$ checks of a planar surface code of distance $d$ and the errors are $Z$ flips. An error set $e \subseteq E$ flips the checks it touches an odd number of times, so the syndrome is the boundary $s = \partial e$. Edges that end on a boundary vertex $\perp$ have only one check, and a chain may end there unnoticed. A decoder must output $\hat e$ with $\partial \hat e = s$. It succeeds if $e \oplus \hat e$ is a product of stabilizers (a closed chain that crosses the left boundary an even number of times) and fails if $e \oplus \hat e$ is a logical operator (a chain from the left boundary to the right one).

2. Erasures are easy: peeling

If the error is known to lie inside an erased set $\mathcal E$, Delfosse and Zémor find a correction in time $O(|\mathcal E|)$. Take a spanning forest $F$ of $\mathcal E$ and repeatedly remove a leaf edge $\{u, w\}$ with pendant vertex $u$: if $u$ is a defect, put the edge in $\hat e$ and flip $w$; otherwise drop the edge. A tree contains exactly one correction for an even set of defects (and exactly one for any set of defects when its root is a boundary vertex), so the peeling order does not matter. With boundaries the forest is grown from the boundary vertices as seeds and peeled back towards them.

A correction exists inside $\mathcal E$ if and only if every connected component of $\mathcal E$ holds an even number of defects or touches a boundary. This is the condition the growth stage establishes.

3. Syndrome validation: cluster growth

For Pauli errors there is no erasure, so the decoder builds one. Every defect starts as a cluster of its own; erased qubits form the initial clusters. While an odd cluster exists, every odd cluster grows by half an edge along all edges leaving it. An edge that becomes fully grown joins $\mathcal E$ and union merges the clusters at its ends. A cluster stops as soon as it is neutral: even, or touching a boundary.

Half-edge steps let two fronts meet in the middle of an edge in the same round. Whole-edge steps (try the switch above) reach a neighbour one round earlier but add about twice as many qubits to $\mathcal E$, which makes the final erasure more likely to contain a logical operator.

4. Union-find, and why it is almost linear

Clusters live in a disjoint-set forest: parent[v] points towards the cluster root, and the root stores the cluster size, its defect parity and whether it touches a boundary. find(v) walks to the root and shortens the path on the way (path compression); union(a, b) hangs the smaller root under the larger one and combines the three fields in $O(1)$. Tarjan showed that $n$ such operations cost $O(n\,\alpha(n))$, where $\alpha$ is the inverse Ackermann function and $\alpha(n) \le 3$ for any physical $n$.

Each edge is grown at most twice, each vertex joins the boundary of a growing cluster during at most two rounds, and peeling is linear in $|\mathcal E|$. The whole decoder therefore runs in $O(n\,\alpha(n))$, against $O(n^3)$ or worse for minimum-weight perfect matching, depending on the implementation. The support table $\texttt{fill}[j] \in \{0, \tfrac12, 1\}$ shown in the picture is the only per-edge state.

5. Guarantees and limits

Theorem (Delfosse and Nickerson). If $t$ qubits are erased and $s$ further qubits carry errors with $t + 2s < d$, the decoder corrects them. The proof: a cluster grows only while an error chain leaves it, so after at most $2s$ rounds every chain is covered, the largest cluster has diameter at most $2s + t < d$, and an erasure that small contains no logical operator, so peeling cannot land in the wrong class. The exhaustive tests behind this page confirm it for $d = 3, 5, 7$.

Above that bound the decoder is weaker than matching: clusters grow blindly in all directions, and peeling returns the unique correction inside the forest rather than the lightest one. The preset UF fails where MWPM succeeds shows a case where a lighter correction in the correct class exists. On the toric code with perfect measurements the threshold is $9.2\%$ with the uniform growth used here, $9.9\%$ when the smallest clusters grow first, and $10.3\%$ for MWPM.

6. Reading the picture

  • Coloured discs are checks; the colour is the cluster they belong to and the filled dot marks the cluster root. Red rings are defects.
  • Small squares are boundary vertices: one per boundary edge on the surface code, $b$ shared ones for a random or custom $H$.
  • A short coloured stub is a half-grown edge, drawn from the vertex it was grown from. A thick coloured edge is fully grown and belongs to $\mathcal E$.
  • During peeling, blue edges form the forest $F$, numbered badges give the peeling order, and yellow edges are the correction $\hat e$.
  • Click a qubit to add or remove an error (or an erasure), then run the decoder again. The URL always encodes the current instance, so it can be shared.
References: N. Delfosse and N. H. Nickerson, Almost-linear time decoding algorithm for topological codes, Quantum 5, 595 (2021). N. Delfosse and G. Zémor, Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel, Phys. Rev. Research 2, 033042 (2020). S. Huang, M. Newman and K. R. Brown, Fault-tolerant weighted union-find decoding on the toric code, Phys. Rev. A 102, 012419 (2020).