Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2606.18035

Approximately Decoding the Colour Code

Mark Walters

quant-phSubmitted Jun 16, 2026• Announced Jun 17, 2026• 0 citations
arXivHTMLPDF

Abstract

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 $\varepsilon>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+\varepsilon$ times the weight of the minimum weight decoding. As a consequence we see that, for any $\varepsilon>0$, there is a polynomial time algorithm that can correct all errors of weight up to $(1-\varepsilon)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.

Related papers

Minimum Weight Decoding in the Colour Code is NP-hard

Mark Walters, Mark L. Turner

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.

quant-pharXiv:2603.04234•Mar 5, 2026•0 citations

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

Shouzhen Gu, Lily Wang, Aleksander Kubica

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.

quant-pharXiv:2603.22064•Mar 24, 2026•0 citations

Hardness of approximation for minimum-weight decoding of two-dimensional topological quantum codes

Louay Bazzi, Georges Khater

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\neq 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 $cN^{1/14}$ of the optimum, where $N$ is the number of qubits, unless $P=NP$. For the planar surface code, we obtain an $Ω(N^{1/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.

quant-pharXiv:2608.17109•Aug 19, 2026•0 citations

A polynomial-time approximation scheme for minimum-weight decoding of topological codes

Shouzhen Gu, Lily Wang, Aleksander Kubica

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 $\varepsilon>0$, a recovery operator of weight within a multiplicative factor of $1+\varepsilon$ 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.

quant-pharXiv:2606.18145•Jun 17, 2026•0 citations

Average-Case Minimum-Weight Decoding of Two-Dimensional Color Codes

Daniel Gibney, Jackson Huffstutler, Kaamil Kaka

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(N^{2+528/ε})\) and \(N(\log N)^{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/\log^2 N)\), we compute an exact minimum-weight correction in deterministic \(N^{1+o(1)}\) time with high probability. If \(p=Ω(1/\log^2 N)\), with \(p\) bounded away from \(1/2\), we compute a \(1+o(1)\)-approximation in deterministic \(N^{1+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)N^{o(1)}\) and \(s^{1+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.

arXiv:2606.10399•Jun 9, 2026•0 citations

Minimising surface-code failures using a color-code decoder

Asmae Benhemou, Kaavya Sahay, Lingling Lao +1 more

The development of practical, high-performance decoding algorithms reduces the resource cost of fault-tolerant quantum computing. Here we propose a decoder for the surface code that finds low-weight correction operators for errors produced by the depolarising noise model. The decoder is obtained by mapping the syndrome of the surface code onto that of the color code, thereby allowing us to adopt more sophisticated color-code decoding algorithms. Analytical arguments and exhaustive testing show that the resulting decoder can find a least-weight correction for all weight d/2 depolarising errors for even code distance d . This improves the logical error rate by an exponential factor O(2d/2) compared with decoders that treat bit-flip and dephasing errors separately. We demonstrate this improvement with analytical arguments and supporting numerical simulations at low error rates. Of independent interest, we also demonstrate an exponential improvement in logical error rate for our decoder used to correct independent and identically distributed bit-flip errors affecting the color code compared with more conventional color-code decoding algorithms.

arXiv:2306.16476•Quantum•Feb 17, 2025•2 citations
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\varepsilon>0ε>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+ε1+\varepsilon1+ε times the weight of the minimum weight decoding. As a consequence we see that, for any ε>0\varepsilon>0ε>0, there is a polynomial time algorithm that can correct all errors of weight up to (1−ε)d/2(1-\varepsilon)d/2(1−ε)d/2 in the distance ddd colour code (so almost up to the theoretical d/2d/2d/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.
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.
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 ZZZ errors, (ii) the surface code with Pauli XXX, YYY and ZZZ errors, and (iii) the surface code with a transversal CNOT gate, Pauli ZZZ 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.
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 XXX- and ZZZ-syndromes. For color codes under independent XXX- and ZZZ-error models, we consider Separate Minimum-Weight decoding. Assuming P≠NPP\neq NPP=NP, we establish polynomial additive inapproximability gaps for these problems. Specifically, for the toric code and the 4.8.84.8.84.8.8 color code on the torus, there exists a constant c>0c>0c>0 such that no polynomial-time algorithm can always produce a solution whose weight is within cN1/14cN^{1/14}cN1/14 of the optimum, where NNN is the number of qubits, unless P=NPP=NPP=NP. For the planar surface code, we obtain an Ω(N1/18)Ω(N^{1/18})Ω(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.
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 ZZZ errors and the toric code with Pauli XXX, YYY and ZZZ 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\varepsilon>0ε>0, a recovery operator of weight within a multiplicative factor of 1+ε1+\varepsilon1+ε 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.
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 NNN, their running times are O(N2+528/ε)O(N^{2+528/ε})O(N2+528/ε) and N(log⁡N)O(1/ε)N(\log N)^{O(1/ε)}N(logN)O(1/ε), respectively, for a (1+ε)(1+ε)(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 NNN faces and iid face-error probability ppp, we obtain near-linear-time algorithms throughout the noise range considered. If p=o(1/log⁡2N)p=o(1/\log^2 N)p=o(1/log2N), we compute an exact minimum-weight correction in deterministic N1+o(1)N^{1+o(1)}N1+o(1) time with high probability. If p=Ω(1/log⁡2N)p=Ω(1/\log^2 N)p=Ω(1/log2N), with ppp bounded away from 1/21/21/2, we compute a 1+o(1)1+o(1)1+o(1)-approximation in deterministic N1+o(1)N^{1+o(1)}N1+o(1) time with high probability. When the syndrome is supplied sparsely and has size sss, the corresponding high-probability running times improve to (1+s)No(1)(1+s)N^{o(1)}(1+s)No(1) and s1+o(1)s^{1+o(1)}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 development of practical, high-performance decoding algorithms reduces the resource cost of fault-tolerant quantum computing. Here we propose a decoder for the surface code that finds low-weight correction operators for errors produced by the depolarising noise model. The decoder is obtained by mapping the syndrome of the surface code onto that of the color code, thereby allowing us to adopt more sophisticated color-code decoding algorithms. Analytical arguments and exhaustive testing show that the resulting decoder can find a least-weight correction for all weight d/2 depolarising errors for even code distance d . This improves the logical error rate by an exponential factor O(2d/2) compared with decoders that treat bit-flip and dephasing errors separately. We demonstrate this improvement with analytical arguments and supporting numerical simulations at low error rates. Of independent interest, we also demonstrate an exponential improvement in logical error rate for our decoder used to correct independent and identically distributed bit-flip errors affecting the color code compared with more conventional color-code decoding algorithms.