Shouzhen Gu, Lily Wang, Aleksander Kubica (Mar 24 2026).
Abstract: 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 memories and logical circuit implementations, highlighting a sharp computational complexity separation between minimum-weight decoding and its approximate realizations.
