Volume 11 (2015) Article 6 pp. 183-219
How Hard Is It to Approximate the Jones Polynomial?
Revised: October 27, 2014
Published: June 6, 2015
[PDF (380K)]    [PS (1583K)]    [PS.GZ (410K)]
[Source ZIP]
Keywords: hardness, quantum computation, Jones polynomial, Tutte polynomial
ACM Classification: F.1.3, G.2.2
AMS Classification: 68Q17, 68Q12, 57M27, 05C31

Abstract: [Plain Text Version]


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 $\shP$-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 $\shP$-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.