We show the problem of counting homomorphisms from the fundamental group of a homology @math -sphere @math to a finite, non-abelian simple group @math is #P-complete, in the case that @math is fixed and @math is the computational input. Similarly, deciding if there is a non-trivial homomorphism is NP-complete. In both reductions, we can guarantee that every non-trivial homomorphism is a surjection. As a corollary, for any fixed integer @math , it is NP-complete to decide whether @math admits a connected @math -sheeted covering. Our construction is inspired by universality results in topological quantum computation. Given a classical reversible circuit @math , we construct @math so that evaluations of @math with certain initialization and finalization conditions correspond to homomorphisms @math . An intermediate state of @math likewise corresponds to a homomorphism @math , where @math is a pointed Heegaard surface of @math of genus @math . We analyze the action on these homomorphisms by the pointed mapping class group @math and its Torelli subgroup @math . By results of Dunfield-Thurston, the action of @math is as large as possible when @math is sufficiently large; we can pass to the Torelli group using the congruence subgroup property of @math . Our results can be interpreted as a sharp classical universality property of an associated combinatorial @math -dimensional TQFT.
For a 3-manifold with triangulated boundary, the Turaev–Viro topological invariant can be interpreted as a quantum error-correcting code. The code has local stabilizers, identified by Levin and Wen, on a qudit lattice. Kitaev’s toric code arises as a special case. The toric code corresponds to an abelian anyon model, and therefore requires out-of-code operations to obtain universal quantum computation. In contrast, for many categories, such as the Fibonacci category, the Turaev–Viro code realizes a non-abelian anyon model. A universal set of fault-tolerant operations can be implemented by deforming the code with local gates, in order to implement anyon braiding. We identify the anyons in the code space, and present schemes for initialization, computation and measurement. This provides a family of constructions for fault-tolerant quantum computation that are closely related to topological quantum computation, but for which the fault tolerance is implemented in software rather than coming from a physical medium. We show that the topological modular functor from Witten-Chern-Simons theory is universal for quantum computation in the sense that a quantum circuit com- putation can be efficiently approximated by an intertwining action of a braid on the functor's state space. A computational model based on Chern-Simons theory at a fifth root of unity is defined and shown to be polynomially equivalent to the quantum circuit model. The chief technical advance: the density of the irreducible sectors of the Jones representation has topological implications which will be considered elsewhere.