Volume 11 (2015) Article 6 pp. 183-219

How Hard Is It to Approximate the Jones Polynomial?

by Greg Kuperberg

Received: August 5, 2009
Revised: October 27, 2014
Published: June 6, 2015

$ \newcommand{\PP}{\mathsf{PP}} \newcommand{\PostBQP}{\mathsf{PostBQP}} \newcommand{\shP}{\mathsf{\#P}} $

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.

DOI: 10.4086/toc.2015.v011a006

© 2015 Greg Kuperberg
Licensed under a Creative Commons Attribution License (CC-BY)