Fast offline decoding with local message-passing automata

Abstract

We present a local offline decoder for topological codes that operates according to a parallelized message-passing framework. The decoder works by passing messages between anyons, with the contents of received messages used to move nearby anyons towards one another. We prove the existence of a threshold, and show that in a system of linear size $L$, decoding terminates with an $O((\log L{)}^{\hat{I}}\cdot )$ average-case runtime, where $\hat{I}\cdot$ is a small constant. For the toric code subject to i.i.d Pauli noise, our decoder has $\hat{I}\cdot =1$ and a threshold at a noise strength of $p_c\approx 7.3\%$.

48+22 pages, 20 figures; v4: updated refs