All utility-scale quantum computers will require some form of Quantum Error Correction in which logical qubits are encoded in a larger number of physical qubits. One promising encoding is known as the colour code which has broad applicability across all qubit types and can decisively reduce the overhead of certain logical operations when compared to other two-dimensional topological codes such as the surface code. However, whereas the surface code decoding problem can be solved exactly in polynomial time by finding minimum weight matchings in a graph, prior to this work, it was not known whether exact and efficient colour code decoding was possible. Optimism in this area, stemming from the colour code's significant structure and well understood similarities to the surface code, fanned this uncertainty. In this paper we resolve this, proving that exact decoding of the colour code is NP-hard -- that is, there does not exist a polynomial time algorithm unless P=NP. This highlights a notable contrast to some of the colour code's key competitors, such as the surface code, and motivates continued work in the narrower space of heuristic and approximate algorithms for fast, accurate and scalable colour code decoding.
Color codes are an important family of topological quantum error-correcting codes, in part because they support a richer set of transversal logical gates than surface codes. Their practical use, however, requires efficient decoding. Minimum-weight decoding is natural under independent noise, but Walters and Turner recently proved that it is NP-hard for the two-dimensional color code. Subsequent independent work of Walters and of Gu, Wang, and Kubica gave polynomial-time approximation schemes; in terms of lattice size
N, their running times are
O(N2+528/ε) and
N(logN)O(1/ε), respectively, for a
(1+ε)-approximation. We ask whether stronger guarantees are possible for random instances generated by a natural iid noise model. For triangular color-code lattices with
N faces and iid face-error probability
p, we obtain near-linear-time algorithms throughout the noise range considered. If
p=o(1/log2N), we compute an exact minimum-weight correction in deterministic
N1+o(1) time with high probability. If
p=Ω(1/log2N), with
p bounded away from
1/2, we compute a
1+o(1)-approximation in deterministic
N1+o(1) time with high probability. When the syndrome is supplied sparsely and has size
s, the corresponding high-probability running times improve to
(1+s)No(1) and
s1+o(1), respectively. The algorithms exploit different random structure at different noise scales: localization into small exact subproblems in the sparse regime, peeling of locally unambiguous errors at intermediate densities, and a block decomposition whose additive loss is negligible relative to the typical optimum at larger densities. Together, these results give a near-linear average-case counterpart to recent worst-case hardness and approximation results for color-code decoding.
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.
Two-dimensional topological translationally invariant (2D TTI) stabilizer codes lie at the heart of fault-tolerant quantum computation, but using them requires solving the decoding problem. Minimum-weight decoding of these codes was recently shown to be NP-hard, even in basic settings, such as the color code with Pauli
Z errors and the toric code with Pauli
X,
Y and
Z errors. Here, we prove that minimum-weight decoding of 2D TTI codes nonetheless admits a polynomial-time approximation scheme (PTAS), i.e., for any constant
ε>0, a recovery operator of weight within a multiplicative factor of
1+ε of the minimum can be found in polynomial time. Our approach builds on Arora's PTAS for Euclidean problems, such as the traveling salesman problem, and applies when decoding can be cast in terms of point-like excitations connected by string-like errors. It therefore extends beyond two dimensions, covering certain higher-dimensional topological codes and quantum memories, including the toric code with phenomenological or circuit-level noise.
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.
Despite the NP hardness of acquiring minimum distance
dm for linear codes theoretically, in this paper we propose one experimental method of finding minimum-weight codewords, the weight of which is equal to
dm for LDPC codes. One existing syndrome decoding method, called serial belief propagation (BP) with ordered statistic decoding (OSD), is adapted to serve our purpose. We hold the conjecture that among many candidate error patterns in OSD reprocessing, modulo 2 addition of the lightest error pattern with one of the left error patterns may generate a light codeword. When the decoding syndrome changes to all-zero state, the lightest error pattern reduces to all-zero, the lightest non-zero error pattern is a valid codeword to update lightest codeword list. Given sufficient codewords sending, the survived lightest codewords are likely to be the target. Compared with existing techniques, our method demonstrates its efficiency in the simulation of several interested LDPC codes.