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.
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.
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.
Recent experimental advances have made it possible to implement logical multiqubit transversal gates on surface codes in a multitude of platforms. A transversal controlled- (t) gate on two surface codes introduces correlated errors across the code blocks and thus requires modified decoding compared to established methods of decoding surface-code quantum memory (SCQM) or lattice-surgery operations. In this work, we examine and benchmark the performance of three different decoding strategies for the t for scalable fault-tolerant quantum computation. In particular, we present a low-complexity decoder based on minimum-weight perfect matching (MWPM) that achieves the same threshold as the SCQM MWPM decoder. We extend our analysis with a study of tailored decoding of a transversal-teleportation circuit, along with a comparison between the performance of lattice-surgery and transversal operations under Pauli- and erasure-noise models. Our investigation builds toward systematic estimation of the cost of implementing large-scale quantum algorithms based on transversal gates in the surface code.
Recently we showed that minimum weight decoding in the (6.6.6 planar) colour code is NP-hard. However, it remained an open question as to whether it was possible to approximate the minimum weight decoding arbitrarily closely in polynomial time. In this paper we prove that it is possible: for any
ε>0 there is an polynomial time algorithm that, given a syndrome, can find an error-set generating that syndrome whose weight is at most
1+ε times the weight of the minimum weight decoding. As a consequence we see that, for any
ε>0, there is a polynomial time algorithm that can correct all errors of weight up to
(1−ε)d/2 in the distance
d colour code (so almost up to the theoretical
d/2 limit).
The polynomial we give is impractically large, but it does open the door for sensible polynomial time algorithms that approximate minimum weight decoding and, in particular, shows that approximate decoding is not NP-hard.
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.