Quick Navigation

Overview Topics Abstract Importance Paper Tools References Reactions Discussion Publication Related

Topics

Quantum Error Correction Fault Tolerance

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

arXiv
Authors: Shouzhen Gu, Lily Wang, Aleksander Kubica

Year

2026

Paper ID

35849

Status

Preprint

Abstract Read

~2 min

Abstract Words

106

Citations

N/A

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.

Why This Paper Matters

  • This paper contributes to the Quantum Error Correction & Fault Tolerance research area in the Quantum Articles archive.
  • It adds a 2026 reference point for readers tracking recent quantum research.
  • The decoding problem is a ubiquitous algorithmic task in fault-tolerant quantum computing, and solving it efficiently is essential for scalable quantum computing.

Paper Tools

Become a member to use research tools

Sign in to open papers, visit source links, share, cite, compare, copy DOI links, request category corrections, and build your reading list.

Become a member Sign in
Show Paper arXiv Publisher Share Cite This Paper Copy URL Compare Copy DOI Add to Reading List Category Correction Request

References & Citation Signals

[1] DOI https://doi.org/arXiv:2603.22064 [2] arXiv https://arxiv.org/abs/2603.22064 [3] Publisher https://arxiv.org/abs/2603.22064

Local Citation Graph (Related-Paper Links)

Current Paper #35849 #68397 Optimizing Parallel Execution o...

External citation index: OpenAlex citation signal

Community Reactions

Quick sentiment from readers on this paper.

Score: 0
Likes: 0 Dislikes: 0

Sign in to react to this paper.

Discussion & Reviews (Moderated)

Average Rating: 0.0 / 5 (0 ratings)

No written reviews yet.