{"id":"arxiv/2608.17109","url":"https://arxiv.org/abs/2608.17109","tags":["quant-ph","cs.CC"],"score":0,"title":"Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes","domain":"quant-ph","source":"arxiv","authors":["Louay Bazzi","Georges Khater"],"reviews":0,"subject":"quant-ph","summary":"Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the $X$- and $Z$-syndromes. For color codes under independent $X$- and $Z$-error models, we consider Separate Minimum-Weight decoding. Assuming $P\\neq NP$, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-08-17","reactions":{}}