The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866918403774611456 |
|---|---|
| author | Gu, Shouzhen Wang, Lily Kubica, Aleksander |
| author_facet | Gu, Shouzhen Wang, Lily Kubica, Aleksander |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22064 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding Gu, Shouzhen Wang, Lily Kubica, Aleksander Quantum Physics Computational Complexity 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. |
| title | The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding |
| topic | Quantum Physics Computational Complexity |
| url | https://arxiv.org/abs/2603.22064 |