Quantum computing relies on error correction, but the setting turns out to be very different from classical error correction. Many of the most popular codes are topological in nature and the proofs and algorithms are entirely combinatorial. In this talk I will show that decoding one such code — the colour code — is NP-hard. This in stark contrast to some other codes, such as the surface code — where there are polynomial time algorithms. The talk will not assume nor use any knowledge of “quantum-ness”.

The problem for the surface code is the following:

Suppose you are given an even number of vertices S in the square lattice. Find the smallest number of edges such that the degree of every vertex in S is odd, but every other vertex has even degree.

This example easily reduces to a Minimum Weight Perfect Matching problem, which can be solved quickly using Edmonds Blossom Algorithm. The colour code problem is a very similar problem on the triangular lattice, but with hyperedges consisting of three vertices. In this case it was unknown whether the strong lattice structure would make the problem easy or the hyperedges would make it hard. We show that the latter is the case.

Joint work with Mark Turner (Riverlane)