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.
Freedman, Kitaev, and Wang (2002), and later Aharonov, Jones, and Landau (2009), established a quantum algorithm to "additively" approximate the Jones polynomial V(L;t) at any principal root of unity t. The strength of this additive approximation depends exponentially on the bridge number of the link presentation. Freedman, Larsen, and Wang (2002) established that the approximation is universal for quantum computation at a non- lattice, principal root of unity. We show that any value-distinguishing approximation of the Jones polynomial at these non-lattice roots of unity is #P-hard. Given the power to decide whetherjV(L;t)j b for fixed constants 0 1, T(G; x; y) is #P-hard to approximate within a factor of c even for planar graphs G. Along the way, we clarify and generalize both Aaronson's theorem and the Solovay- Kitaev theorem.