Decoder Accuracy vs Speed
Every practical decoder sits on a curve trading correction quality against runtime, and the right choice depends on the hardware's error rate and clock.
The trade-off curve
Decoders range from very fast and approximate to slow and near-optimal. Union-find is extremely fast and near-linear time but slightly less accurate. Minimum-weight matching is more accurate but slower. Tensor-network and full maximum-likelihood decoders are the most accurate and the slowest. A machine must pick a point on this curve that fits its qubit speed and target logical error rate.
Why speed is a hard constraint
Syndromes arrive every cycle, often every microsecond on superconducting hardware. If the decoder cannot keep up, unprocessed syndromes pile up, a backlog that grows without bound and stalls the computation. This backlog problem means a slightly less accurate decoder that keeps pace can outperform a more accurate one that falls behind.
- Union-find: near-linear time, small accuracy penalty.
- Matching: higher accuracy, higher runtime, still practical.
- Tensor-network: best accuracy, generally offline only.
- Falling behind the syndrome rate causes an unbounded backlog.
Accuracy also interacts with distance. A better decoder effectively raises the code's threshold and lowers the logical error rate at fixed distance, which can mean a smaller code reaches the same protection. So decoder quality trades against qubit count, not just against runtime.
The current consensus is a layered strategy: a fast local decoder handles the common cases in real time, escalating rare, ambiguous cases to a slower, more accurate decoder, and using windowing so the fast path never stalls. This keeps average latency low while preserving accuracy where it matters most.