Approximating optimal decoding of quantum LDPC codes with narrow frontiers
Provides a practical, low-complexity decoder for quantum error correction, addressing the bottleneck of optimal decoding for sparse quantum codes.
The Frontier decoder approximates optimal decoding for quantum LDPC codes by pruning dynamic programming, achieving near-optimal thresholds for surface and color codes and state-of-the-art circuit-level performance (e.g., <100 retained list size for the [[144,12,12]] gross code at 0.001 error rate).
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.