The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding

Shouzhen Gu, Lily Wang, Aleksander Kubica

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 th…