{"id":"arxiv/2603.04234","url":"https://arxiv.org/abs/2603.04234","tags":["quant-ph"],"score":0,"title":"Minimum Weight Decoding in the Colour Code is NP-hard","domain":"quant-ph","source":"arxiv","authors":["Mark Walters","Mark L. Turner"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-03-04","reactions":{}}