Efficient decoding is essential for the practical realization of fault-tolerant quantum computers. We study the computational complexity of minimum-weight decoding for topological quantum codes. For surface codes under the depolarizing channel, we consider Minimum-Weight decoding, which seeks a minimum-weight Pauli error consistent with both the
X- and
Z-syndromes. For color codes under independent
X- and
Z-error models, we consider Separate Minimum-Weight decoding.
Assuming
P=NP, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the
4.8.8 color code on the torus, there exists a constant
c>0 such that no polynomial-time algorithm can always produce a solution whose weight is within
cN1/14 of the optimum, where
N is the number of qubits, unless
P=NP. For the planar surface code, we obtain an
Ω(N1/18) gap. Our inapproximability results use Håstad's hardness of approximation for MAX-3SAT.
Our reduction develops a general, modular framework for embedding logical constraints into coupled primal--dual join problems on a lattice. A key ingredient is a localization argument that controls unintended interactions between different parts of the construction.
After the NP-hardness of computational problems such as 3SAT and MaxCut was established, a natural next step was to explore whether these problems remain hard to approximate. While the quantum extensions of some of these problems are known to be hard-indeed undecidable-their inapproximability remains largely unresolved. In this work, we introduce definitions for the quantum extensions of Label-Cover and Unique-Label-Cover. We show that these problems play a similarly crucial role in studying the inapproximability of quantum constraint satisfaction problems as they do in the classical setting.