Minimum Weight Decoding in the Colour Code is NP-hard

• URL: http://arxiv.org/abs/2603.04234v1
• Date: Wed, 04 Mar 2026 16:18:18 GMT
• Title: Minimum Weight Decoding in the Colour Code is NP-hard
• Authors: Mark Walters, Mark L. Turner,
• Abstract summary: We show that exact decoding of the colour code is NP-hard -- that is, there does not exist an algorithm unless P=NP.<n>This highlights a notable contrast to some of the colour code's key competitors, such as the surface code.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Decoding 3D color codes with boundaries [0.9744114320491685]
  Three-dimensional (3D) color codes are a promising candidate for fault-tolerant quantum computation.<n>We extend previous decoders for two-dimensional color codes to three dimensions.<n>We present qCodePlot3D, a Python package for visualizing 2D and 3D color codes, error configurations, and decoding paths.
  arXiv  Detail & Related papers  (2025-12-15T15:30:54Z)
• Colour Codes Reach Surface Code Performance using Vibe Decoding [0.5242869847419834]
  Two-dimensional quantum colour codes hold significant promise for quantum error correction.<n>Despite their theoretical appeal, the practical deployment of these codes faces challenges.<n>This paper introduces vibe decoding which, for the first time, brings colour code performance on par with the surface code.
  arXiv  Detail & Related papers  (2025-08-21T17:38:42Z)
• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• Scaling and logic in the color code on a superconducting quantum processor [109.61104855764401]
  We present a demonstration of the color code on a superconducting processor, achieving logical error suppression and performing logical operations.<n>We inject magic states, a key resource for universal computation, achieving fidelities exceeding 99% with post-selection.<n>This work establishes the color code as a compelling research direction to realize fault-tolerant quantum computation on superconducting processors.
  arXiv  Detail & Related papers  (2024-12-18T19:00:05Z)
• Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
  Low-Density Parity-Check (LDPC) codes possess several advantages over other families of codes. The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
  arXiv  Detail & Related papers  (2024-06-09T12:08:56Z)
• Near-optimal decoding algorithm for color codes using Population Annealing [44.99833362998488]
  We implement a decoder that finds the recovery operation with the highest success probability. We study the decoder performance on a 4.8.8 color code lattice under different noise models.
  arXiv  Detail & Related papers  (2024-05-06T18:17:42Z)
• Facilitating Practical Fault-tolerant Quantum Computing Based on Color Codes [0.6963971634605797]
  In this work, we address several key issues to facilitate practical fault-tolerant quantum computing based on color codes. First, by introducing decoding graphs with error-rate-related weights, we obtained the threshold of $0.57%$ of the triangular color code. Second, our work firstly investigates the circuit-level decoding of color code lattice surgery, and gives an efficient decoding algorithm. Third, a new state injection protocol of the triangular color code is proposed, reducing the output magic state error rate in one round of 15 to 1 distillation by two orders of magnitude compared to a previous rough protocol.
  arXiv  Detail & Related papers  (2023-09-11T03:56:18Z)
• The domain wall color code [0.7224497621488285]
  We introduce the domain wall color code, a new variant of the quantum error-correcting color code. The code exhibits exceptionally high code-capacity error thresholds for qubits subject to biased noise.
  arXiv  Detail & Related papers  (2023-06-30T18:00:06Z)
• Decoding quantum color codes with MaxSAT [4.29377170477633]
  We propose a novel decoder for quantum color codes using a formulation as a MaxSAT problem based on the LightsOut puzzle. We show that the decoding performance of the proposed decoder achieves state-of-the-art decoding performance on color codes.
  arXiv  Detail & Related papers  (2023-03-24T19:00:02Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix. This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
  arXiv  Detail & Related papers  (2022-12-20T13:41:27Z)
• Morphing quantum codes [77.34726150561087]
  We morph the 15-qubit Reed-Muller code to obtain the smallest known stabilizer code with a fault-tolerant logical $T$ gate. We construct a family of hybrid color-toric codes by morphing the color code.
  arXiv  Detail & Related papers  (2021-12-02T17:43:00Z)
• Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders [77.34726150561087]
  We prove that the Restriction Decoder successfully corrects errors in the color code if and only if the corresponding toric code decoding succeeds. We numerically estimate the Restriction Decoder threshold for the color code in two and three dimensions against the bit-flip and phase-flip noise.
  arXiv  Detail & Related papers  (2019-05-17T17:41:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.