Citation: Kuperberg, Greg, and Eric Samperton. "Coloring invariants of knots and links are often intractable." Algebraic & Geometric Topology 21.3 (2021): 1479-1510.
Web: https://arxiv.org/abs/1907.05981
Tags: Mathematical
This paper proves a lovely computational hardness result in quantum topology. This goes as follows. Let K be a knot, let G be a group, and let C be a conjugacy class in K. We can consider coloring the arks of a projection of K by elements of the conjugacy class C. We call such a coloring of arks admissable if at every crossing the standard relation for ordered media (g,h)-> (ghg^-1,h) holds. The number of admissable colorings is an invariant of K, independent of the choice of projection.
This paper then proves that the problem of computing the number of admissable colorings (or, more precisely, the number of admissible colorings for which every element of the conjugacy class is used in the coloring) is #P-complete whenever the group G is a non-abelian simple group. This is a fantastic classical analogue of Mochon's theorem in topological quantum computing, which shows that topological quantum computing with G non-abelian simple is BQP complete.
Not only is the main result of this paper fantastic, but it is also a treasure trove of results about the braid group representations associated to non-simple groups. There are a lot of important statements and useful lemmas proved along the way. This is certainly one of the most important references to be aware of for anyone interested in topological classical computing.