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

Preprint · Shouzhen Gu, Lily Wang, Aleksander Kubica

- Archive id: arxiv:2603.22064
- Published: 2026-03-23
- arXiv: <https://arxiv.org/abs/2603.22064>
- Source URL: <https://arxiv.org/abs/2603.22064>
- PDF: <https://arxiv.org/pdf/2603.22064>
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._


---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.