Fast offline decoding with local message-passing automata

2025/06/03 by Ethan Lake, Lake, Ethan · 4 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Cellular Automata and Lattice Gases (nlin.CG) #Complexity and Algorithms in Graphs #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Statistical Mechanics (cond-mat.stat-mech) #Strongly Correlated Electrons (cond-mat.str-el)

paper · pdf · doi:10.48550/arxiv.2506.03266

openalex publication_date 2025/06/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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)^η) average-case runtime, where η is a small constant. For the toric code subject to i.i.d Pauli noise, our decoder has η=1 and a threshold at a noise strength of p_c≈ 7.3%.

Cited by

• Local active error correction from simulated confinement
• Squeezing codes: robust fluctuation-stabilized memories
• Exploring the Landscape of Non-Equilibrium Memories with Neural Cellular Automata
• Scalable dissipative quantum error correction for qubit codes

Related

• A local automaton for the 2D toric code
• A blindness property of the Min-Sum decoding for the toric code
• Tradeoff between decoding complexity and rate for codes on graphs
• Local active error correction from simulated confinement
• On Locally Decodable Codes in Resource Bounded Channels