How hard is it to approximate the Jones polynomial?
by
Greg Kuperberg
UC Davis

Jaeger, Vertigan, and Welsh showed that the Jones polynomial and many related invariants are #P-hard to compute exactly at almost all of its values. This means that computing the Jones polynomial of a link diagram is as difficult, up to polynomial-sized conversions of input, as counting the solutions to any set of combinatorial equations. But partial information about the Jones polynomial may not be difficult to compute; for instance its derivatives at q=1 are all finite-type invariants and each can be computed in deterministic polynomial time. Freedman, Larsen, and Wang, and later Aharonov, Jones, and Landau showed that polynomial-time quantum computation is equivalent to approximating the Jones polynomial at a non-lattice principal root of unity, with a certain description-dependent error. If the Jones polynomial were directly used to distinguish large knots, it would have to be computed with only value-dependent error. Our new result is that the same equivalence shows that value-dependent approximation of the Jones polynomial is #P-hard. At least for these roots of unity, this is a new proof of the Jaeger-Vertigan-Welsh theorem, with a stronger conclusion.

Date received: May 22, 2009