  A celebrated important result due to Freedman, Larsen and Wang states that
providing additive approximations of the Jones polynomial at the k'th root of
unity, for constant k=5 and k>6, is BQP-hard. Together with the algorithmic
results of Freedman et al and Aharonov et al, this gives perhaps the most
natural BQP-complete problem known today and motivates further study of the
topic. In this paper we focus on the universality proof; we extend the
universality result of Freedman et al to k's that grow polynomially with the
number of strands and crossings in the link, thus extending the BQP-hardness of
Jones polynomial approximations to all values for which the AJL algorithm
applies, proving that for all those values, the problems are BQP-complete. As a
side benefit, we derive a fairly elementary proof of the Freedman et al density
result, without referring to advanced results from Lie algebra representation
theory, making this important result accessible to computer science audience.
We make use of two general lemmas we prove, the Bridge lemma and the Decoupling
lemma, which provide tools for establishing density of subgroups in SU(n).
Those tools seem to be of independent interest in more general contexts of
proving quantum universality. Our result also implies a completely classical
statement, that the_multiplicative_ approximations of the Jones polynomial, at
exactly the same values, are #P-hard, via a recent result due to Kuperberg.
Since the first publication of those results in their preliminary form
(arXiv:quant-ph/0605181v2), the methods we present here were used in several
other contexts. This paper is an improved and extended version of the original
results, and also includes discussions of the developments since then.
