Theory of Computing
-------------------
Title : How Hard Is It to Approximate the Jones Polynomial?
Authors : Greg Kuperberg
Volume : 11
Number : 6
Pages : 183-219
URL : http://www.theoryofcomputing.org/articles/v011a006
Abstract
--------
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 whether $|V(L,t)| < a$ or $|V(L,t)| > b$ for fixed
constants $0 < a < b$, there is a polynomial-time algorithm to exactly
count the solutions to arbitrary combinatorial equations. Our result
is a mutual corollary of the universality of the Jones polynomial, and
Aaronson's theorem (2005) that PostBQP = PP.
Using similar methods, we find a range of values $T(G,x,y)$ of the
Tutte polynomial such that for any $c > 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.