by Mark Walters and Mark Turner
For many Quantum Error Correction (QEC) codes, like the well-known surface code, there are efficient algorithms to find the most likely errors and correct them. But what about the colour code?
This elegant and powerful QEC code has received attention over the years for its unique advantages. Our new arXiv paper Minimum Weight Decoding in the Colour Code is NP-hard delivers a fundamental answer: finding the most likely physical error pattern in a colour code is an NP-hard problem.
What does NP-hard mean in plain English? Informally, it means that, for large enough colour codes, there's no algorithm that can always find the single best way to correct errors in a reasonable (polynomial) amount of time - unless some widespread beliefs in computational computer science collapse. In other words, exact decoding of colour codes is computationally intractable.
This isn't a dead end, but a strong indication of where future research must go. It motivates continued work in the narrower space of heuristic and approximate algorithms for fast, accurate, and scalable colour code decoding.
Why consider colour codes at all?
So, if they're probably hard to decode, why do people care about colour codes? The answer lies in their incredible promise for quantum computing:
- Excellent logical operations: Colour codes offer a much richer set of logical operations compared to surface codes. For example, crucial operations like S and Hadamard gates, which can be very expensive (requiring many time-consuming rounds of syndrome extraction) for surface codes, are transversal in colour codes. This means they can be implemented with much lower time overheads, a critical factor for building large-scale quantum computers.
- Versatile applications: Colour codes are particularly useful for "state preparation." State preparation is the process of initialising a quantum system into a desired quantum state before you perform further operations or measurements. State preparation is vital for all quantum algorithms, across all qubit types.
- Real-world success: We've seen exceptional demos of the colour code by the likes of Harvard (Nature 649, 2026) Google (Nature 638, 2025) QuEra (Nature 645, 2025) and Quantinuum (PRX 11, 2021), showcasing their practical viability on superconducting qubit architectures. In other words, this isn't just theory; it's being explored in leading labs worldwide.
Our work extends our understanding of these codes, giving us a clearer picture of their inherent computational challenges.
How did we prove this result? Well, this wasn't just a quantum physics problem; it quickly became a fascinating mathematical question. This highlights a crucial point: Decoders are classical algorithms. Therefore, the computational bottlenecks in quantum computing often stem from classical processing. In other words, you don’t need to be a quantum expert to bring valuable expertise to the field of quantum computing – and solve some of its pivotal problems.
Efficiently decoding colour codes has been a major challenge. While surface codes have an elegant solution (Minimum Weight Perfect Matching), colour codes don't readily fit into the “graph problem" framework, making them more complex than codes like the surface code. Prior to our work, it was unknown whether this 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. We have shown this is not possible.
Our approach was rooted in a common technique in complexity theory: reduction. We embedded a well-known hard computational problem, 3-SAT (a Boolean satisfiability problem), into a colour code decoding problem.
To do this, we designed "gadgets" – specific patterns of errors and defects within the colour code's structure. Here, "variable gadgets" represent the TRUE/FALSE states of variables in a 3-SAT problem, "clause gadgets" enforce its logical rules, and "wire gadgets" connect them. These intricate patterns encoded the 3-SAT problem directly into the colour code's error syndromes.
We then rigorously proved that if you could find the exact minimum weight decodings for our specially constructed colour code syndromes in polynomial time, you could, in turn, efficiently solve any 3-SAT problem. Since 3-SAT is known to be NP-complete, this means that minimum weight decoding for colour codes is also NP-hard.
The result is clear: exact decoding is impossible for colour codes in polynomial time (unless P=NP).
What's next?
The result is timely since quantum computing is evolving rapidly, with real hardware demonstrating the potential of QEC codes like the colour code. As these devices grow larger and more complex, understanding the fundamental qualities of their error correction becomes paramount.
While surface codes are still a leading candidate due to their well-understood and efficient decoding, colour codes offer superior transversal gates that could dramatically simplify certain quantum operations. This means finding effective decoders for them is highly desirable.
Our paper validates the current focus in the colour code literature on heuristic and approximate decoders. It shifts the question from that of finding an exact algorithm to optimising the trade-offs – how close can approximate decoders get to the optimal correction while maintaining speed and efficiency? And that, in itself, is another fascinating challenge.
You can read the full paper on arXiv here.