Computational complexity of Knot polynomials

Complexity: Knots, Colourings and Counting By D. J. A. Welsh

Has pretty extensive information.

The old (1990) paper, "On the computational complexity of the Jones and Tutte polynomials" (Cambridge link), shows that determining the Jones polynomial of alternating links is #P-hard, as the OP notes. Then, much later, the 2012 book Quantum Triangulations (eds.: Carfora, Marzuoli), says this (p.233):
 
See the Wikipedia entry on BPQ for a definition: essentially, solvable in polynomial time on a quantum computer, with bounded error probability. It is conjectured that BPQ $\supset$ P.

In the same book, there follows a section entitled "Efficient Quantum Processing of Colored Jones Polynomials," with several references.

(Added: All of this circa 2012 when originally posted.)