{"id":"arxiv/2606.18145","url":"https://arxiv.org/abs/2606.18145","tags":["quant-ph","cs.DS"],"score":0,"title":"A polynomial-time approximation scheme for minimum-weight decoding of topological codes","domain":"quant-ph","source":"arxiv","authors":["Shouzhen Gu","Lily Wang","Aleksander Kubica"],"reviews":0,"subject":"quant-ph","summary":"Two-dimensional topological translationally invariant (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation, but using them requires solving the decoding problem. Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings, such as the color code with Pauli $Z$ errors and the toric code with Pauli $X$, $Y$ and $Z$ errors. Here, we prove that minimum-weight decoding of 2D TTI codes nonetheless admits a polynomial-time approximation scheme (PTAS), i.e., for any constant $\\varepsilon>0$, a recovery operator of weight within a…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-06-16","reactions":{}}