{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreifueht6jxl3krartihfxrwp2vh5ame44npiapd7bklwddmawb45se",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mhtyzvztfv62"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.22064v1",
  "publishedAt": "2026-03-24T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Shouzhen Gu",
    "Lily Wang",
    "Aleksander Kubica"
  ],
  "textContent": "**Authors:** Shouzhen Gu, Lily Wang, Aleksander Kubica\n\nThe 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.",
  "title": "The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding"
}