Short answer: The union-find decoder is a classical algorithm that reads the error syndrome from a topological quantum code and decides how to correct it, with a running time that grows almost linearly in the number of qubits. A 2021 paper introduced it, and a 2023 paper shows how it could run on a lattice of simple processors with local links. Both are algorithm and architecture studies.
Why decoding speed matters
The 2021 paper in Quantum states the goal: to build a large-scale quantum computer, errors must be corrected extremely fast. It stresses worst-case rather than average running time, because the maximum running time of the decoder is what determines the clock time of the quantum computer. A 2023 Quantum paper says fault-tolerant quantum computing needs classical hardware to perform the decoding for error correction, and calls the union-find decoder one of the best candidates.
The 2021 algorithm
The authors design a decoding algorithm for topological codes that corrects Pauli errors, erasure, and combinations of both. Its worst-case complexity is O(n alpha(n)), where n is the number of physical qubits and alpha is the inverse of Ackermann's function, which grows extremely slowly and which they say is at most 3 for all practical purposes. The key idea is the union-find data structure, which lets the decoder track and update its estimate of the error as it runs. They prove it performs optimally for errors of weight up to (d-1)/2 and for loss of up to d-1 qubits, where d is the code's minimum distance. Numerically they report a threshold of 9.9% for the two-dimensional toric code with perfect syndrome measurements, and 2.6% with faulty measurements.
A local hardware realisation, 2023
The 2023 paper notes that the decoder has characteristics, namely growth and merger of data structures through nearest-neighbour steps, that suggest implementation on a lattice of simple processors with nearest-neighbour links, spreading the computing load with near-ideal parallelism. The authors show for the first time that strict locality is practical, with worst-case runtime O(d cubed) and mean runtime subquadratic in the surface code distance d. A new parity-calculation scheme can simplify earlier architectures, and the approach is optimised for circuit-level noise. They compare the local version with one augmented by long-range links, which is faster, and note that local asynchronous logic could negate the difference.
Where it fits
Decoders sit between the measured syndromes and the control system, so their speed and cost affect how a surface code can be run. The 2021 result concerns the algorithm itself, with its threshold and worst-case scaling. The 2023 result concerns where the computation could live, spread across many small processors close to the qubits' data layout. Together they show the same decoder studied at two levels, as an algorithm and as a hardware design, with the second paper assuming the first paper's approach.
Limits
The thresholds are for the specific noise models in the 2021 paper, and the 2023 runtimes are theoretical figures for a proposed architecture. Neither paper reports a decoder running in a deployed quantum computer.
FAQ
What does a decoder do?
It takes the measured syndrome and decides which correction to apply.
Why is almost-linear time important?
The decoder's worst-case time sets the machine's clock time, per the 2021 paper.
What threshold was reported?
9.9% for the toric code with perfect measurements, and 2.6% with faulty measurements.
Can it be made local?
The 2023 paper shows a strictly local version with worst-case runtime O(d cubed).
Is it deployed?
These papers do not report that.
All field notes