The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
This work addresses a fundamental algorithmic challenge for scalable quantum computing, showing that exact decoding is computationally hard, which is incremental as it builds on known complexity theory but applies to specific quantum codes.
The paper tackles the decoding problem in fault-tolerant quantum computing by proving that minimum-weight decoding is NP-hard in three key settings: the color code with Pauli Z errors, the surface code with Pauli X, Y, and Z errors, and the surface code with a transversal CNOT gate and errors. This result demonstrates computational intractability in basic and practical decoding scenarios.
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.