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.10399

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

Daniel Gibney, Jackson Huffstutler, Kaamil Kaka

Published Jun 9, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2606.10399

Related papers

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

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

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

Approximately Decoding the Colour Code

Mark Walters

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.

quant-pharXiv:2606.18035•Jun 17, 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

Rescaling decoder for two-dimensional topological quantum color codes on 4.8.8 lattices

Pedro Parrado-Rodríguez, Manuel Rispler, Markus Müller

Fault-tolerant quantum computation relies on scaling up quantum error correcting codes in order to suppress the error rate on the encoded quantum states. Topological codes, such as the surface code or color codes, are leading candidates for practical scalable quantum error correction and require efficient and scalable decoders. In this work, we propose and study the efficiency of a decoder for two-dimensional topological color codes on the 4.8.8 lattice (also known as the square-octagon code), by building on the work of Sarvepalli and Raussendorf [Phys. Rev. A 85, 022317 (2012)], for color codes on hexagonal lattices. The decoder is based on a rescaling approach, in which syndrome information on a part of the qubit lattice is processed locally, and then the lattice is rescaled iteratively to smaller sizes. We find a threshold of 6.0% for code capacity noise.

arXiv:2112.09584•Physical Review A•Sep 26, 2022•5 citations
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.
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.
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.
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.
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.
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.
Fault-tolerant quantum computation relies on scaling up quantum error correcting codes in order to suppress the error rate on the encoded quantum states. Topological codes, such as the surface code or color codes, are leading candidates for practical scalable quantum error correction and require efficient and scalable decoders. In this work, we propose and study the efficiency of a decoder for two-dimensional topological color codes on the 4.8.8 lattice (also known as the square-octagon code), by building on the work of Sarvepalli and Raussendorf [Phys. Rev. A 85, 022317 (2012)], for color codes on hexagonal lattices. The decoder is based on a rescaling approach, in which syndrome information on a part of the qubit lattice is processed locally, and then the lattice is rescaled iteratively to smaller sizes. We find a threshold of 6.0% for code capacity noise.