Anthony Leverrier, Rüdiger Urbanke (Jun 19 2026).
Abstract: We introduce the Frontier decoder, a pruned dynamic-programming decoder for sparse quantum decoding problems. Frontier processes error variables in a chosen order, merges prefixes with the same residual syndrome and logical label, and approximates logical-coset posterior masses by retaining only a narrow scored frontier. Without pruning, the recursion is exact ordered inference with exponential complexity. In the code-capacity setting, the decoder reaches thresholds close to optimal for the surface code and the color code. In the circuit-level noise model, it achieves state-of-the-art performance with a very small average retained list size: less than 100 for the gross code
[[144,12,12]] at a physical error rate of
0.001. When the list size is constant, the decoder has linear complexity, suggesting the possibility of low-latency implementations.
