Approximating optimal decoding of quantum LDPC codes with narrow frontiers
2026-06-18 • Information Theory
Information Theory
AI summaryⓘ
The authors present the Frontier decoder, a smart method to fix errors in quantum computers by focusing only on the most important error possibilities. It works by looking at errors step-by-step, combining similar cases, and keeping track of a small number of likely outcomes to save time. This method is very accurate for certain quantum error-correcting codes and works efficiently even when noise is more complicated. Because it keeps the number of cases low, it can run quickly and might be used in real-time error correction.
Quantum error correctionSurface codeColor codeDynamic programmingCircuit-level noiseLogical qubitDecoderPruningList decodingQuantum computing
Authors
Anthony Leverrier, Rüdiger Urbanke
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.