  The Jones polynomial, discovered in 1984, is an important knot invariant in
topology. Among its many connections to various mathematical and physical
areas, it is known (due to Witten) to be intimately connected to Topological
Quantum Field Theory (TQFT). The works of Freedman, Kitaev, Larsen and Wang
provide an efficient simulation of TQFT by a quantum computer, and vice versa.
These results implicitly imply the existence of an efficient quantum algorithm
that provides a certain additive approximation of the Jones polynomial at the
fifth root of unity, e^{2\pi i/5}, and moreover, that this problem is
BQP-complete. Unfortunately, this important algorithm was never explicitly
formulated. Moreover, the results mentioned are heavily based on TQFT, which
makes the algorithm essentially inaccessible to computer scientists.
  We provide an explicit and simple polynomial quantum algorithm to approximate
the Jones polynomial of an n-strands braid with m crossings at any primitive
root of unity e^{2\pi i/k}, where the running time of the algorithm is
polynomial in m,n and k. Our algorithm is based, rather than on TQFT, on well
known mathematical results. By the results of Freedman et. al., our algorithm
solves a BQP complete problem.
  The algorithm we provide exhibits a structure which we hope is generalizable
to other quantum algorithmic problems. Candidates of particular interest are
the approximations of other #P-hard problems, most notably, the partition
function of the Potts model, a model which is known to be tightly connected to
the Jones polynomial.
