arXiv:2610.16375
Pathfinder-BP: A Low-Latency Recursive Decoder for Topological Codes
Stefano Tinelli, Francisco Lázaro, Francisco García Herrero
Abstract
We propose Pathfinder-BP, a recursive decoder for topological quantum codes that combines belief propagation with controlled bit-flipping. An initial BP pass identifies and permanently fixes high-confidence errors. Upon convergence failure, the decoder recursively explores alternative error patterns by tentatively flipping low-confidence variables. On surface codes, Pathfinder-BP achieves a noise threshold and logical error rate comparable to minimum-weight perfect matching (MWPM). A crucial advantage of Pathfinder-BP is its highly parallelizable structure, which yields a worst-case decoding latency quasi-linear in the code distance, making it a suitable candidate for low-latency hardware implementation.
AI Summary
Pathfinder-BP addresses whether belief-propagation decoding can approach minimum-weight perfect matching (MWPM) performance on surface codes while limiting worst-case decoding latency. It combines BP with heuristic decimation and parallel speculative bit-flip searches, avoiding matrix inversion. After an initial BP pass fails, variables whose posterior beliefs changed sign exactly once and ended sufficiently negative are permanently fixed as errors. Checks are ranked by how often they remained unsatisfied; low-confidence neighboring variables seed separate search branches. Each branch repeatedly fixes additional errors and runs BP on the residual syndrome, stopping at convergence or a prescribed depth. The minimum-weight converged candidate is returned. Monte Carlo simulations use planar surface codes with distances $d=3,5,\ldots,15$, independent phase-flip noise, and perfect syndrome measurements. Each data point collects 100 logical failures. With branch count and depth $\eta=t=2d$, the reported finite-size threshold is approximately $0.103$, with logical error rates comparable to MWPM. At $d=11$, comparable performance is also reported for $\eta=t=d$. Assuming fully parallel BP cores, the iteration cap is $T_1+tT_2=50+30d$ for $\eta=t=2d$, requiring $O(d^3)$ processing elements; global reductions add hardware overhead. At $d=11$ and physical error rate $0.04$, the mean is 102 iterations and the cap is 380, versus 120 and 36,140 for the tested relay-BP configuration. The latency analysis assumes parallel hardware rather than demonstrating an implementation. Tests cover only code-capacity surface-code decoding; other CSS families, correlated noise, and circuit-level noise are left for future work.
Error found: The abstract's MWPM-comparable performance claim is supported only for code-capacity noise with perfect syndrome extraction and independent X/Z errors. The latency scaling assumes fully parallel hardware with O(d^3) processing elements and fixed BP iteration caps, whose MWPM-comparable performance is tested only through distance 15. The clock-cycle derivation omits repeated global-operation overhead: its stated per-recursion costs contribute O(t log n), although including this term preserves quasi-linear scaling in code distance.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.