Abstract
Freedman, Kitaev, and Wang [arXiv:quant-ph/0001071], and later Aharonov, Jones, and
Landau [arXiv:quant-ph/0511096], 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 [arXiv:math/0103200] established that the
approximation is universal for quantum computation at a non-lattice, principal root of
unity; and Aharonov and Arad [arXiv:quant-ph/0605181] established a uniform version of this
result. In this article, we show that any value-dependent approximation of the Jones
polynomial at these non-lattice roots of unity is #P-hard. If given the power to decide
whether |V(L,t)| > a or |V(L,t)| < b for fixed constants a > b > 0, there is a
polynomial-time algorithm to exactly count the solutions to arbitrary combinatorial
equations. In our argument, the result follows fairly directly from the universality result
and Aaronson's theorem that PostBQP = PP [arXiv:quant-ph/0412187].
