The Union-Find Decoder
The union-find decoder grows clusters around surface-code defects and merges them, achieving almost-linear speed with near-matching accuracy.
Trading accuracy for speed
Minimum-weight perfect matching is accurate but its runtime grows faster than linearly in the number of defects, which strains real-time decoding at large code distances. The union-find decoder, introduced by Delfosse and Nickerson, sacrifices a small amount of accuracy to run in almost-linear time, close to the theoretical minimum, making it attractive for hardware where the decoder must keep pace with the syndrome stream.
How it works
The decoder grows a cluster around each defect on the syndrome graph, expanding all clusters outward step by step. When two clusters touch, they merge. A cluster is even when it contains an even number of defects, meaning the defects inside it can be paired off by an internal error chain. Growth continues until every cluster is even, at which point a spanning-tree peeling step reconstructs a valid correction inside each cluster. The union-find data structure makes the repeated merge-and-check operations extremely fast.
- Grow clusters around defects; merge on contact.
- Stop when every cluster has an even number of defects.
- Peel a spanning tree to read out the correction within each cluster.
- Almost-linear runtime via the union-find (disjoint-set) structure.
Where it fits
The union-find decoder achieves a threshold only slightly below that of minimum-weight perfect matching, typically within a fraction of a percent, while being far faster and simpler to implement in hardware such as FPGAs or ASICs. This combination has made it a leading choice for real-time surface-code decoding, where latency directly limits how long logical qubits can be kept alive.
Like matching, it operates on the space-time syndrome graph to handle measurement errors, and variants add weighting to recover some of the accuracy lost relative to exact matching. It is a good example of how decoder engineering, not just code design, sets the practical performance of a fault-tolerant machine.