{"id":"arxiv/2603.22064","url":"https://arxiv.org/abs/2603.22064","tags":["quant-ph","cs.CC"],"score":0,"title":"The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding","domain":"quant-ph","source":"arxiv","authors":["Shouzhen Gu","Lily Wang","Aleksander Kubica"],"reviews":0,"subject":"quant-ph","summary":"The decoding problem is a ubiquitous algorithmic task in fault-tolerant quantum computing, and solving it efficiently is essential for scalable quantum computing. Here, we prove that minimum-weight decoding is NP-hard in three quintessential settings: (i) the color code with Pauli $Z$ errors, (ii) the surface code with Pauli $X$, $Y$ and $Z$ errors, and (iii) the surface code with a transversal CNOT gate, Pauli $Z$ and measurement bit-flip errors. Our results show that computational intractability already arises in basic and practically relevant decoding problems central to both quantum…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-03-23","reactions":{}}