Plaintext
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219
www.theoryofcomputing.org
How Hard Is It to
Approximate the Jones Polynomial?
Greg Kuperberg∗
Received August 5, 2009; Revised October 27, 2014; Published June 6, 2015
Dedicated to the memory of François Jaeger (1947-1997)
Abstract: 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 #P-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 #P-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.
ACM Classification: F.1.3, G.2.2
AMS Classification: 68Q17, 68Q12, 57M27, 05C31
Key words and phrases: hardness, quantum computation, Jones polynomial, Tutte polynomial
∗ Partly supported by NSF grants DMS-0606795 and CCF-1013079.
© 2015 Greg Kuperberg
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2015.v011a006
G REG K UPERBERG
1 Introduction
A well-known paper of Aharonov, Jones, and Landau [5] establishes a polynomial quantum algorithm to
approximate the Jones polynomial at any principal root of unity; a more abstract form of this algorithm
appeared previously in a paper of Freedman, Kitaev, and Wang [11].
Theorem 1.1 (Freedman, Kitaev, Wang [11]; Aharonov, Jones, Landau [5]). Let t = exp(2πi/r) be a
principal root of unity, let L be a link presented by a plat diagram with bridge number g, and let V (L,t)
be its Jones polynomial. Then there is a polynomial-time quantum decision algorithm that answers yes
with probability
2
V (L,t)
P[yes] = 1/2 −1/2 g−1 .
(t + t )
(See Burde and Zieschang [9, §2.D] or Section 3.4 for the definition of a plat diagram and its bridge
number.)
In the version of the result of Aharonov et al., the algorithm is jointly polynomial time in the r, the
order of the root of unity; as well as in the bridge number and the crossing number. They also refine the
algorithm to estimate V (L,t) as a complex number rather than just estimating its length. Aharonov et
al. describe the error in this algorithm as additive, and note that it would be much harder to provide an
algorithm with multiplicative error. Multiplicative approximation (in the sense of the complexity class
APX [40]) would mean that V (L,t) or |V (L,t)| can be approximated to within some constant factor c > 1.
Another way to distinguish between types of error is to say that the approximation in Theorem 1.1
is input-dependent. Given different plat diagrams of the same link L, the error grows exponentially in
one of the parameters of the presentation, namely the bridge number. (This additive, input-dependent
model of approximating the Jones polynomial was first considered in the converse problem of simulating
a quantum computer with the Jones polynomial [7].) An algorithm to approximate the Jones polynomial
is only directly useful for topology if the approximation is value-distinguishing; i. e., if there is an error
bound which is independent of quantities other than the value of |V (L,t)|. Multiplicative approximation
is one type of value-distinguishing approximation, but it is not the most general kind. For instance, a
multiplicative approximation of log(1 + |V (L,t)|) is much weaker than a multiplicative approximation
of |V (L,t)| itself, but it is still a value-distinguishing approximation. In general, if an algorithm yield
any value-distinguishing approximation of a real-valued function f (x), it means that for each c ∈ R,
there exist real numbers a < c < b such that f (x) < a can be distinguished from f (x) > b. (See also
Section 2.2.)
Freedman, Larsen, and Wang [13] established that the approximated quantity
g−1 2
V (L,t)/ t 1/2 + t −1/2
in Theorem 1.1 is universal for quantum computation when r = 5 or r ≥ 7. Aharonov and Arad [3]
establish an r-uniform version of this result. The exceptions, among principal roots of unity, are
t = exp(2πi/r) with r ∈ {1, 2, 3, 4, 6}. We call these lattice roots of unity, because they are the roots of
unity for which the ring Z[t] is a discrete subset of C; the other values of r are non-lattice roots of unity.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 184
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
These results show that even if the approximation is input-dependent, it is computationally valuable for
carefully chosen link diagrams.
On the discouraging side, Vertigan [36] showed that it is #P-hard to exactly compute the Jones
polynomial V (L,t) except when t is a lattice root of unity. Jaeger, Vertigan, and Welsh [20] established
a reduction from the Tutte polynomial of a planar graph to the Jones polynomial of an associated link.
Vertigan then showed that the specific values of the Tutte polynomial used in this reduction are #P-hard.
The main result of this article is that the “encouraging” universality result strengthens the “discourag-
ing” hardness result: Any value-distinguishing approximation of a value of the Jones polynomial at a
non-lattice root of unity is #P-hard. The argument is a mash-up of three standard theorems in quantum
computation: The Solovay-Kitaev theorem [30], the FLW density theorem, and Aaronson’s theorem that
PostBQP = PP [1]. (See also [7] for a different hardness result.)
Theorem 1.2. Let V (L,t) be the Jones polynomial of a link L described by a link diagram, and let t be a
principal, non-lattice root of unity. Let 0 < a < b be two positive real numbers, and assume as a promise
that either |V (L,t)| < a or |V (L,t)| > b. Then it is #P-hard, in the sense of Cook-Turing reduction, to
decide which inequality holds. Moreover, it is still #P-hard when L is a knot.
Theorem 1.2 is proven in Section 3.5 after developing several lemmas. The theorem is stated for
the Jones polynomial and only for values where the associated braid group representations are unitary
and dense. But the idea applies to many other link invariants and to many non-unitary values of the
Jones polynomial. The idea also applies to various functions on graphs or other input data that aren’t
link invariants. We have no formal statement of a general result, but the basic argument is that if a
numerical function can model the execution of a quantum computer sufficiently accurately, then typically
multiplicative or value-distinguishing approximation is universal for PostBQP and therefore #P-hard.
Here is an example result of this type.
Theorem 1.3. Let c > 1 and let x and y be two real numbers such that q = (x − 1)(y − 1) > 4 and
x, y < 0, and x and y each have an FPTEAS approximation. Then it is #P-hard to approximate the Tutte
polynomial value T (G, x, y) for planar graphs G to within a factor of c.
Here, a real or complex number has an FPTEAS (fully polynomial-time exponential approximation
scheme) if its digits can be computed in FP, for instance if it is an algebraic number (Section 2.2).
One interesting ingredient is that we need the Solovay-Kitaev theorem for non-compact Lie groups,
Theorem 2.4. (Aharonov, Arad, Eban, and Landau [4] obtained this result for the Lie groups SL(d, R)
and SL(d, C), which is actually enough for Theorem 1.3.)
We will complete prove Theorem 1.3 in Section 4.5, again after developing some lemmas.
In related results, Aharonov, Arad, Eban, and Landau [4] obtained BQP-universality results about
additive approximation to the Tutte polynomial for planar graphs that are clearly related to Theorem 1.3.
In particular, as with us, their approach involves a study of non-unitary linear gates. However, their
derivation concerns multivariate Tutte polynomials, in which different edges of a graph are allowed
different parameters. The value of q must be the same everywhere, but in their version the choice of x
(say) is taken from a finite list that satisfies technical conditions. Following Goldberg and Jerrum, we
restrict to a single pair of values (x, y).
Goldberg and Jerrum [15] showed that multiplicative approximation of many values of the Tutte
polynomial T (G, x, y) is NP-hard (where the reductions are in RP) for non-planar graphs, while some
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 185
G REG K UPERBERG
values (those with q = 4 and −1 < y < 0) are #P-hard. Jaeger, Vertigan, and Welsh [20] also analyzed
when T (G, x, y) is #P-hard to compute exactly. They noted that the Jones polynomial V (L,t) of an alter-
nating link L is equivalent to T (G, x, y) for a planar graph G along the curve xy = 1. More recently [16],
Goldberg and Jerrum also established that many values of the planar Tutte polynomial are NP-hard to
approximate. Their new theorems apply to those values of (x, y) in Theorem 1.3 with q > 5 (and some
other values that we do not analyze), but their constructions are very different. Moreover, we establish
#P-hardness, while their planar constructions only establish NP-hardness. On the other hand, we use
Goldberg and Jerrum’s gadget idea to change from one value of (x, y) to another for a fixed value of q.
Remark 1.4. The first version of this article contained a significant mistake, which the reader may
grasp after reading Section 2.5. The author supposed that all of the implementations of quantum gates
could have complexity poly(1/ε) (or FPTAS approximability) in the proof of both Theorem 1.2 and
Theorem 1.3, because this complexity is sufficient to express the complexity class BQP. We actually
need complexity poly(− log(ε)) (or FPTEAS) to express the complexity class PostBQP, because this
class unavoidably needs exponentially small probabilities. Fortunately, the Solovay-Kitaev theorem
(Theorem 2.4) satisfies this stringent approximation requirement. See also Lemma 4.3 and Theorem 2.10
for our corrected constructions.
Acknowledgments
The author would like to thank Scott Aaronson, Dorit Aharonov, Leslie Ann Goldberg, and Eric Rowell
for helpful discussions. The author would also like to thank the referees for their meticulous remarks.
2 Complexity theory
2.1 Complexity classes
We assume that the reader is somewhat familiar with complexity classes such as P, NP, BQP, #P, and
the notation that AB means the class A with oracle B. See the Complexity Zoo [40] and Nielsen and
Chuang [30] for a review.
Whereas a problem in the class #P counts the number of witnesses accepted by a verifier in polynomial
time, and a problem the class NP reports whether there is an accepted witness, a problem in the class PP
reports whether a majority of the witnesses are accepted.
Proposition 2.1. A problem is #P-hard if and only if it is PP-hard with respect to Cook-Turing reduction,
i. e.,
PPP = P#P .
Proposition 2.1 is given as an exercise for the reader in the Complexity Zoo [40]. (Hint: Binary
search.) It is one reason that we use Cook-Turing reduction in the statement of Theorem 1.2.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 186
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
A problem which is #P-hard is also hard for the polynomial hierarchy PH, by the deeper theorem due
to Toda [34] that
∞ NP
..
def [ NP . #P
PH = NP
| {z }⊆P .
n=1 n
The class NP with a tower of n − 1 NPs as an oracle is called the nth level of the polynomial hierarchy.
One of the standard conjectures in complexity theory is the polynomial hierarchy does not collapse, i. e.,
that nth level does not equal the n + 1st level for any n. Thus by Toda’s theorem, if a problem is #P-hard,
then it is viewed as qualitatively harder than if it is merely NP-hard.
2.2 Approximation classes
The approximation classes listed in the Complexity Zoo [40] that express multiplicative approximation
include APX, PTAS, and FPTAS. These classes are defined there for optimization problems, but they
can equally well be defined for arbitrary functional problems. Let f : Σ∗ → R+ be a function that takes
bit strings x to positive real numbers. Then f (x) is in APX if it can be approximated to within some
bounded factor in polynomial time (with fixed-point output); it is in PTAS if it can be approximated to
within a factor 1 + ε in polynomial time for any ε > 0; and it is in FPTAS if the computation is jointly
polynomial time in the bit length |x| and 1/ε. (These classes all refer to deterministic computation; there
are analogous randomized classes such as FPRAS.)
We will need a stricter version of FPTAS. For many approximate numerical algorithms, although not
usually for optimization problems, the computation time is jointly polynomial in |x| and − log(ε). We
call such an approximation scheme an FPTEAS, or fully polynomial time, exponential approximation
scheme. In particular every algebraic number has an FPTEAS, using standard numerical algorithms to
find its digits.
Indeed, much more is true: The digits of algebraic numbers, and the values of many other elementary
functions such as exponentials and logarithms, can be computed in quasilinear time in the RAM machine
model [8]. Most numbers that arise in calculus derivations have quasilinear digit complexity; nearly all of
them have polynomial digit complexity.
We do not know of a standard complexity class to express general value-distinguishing approximation,
so we define such a class here, APV. Again let f : Σ∗ → R+ . Then f is in APV if for every constant a > 0,
there exists a constant b > a and a polynomial-time algorithm to decide whether f (x) > b or f (x) < a,
given the promise that one of the two is true. Similarly, we could define a randomized version ARV.
Also, both APV and ARV have a variation in which the constant a is an input to one universal algorithm,
instead of asking for an algorithm for each value of a.
The following proposition says that if f (x) can be suitably rescaled, then general value-distinguishing
approximation becomes equivalent to multiplicative approximation in the sense of APX. Proposition 2.2
and its proof are similar to that of Proposition 2.14, in particular similar to the rescaling of Aaronson [1,
Thm 3.4]. We will need the contrapositive of Proposition 2.2 in the proof of Theorem 1.2.
Proposition 2.2. Suppose that f (x) takes positive real values and is in APV, and suppose further that
| log( f (x))| is bounded by a polynomial in the bit length |x| of the input. Suppose that there are constants
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 187
G REG K UPERBERG
c > 1 and k > 1 such that for every integer n, there is a reduction yn (x) such that
f (x) < kn f (yn (x)) < c f (x) ,
and suppose that this reduction can be computed in joint polynomial time in n and in |x|. Then f (x) is in
APX.
Proof. Let a and b be some constants such that we can decide by a subroutine whether f (x) < a or
f (x) > b in polynomial time. Then we can bound f (x) to within a factor of cb/a. We know by hypothesis
that f (x) > k−m and f (x) < km for some m which is polynomial in |x|. So the strategy is to ask whether
f (yn (x)) is less than a or more than b for every |n| ≤ m. The largest n for which the subroutine reports
that f (yn (x)) < a yields a good estimate of ak−n . The estimate is within a factor of cb/a, even though
the subroutine could give a false yes answer when f (yn (x)) > b.
2.3 Quantum computation
We cannot give a full review of quantum computation in this article. There are many equivalent models
of quantum computation, and we would simply like to carefully describe the one that we will use. Let
D : Σ∗ → {yes, no} be a decision problem, a function D(x) on bit strings x that takes the values “yes” and
“no.” In the most standard definition of BQP, we assume a uniform family of quantum circuits C such
that x is supplied in input qubits along with ancillas, and one of the output qubits is the output D(x) with
good probability. We will use a variation of this definition in which the input is encoded in the circuit
rather than in the input to its gates; and the inputs and outputs are all set to 0.
Proposition 2.3. D ∈ BQP if and only if there is a quantum circuit C = C(x) with poly(|x|) unitary gates
acting on n = poly(|x|) qubits, such that C itself can be generated in deterministic polynomial time FP,
and such that the probability
p(x) = |h0n |C|0n i|2 (2.1)
is at least 2/3 if D(x) = yes and at most 1/3 if D(x) is no.
Proposition 2.3 is a well-known result even though it is not the most standard definition. The proof
uses the “uncomputation” method.
Proof. We first assume a circuit C = C(n) of the more standard type in which |xi is the input along with
|0i ancillas, and one of the qubits is the output. Then we can make a new circuit C0 whose input is all
ancillas, and that first changes some of the ancillas to |xi. One of the outputs |yi of C0 agrees with D(x)
with probability at least 2/3; the other outputs are unpredictable. We make a new circuit C00 that applies
C0 , then copies |yi to a fresh ancilla with a CNOT gate, and then applies (C0 )−1 .
2.4 Solovay-Kitaev
In this section we will analyze a central result in quantum computation, the Solovay-Kitaev theorem.
Let BQPΓ be the class BQP defined by some universal finite gate set Γ. If each gate in Γ has at least
an FPTAS, then the Solovay-Kitaev theorem implies that BQPΓ does not depend on the choice of Γ
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 188
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
and can be called BQP. We need some approximability condition here: If the matrix entries of gates in
Γ have intractable or uncomputable information, then BQPΓ also carries intractable or uncomputable
information [2, Thm. 5.1].
In this paper we will need the more delicate class PostBQP. As stated in Theorem 2.10, in order to
know that PostBQPΓ is independent of Γ, we need to assume that every gate in Γ has an FPTEAS, and
not just an FPTAS. One special case which is widely used in quantum computation and which we need
for Theorem 1.2 is gates with algebraic entries; happily, all algebraic gates have an FPTEAS. (Indeed
the FPTEAS class is far more general, as explained in Section 2.2.) We also need the Solovay-Kitaev
theorem to have polylogarithmic overhead; happily it does.
Finally, for Theorem 1.3 we will need the Solovay-Kitaev theorem for non-compact Lie groups. The
theorem was originally proven in the case G = SU(d). This case is explained in Nielsen and Chuang [30];
as far as we know the proof works without change when G is any compact, semisimple Lie group.
Aharonov, Arad, Eban, and Landau [4] derive a version of this theorem for the Lie groups SL(d, R) and
SL(d, C), which are not compact but still semisimple. Their result is enough for Theorem 1.3; here we
show that the traditional argument applies to a more general class of Lie groups.
Theorem 2.4 (Solovay, Kitaev). Let G be a connected Lie group whose Lie algebra g is perfect. Let
Γ be a finite set of elements (closed under taking inverses) that densely generates G, and let g ∈ G.
Suppose that there is an FPTEAS for g and every element of Γ. Then there is a word made from Γ that
approximates g,
d(g1 g2 . . . gm , g) ≤ ε ,
where the length m and the (deterministic) computation time to find the word are both poly(− log(ε))
(non-uniformly in the choice of G, Γ, and g).
Before turning to the proof of Theorem 2.4, we discuss some basics of Lie theory. (See Varadara-
jan [35].)
A Lie group G is a real analytic manifold with a real analytic group law. (Or a smooth manifold or
even just a topological manifold; it turns out that the group law induces a unique real analytic structure.)
Its Lie algebra g = T1 G is by definition the tangent space at the identity. We assume that our Lie group
G is given with some tractable algorithm for computing the group law in real analytic coordinates. For
example, G could be a real algebraic group, by definition a Lie group that can be realized (non-uniquely)
by polynomial equations in some GL(n, R).
We can give G a metric to discuss approximation to points in G. The most natural choice is a
left-invariant Riemannian metric [31]. Every left-invariant Riemannian metric comes from a positive
definite inner product on the Lie algebra g of G. Two different inner products on g plainly yield different
Riemannian metrics on G, but they are they are bi-Lipschitz equivalent. (If d1 and d2 are two metrics on a
set, then they are bi-Lipschitz equivalent if d1 (p, q) = Θ(d2 (p, q)).) A left-invariant metric on GL(n, R) is
not bi-Lipschitz equivalent with Euclidean distance between matrices, but it is equivalent on any bounded
set. Thus, any of these choices of metric are equivalent for the purpose of stating Theorem 2.4.
The usual way to understand the structure of a Lie group G is to begin with its Lie algebra g. A
finite-dimensional Lie algebra g is semisimple if it is a direct sum of non-abelian, simple Lie algebras. It
is perfect if g = [g, g], i. e., g is the linear span of all Lie brackets of pairs of its elements. (A semisimple
Lie algebra is analogous to a direct product of non-abelian, finite simple groups; a perfect Lie algebra is
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 189
G REG K UPERBERG
analogous to a finite perfect group.) The most commonly used Lie algebras, such as su(d) and sl(n, R),
have simple and therefore semisimiple Lie algebras (and are themselves called semisimple groups). Every
semisimple Lie algebra is perfect, but there are perfect Lie algebras that are not semisimple. For example,
if V is a linear representation of a semisimple Lie group G without any trivial summand, then the Lie
algebra of the semidirect product G nV is perfect.
Every Lie group G has a (real analytic) exponential map
exp : g → G
defined in polar coordinates by the derivative equation
d
exp(tx) = x exp(tx)
dt
for t ∈ R≥0 and x ∈ g. In the special case of an algebraic group, it is the usual matrix exponential. We will
use three standard results about the derivative map. To state the results, we assume some inner product on
g, and the induced left-invariant metric on G.
Proposition 2.5 ([35, Thm. 2.10.1]). The exponential map exp is a bi-Lipschitz, diffeomorphic embedding
when restricted to a ball B = B(0, ε) of some radius ε in g.
Proposition 2.6 ([35, Thm. 2.10.1]). Suppose that g has a basis b1 , . . . , bk , and define a function h : g → G
by !
h ∑ t jb j = ∏ exp(t j b j ) .
j j
Then f is a bi-Lipschitz embedding when restricted to a ball B = B(0, ε) of some radius ε in g. Moreover,
we can choose ε and δ so that f is uniformly bi-Lipschitz for any basis b01 , . . . , b0k with kb0j − b j k < δ .
Proposition 2.6 is less standard than Proposition 2.5, but happily Varadarajan proves a mutual
generalization in a single theorem. The last statement about uniform constants if the basis {b j } is
perturbed is not in the statement of the theorem, but it follows readily from the proof. Remark: The
formula in Proposition 2.6 is a generalization of Euler angles for the group SO(3).
Proposition 2.7 ([35, Thm. 2.12.4]). If [g, h]G = ghg−1 h−1 is the group commutator and [x, y]g is the Lie
bracket, then
[exp(x), exp(y)]G = exp([x, y]g + O max(kxk, kyk)3 ) .
Varadarajan proves Proposition 2.7 with a less uniform error estimate, but the same proof establishes
the given formula.
The plan of our proof of Theorem 2.4 is not very different from the standard proof in Nielsen and
Chuang [30]: For some constant r < 1, we create a set of elements in G that, under the inverse of the
exponential map, is a basis of g at the scale rn . In fact, it always approximately the same basis. These
bases are formed from commutators at larger scales. Finally, every element g ∈ G can first be brought
within the unit ball of the identity and then whittled away to smaller and smaller scales with these bases.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 190
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
Since the result is not required to be uniform in g, we do not need a global epsilon net of the Lie group G,
only a local one near the identity; a global epsilon net would add extra difficulties in the non-compact
case. Another trick that simplifies the derivation is to save the choice of r for the end; it also serves as a
fudge factor to enable the construction.
Proof of Theorem 2.4. Let k be the dimension of G. If g is a perfect Lie algebra, then it has a basis
b1 , . . . , bk and elements x1 , . . . , xk and y1 , . . . , yk such that [x j , y j ] = b j . We choose some positive definite
inner product on g and take the induced left-invariant Riemannian metric on G.
By Proposition 2.5, the exponential map exp : g → G is a bi-Lipschitz diffeomorphism within some
radius ε1 . Also, let ε2 and δ be the constants produced by Proposition 2.6, a radius out to which the map
f is a bi-Lipschitz diffeomorphism. Also, since the Lie bracket is bilinear, and by the approximation
in Proposition 2.7, we can choose a radius ε3 within which both the Lie bracket on g and the group
commutator on G take the ball B3 = B(0, ε3 ) to itself. In other words, both brackets are maps
[·, ·]g : B3 × B3 → B3 and [·, ·]G : exp(B3 ) × exp(B3 ) → exp(B3 )
when ε3 is small enough. Finally we choose
ε0 = min(ε1 , ε2 , ε3 )
to obtain all three properties simultaneously, and we let B0 = B(0, ε0 ).
We take advantage of a subtlety of Proposition 2.6, that the map h only depends on the lines spanned
by {b j }. We can thus rescale the vectors {x j , y j , b j } so that they all lie in B0 , without disturbing the
constants used to define B0 .
We can interpret the group commutator [·, ·]G as a map from B0 × B0 to B0 via the equation
def
[x, y]G = log [exp(x), exp(y)]G
so that we can then say restate Proposition 2.7 as saying that
[x, y]G = [x, y]g + O max(kxk, kyk)3 .
(2.2)
Without loss of generality, g ∈ exp(B0 ): Because Γ densely generates G, we can find a word close to
g and multiply g by its inverse. Also, we let r < 1 be a constant that will be chosen at the end of the proof.
Again because Γ densely generates G, we can assume for each n ≤ 3 that it contains the set {exp(b j,n )}
for a basis {b j,n } in B0 such that
kr−n b j,n − b j k < δ (2.3)
for every j. Recall again that δ is chosen to match Proposition 2.6.
In the remainder of the proof, we will use asymptotic notation such as x = O(r) to express errors in
Lie elements x ∈ g. What we mean is that kxk < Cr, where each constant C does not depend on r or n,
but can depend on everything else defined so far.
For each integer n ≥ 1, we want to define Lie algebra elements b j,n , x j,n , and y j,n , all of them words
in Γ made using the group law of G, such that (2.3) holds for all n, and such that
x j,n = rn (x j + O(r)) and y j,n = rn (y j + O(r)) (2.4)
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 191
G REG K UPERBERG
also holds for all n. The definition is by an inductive algorithm that makes x j,n and y j,n from b j,n+1 , and
makes b j,n from x j,dn/2e and y j,bn/2c . So the numbering in n is slightly out of order, but since we have
already produced b j,n for n ≤ 3, the induction works.
For each n ≥ 1, we choose integers t j = O(r−1 ) so that the expressions
!
log ∏ exp(t j b j,n+1 ) (2.5)
j
are as close as possible to rn x j and rn y j . We set x j,n and y j,n to be these approximations. We claim that
the expressions in (2.5) form an O(rn+1 ))-net of rn B0 . We argue this in stages:
1. The sums ∑ j t j rn+1 b j are a lattice and an O(rn+1 )-net by rescaling.
2. The sums ∑ j t j b j,n+1 are an O(rn+1 )-net because (2.3) limits the distortion of the lattice.
3. The products ∏ j exp(t j b j,n+1 ) are an O(rn+1 )-net because the map h in Proposition 2.6 is Lipschitz
on B0 .
4. The logarithms !
log ∏ exp(t j b j,n+1 )
j
are an O(rn+1 )-net because the exponential map exp is inverse Lipschitz on B0 .
Thus, we obtain the error estimates (2.4).
For each n ≥ 4, we let
b j,n = [x j,dn/2e , y j,bn/2c ]G .
If we combine (2.4) with (2.2), we obtain
b j,n = rn (b j + O(r) + O(r3bn/2c−n )) = rn (b j + O(r)). (2.6)
We would like to reconcile (2.6) with (2.3). The relation (2.6) gives us
kr−n b j,n − b j k < Cr
and we are done provided that Cr < δ . So, at final this stage it is crucial that C does not depend on n or r;
we can choose r small enough to make the induction work.
Finally we let g0 = g ∈ exp(B0 ). We inductively let
hn = ∏ exp(b j,n+1 )t j
j
as in (2.5), and then we let gn+1 = h−1
n gn . We obtain the estimate
k log(gn+1 )k = O(rn+1 ) .
It is easy to check by induction that the word length of each exp(b j,n ) is O(n2 ) (non-uniformly in r, but r
is now fixed). Therefore the word length of the product h1 h2 . . . hn is O(n3 ). Also all of the work to find
these words is polynomial in n.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 192
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
Theorem 2.4 is not uniform in the choice of the group element g and we do not need this uniformity for
our purposes. However, the proof shows that it is uniform on any bounded region in G. For completeness,
we give a complementary result that in any semisimple algebraic group, any element can be efficiently
approximated to within a bounded distance.
Theorem 2.8. Let G be a semisimple (real) algebraic group which is equipped with a left-invariant
Riemannian metric, and which is densely generated by a subset Γ. Let r > 0, let g ∈ G, and let ` = d(g, 1).
Then there is word made from Γ that approximates g to within a bounded distance,
d(g1 g2 . . . gm , g) < r
with m = O(` + 1) uniformly in g. Moreover, such a word can be found in time poly(`).
Evidently Theorem 2.8 can be combined with Theorem 2.4 to obtain a total word length of
m = O(` + 1) + poly(− log(ε)) .
Note also that the lower bound m = Ω(` + 1) follows from the triangle inequality
d(1, gh) ≤ d(1, g) + d(1, h)
and the fact that the finite set Γ has a maximum distance to 1. So Theorem 2.8 is optimal up to a constant
factor.
We conjecture that Theorem 2.8 holds for all connected Lie groups. Note that most named Lie groups,
such as GL(n, R), O(n, C), etc., are algebraic groups.
Proof. We assume that G is given as a subgroup of some GL(n, R) defined by polynomial equations. We
review some of the structure theory of semisimple real algebraic groups [31]:
1. G has a maximal compact subgroup K.
2. Every element g ∈ G has a (canonical) Cartan decomposition g = exp(x)k, where k ∈ K and x ∈ k⊥ ⊆ g.
3. The quotient manifold G/K has a G-invariant Riemannian metric; it is then called a symmetric space
of noncompact type.
4. In the quotient G/K, the unique geodesic connecting gK = exp(x)K to the identity coset is given by
exp(tx)K with 0 ≤ t ≤ 1.
5. Up to a change of basis, G = GT , i. e., G is stable under the transpose map. K = G ∩ O(n) is a maximal
compact subgroup if and only if G = GT .
6. If G = GT , then the Cartan decomposition g = exp(x)k coincides with the polar decomposition for
matrices, so that x and exp(x) are symmetric matrices.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 193
G REG K UPERBERG
Note also that every G-invariant metric on G/K comes from a left-invariant metric on G which also
happens to be right-K-invariant. We assume such a metric on G. As a consequence, given any two group
elements g, h ∈ G, we have both that
d(gK, hK) ≤ dG (g, h)
and that equality can be achieved by passing to a different representative g0 ∈ gK or h0 ∈ hK. (We need
not change both.)
The idea of our proof is to first find a word with all of the desired properties in the symmetric space
G/K rather than in the group G. The advantage of working in G/K is that we know how to calculate
geodesics and distances, using polar decompositions. Geometrically, the idea is not complicated: We can
build a word by taking steps approximately in the direction of the geodesic from 1K to gK.
Since Γ densely generates G, and since closed and bounded regions in G are compact, we can assume
without loss of generality that Γ contains an r/2-net of points inside the closed ball B = B(1, r) of radius
r at the identity. Given gK ∈ G/K, let γ be the unique geodesic that connects 1K to gK; we can compute
it from the polar decomposition of g. Let hK be the point at which γ exits BK. Then we know or we can
assume that
d(1K, hK) = d(1, h) = r and d(hK, gK) = d(h, g) = ` − r .
We can choose g1 ∈ Γ such that d(g1 , h) < r/2. By the triangle inequality,
r
d(g1 , g) = d(1, g−1
1 g) < ` − .
2
Thus, we can let g0 = g−11 g and proceed by induction.
We obtain a word w such that d(w−1 g, K) < r/2. We are given that K is compact; it follows that there
is a finite set of words v in Γ that forms an r/2-net of K. So for one of these words,
r r
d(wv, g) = d(v, w−1 g) < + =r
2 2
as desired.
2.5 Postselection
Aaronson [1] defined the class PostBQP as polynomial-time quantum computation with free retries, or
postselection. In other words, the computation can output |yesi, |noi, or |retryi. (In Aaronson’s formal
definition, the outputs are measured as h00|, h01|, and h1 ∗ |, respectively; of course the output can equally
well be a qutrit whose values are renamed semantically.) If the absolute probabilities are
P[yes] = a and P[no] = b
then the conditional or postselected probabilities are
a b
P[yes | yes or no] = and P[no | yes or no] = .
a+b a+b
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 194
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
An algorithm in PostBQP is required to output “yes” or “no” with conditional (rather than absolute)
probability of at least 2/3. It is trivially equivalent to say that for some c > 1, either a > cb or b > ca;
all values of c are equivalent because c can be amplified by repeated trials. There is an analogous class
PostBPP for classical randomized computations; it was also defined previously as BPPpath . Aaronson
established that PostBQP = PP. It is not hard to show that PostBQP is a subset of PP, just as BQP, NP,
and a number of other important classes are known to be. (The inclusion SBQP ⊆ A0 PP is proved in the
same way in Proposition 2.13.) The more surprising fact is that PostBQP is all of PP.
By contrast, PostBPP is unlikely to be all of PP. The relevant complexity results are as follows:
1. PostBPP contains P||NP (P with parallel NP queries) [17].
2. P||NP equals PNP[log] (P with logarithmically many NP queries) [19, 10].
3. PostBPP derandomizes to P||NP . I. e., they are equal if sufficiently good pseudo-random number
generators exist [33].
4. Without any derandomization assumption [17],
NP
PostBPP ⊆ BPPNP ⊆ NPNP .
Thus, PostBPP is known to be in the third level of PH. If we accept derandomization, then it is in the
second level.
Another interpretation of PostBQP or PostBPP is given by the following proposition:
Proposition 2.9. Let c > 1. Then a decision function D is in PostBPP if and only if there are two
randomized, polynomial time algorithms run by Alice and Bob that report “yes” with probabilities a and
b, and such that D(x) = yes when a > cb and D(x) = no when b > ca. The same holds for PostBQP and
quantum algorithms.
Proof. Suppose that we are given a PostBQP algorithm in the original definition. Then Alice and Bob
can both run this algorithm, with the following conversion:
yes 7→ Alice yes, Bob no ,
no 7→ Alice no, Bob yes ,
retry 7→ Alice no, Bob no .
It is easy to check that this satisfies the requirements of the proposition. Conversely, suppose that Alice
and Bob have separate algorithms. Then we can combine them into one postselecting algorithm in
Aaronson’s sense by flipping a coin to decide which of Alice or Bob runs; only one of them runs in a
given trial. We can convert according to the following table:
Alice yes 7→ yes , Alice no 7→ retry ,
Bob yes 7→ no , Bob no 7→ retry .
It is easy to check that this conversion satisfies Aaronson’s definition.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 195
G REG K UPERBERG
We also need to clarify the definition of PostBQP with regard to different gate sets. Aaronson defines
PostBQP using Hadamard and Toffoli gates, on the argument that all choices of gates are equivalent by
Solovay-Kitaev. But this is somewhat overstated; we give a more precise equivalence as follows:
Theorem 2.10. Let Γ be a universal gate set acting on qudits, let PostBQPΓ be PostBQP defined with
the gate set Γ, and suppose that:
1. The matrix entries in each gate have an FPTEAS.
2. If z 6= 0 is expressible as an integer polynomial in the gate entries with bit complexity poly(n) with
exponents written in unary, then
|z| > exp(−poly(n)) .
Then PostBQP = PostBQPΓ . If only condition 1 holds, then PostBQP ⊆ PostBQPΓ .
Before proving Theorem 2.10, here are three remarks. First, the class BQP only requires a weaker
version of condition 1, namely that each gate in Γ has an FPTAS, in order to enable the Solovay-Kitaev
theorem. We need FPTEAS because PostBQP relies on exponentially small probabilities. Without
exponentially good approximation, Solovay-Kitaev would still give us a circuit reduction, but the
reduction would be relative to P/poly rather than relative to P. Second, we conjecture that if only
condition 1 holds, then PostBQP and PostBQPΓ are not always equal. Third, we do not know whether
postselected quantum computation is gate-independent with a time bound of Õ(nα ) for some fixed
exponent α, because the Solovay-Kitaev theorem could change the exponent.
Proof. Condition 1 and Theorem 2.4 together imply that PostBQP ⊆ PostBQPΓ . The traditional gate
set consisting of Hadamard and Toffoli gates can be approximated using gates in Γ; how good of an
approximation is sufficient? It is easy to check that the Hadamard and Toffoli gates satisfy condition 2, so
the strength of approximation that we need is exp(−poly(|x|)). This is precisely how much Theorem 2.4
gives us with polynomial overhead, if each gate in Γ has an FPTEAS.
The same argument works in reverse, but we must add condition 2 explicitly, since it is not guaranteed
in general.
We will not strictly need the following proposition, but it helps for understanding Theorem 2.10. It
shows that any gate set with algebraic matrix entries automatically satisfies condition 2.
Theorem 2.11. Let t1 , . . . ,tk be a finite list of algebraic numbers in C, and let p be an integer polynomial
in k variables with bit complexity poly(n) with exponents written in unary. Then
|p(t1 , . . . ,tk )| > exp(−poly(n))
(non-uniformly in the choice of {t j }), assuming that the value is non-zero.
Proof. We first reduce to the case k = 1. The numbers {t j } all lie in some finite-degree field extension
K ⊇ Q. It is a theorem of Galois that every such field has a generator t. We thus obtain that each t j = p j (t)
is some rational polynomial in t, and by rescaling t, we can make each p j an integer polynomial; these
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 196
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
fixed polynomials can be composed with the polynomial p in the proposition. Thus, without loss of
generality, we can take k = 1 and t = t1 .
Next we consider the case that t = a/b ∈ Q is rational. In this it is enough for p to have degree
poly(n), because we immediately get
|p(t)| > bdeg p .
In the general case, let d be the degree of the field K, and let z = p(t). Then z = z1 has a list of Galois
conjugates z1 , z2 , . . . , zd . Moreover, if we choose some basis of the ring of integers of K, then t has rational
coordinates s1 , . . . , sd , and we can write
d
∏ z j = q(s1 , . . . , sd )
j=1
for a polynomial q with deg q = d(deg p). Thus by the rational case we obtain
d
∏ z j > exp(−poly(n)) .
j=1
At the same time, because of the degree bound on p and because each coefficient of p is bounded by
exp(poly(n)), we obtain
|z j | < exp(−poly(n)) .
By dividing through, we obtain
|z| = |z1 | > exp(−poly(n)) .
It is important to compare PostBQP and PostBPP to three other complexity classes: A0 PP, or
one-sided almost wide PP, defined by Vyalyi [37]; SBP, or small-bounded probabilistic P [6]; and a
quantum class that we will call SBQP. All three classes depend on a real-valued function f (x) in FP
(expressed in fixed-point arithmetic, say), where x is the input to the decision problem, and a constant
c > 1. The classes SBP and SBQP are defined in the same way as the Alice-Bob definition of PostBPP
and PostBQP, except with a different model for Bob. As in Proposition 2.9, Alice executes a randomized
algorithm in the case of SBP and a quantum algorithm in the case of SBQP and has success probability a.
Meanwhile Bob’s value b = f (x) is computed directly in FP, as a real number in fixed-point arithmetic.
In both SBP and SBQP, the answer is “yes” when a > cb and “no” when b > ca.
Finally, A0 PP is a non-quantum class that is closely related to PP and is defined similarly to SBP.
Like SBP, a decision function D ∈ A0 PP has a function b = f (x) which lies in FP, and a randomized
algorithm whose success probability is a. When D ∈ A0 PP, we require that
1 1 1
D(x) = yes =⇒ a > cb + and D(x) = no =⇒ ≤ a < b+ ,
2 2 2
which again is like SBP but has an extra 1/2 term.
Lemma 2.12. Without loss of generality, the function f (x) in the definition of A0 PP, SBP, SBQP can be
taken to be 2−p(|x|) for some p; and all values of the constant c are equivalent.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 197
G REG K UPERBERG
Proof. The constant c is irrelevant by the usual technique of amplification by repeated trials. This is
immediate in the case of SBP and SBQP. It is not very difficult in the case of A0 PP, and was established
by Vyalyi [37].
To argue that f (x) can be set to 2−p(|x|) (in the cases of SBP and SBQP), first choose p so that
f (x) > 2−p(|x|) . Then Alice can compute f (x) and reduce her success probability by a factor of 2 p(|x|) f (x).
The argument in the case of A0 PP is essentially the same and was also explained by Vyalyi [37].
Proposition 2.13. SBQP = A0 PP .
Proof. The proof is almost the same as Aaronson’s proof that PostBQP = PP [1, Thm. 3.4]. We can also
define A0 PP as a counting class in which, for each certificate y of length n, the computation produces a
value f (y) = ±1, and these values are summed to produce A(x). For a decision problem D ∈ A0 PP, we
require that
D(x) = yes =⇒ A(x) > 2nCb and D(x) = no =⇒ 0 ≤ A(x) < 2n b .
First, let L ∈ SBQP be computed by a quantum circuit that consists of Hadamard and Toffoli gates. It
is convenient to change the counting model of A0 PP slightly to let the values be ±1 or 0. Then we obtain
an A0 PP algorithm by multilinear expansion of the effect of these gates on density matrices. The matrix
entries of a Toffoli gate, in its effect on a density matrix, are 0 and 1; the corresponding matrix entries of
a Hadamard gate are ±1/2. The final probability is given by a partial trace of the output density matrix,
and is non-negative and exactly matches the criteria for A0 PP.
Now let L ∈ A0 PP and let a be Alice’s success probability in the A0 PP algorithm. We can again
slightly re-express the counting model of A0 PP so that f (y) ∈ {0, 1} and its sum A = A(x) is given by
A = 2n a.
Then, in the SBQP algorithm, we can quantum-compute the unitary map
U f |yi = |y, f (y)i
where the value f (y) is written to an ancilla qubit. We provide the input | + + · · · +i to U f , and then
postselect on whether the left n qubits of the result are all |+i. If they are, then the ancilla qubit has the
state
|ψi ∝ (1 − a)|0i + a|1i .
If this qubit is measured in the ± basis, then the probability of |−i is
(2a − 1)2
a0 = .
1 + (2a − 1)2
If we assume that b > 1/4 and let c = 2 in the A0 PP algorithm, then
1 4b2
0<a< + b =⇒ a0 < < 4b2 and
2 1 + 4b2
1 16b2
a > + 2b =⇒ a0 > > 8b2 .
2 1 + 16b2
So we can let b0 = 4b2 and c0 = 2 in an SBQP algorithm that produces the probability a0 .
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 198
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
Many of the complexity classes discussed here employ the semantic condition that the probabilities
of particular outcomes are above one threshold or below another threshold. We can also consider promise
versions of these classes in which these conditions hold for some inputs and not others. When they
are considered in promise form, SBP- and SBQP-hardness are the same as PostBPP- and PostBQP-
hardness. The non-trivial part of this equality (given that SBP ⊆ PostBPP and SBQP ⊆ PostBQP) is
the following inclusions:
Proposition 2.14. PromisePostBPP ⊆ PPromiseSBP and PromisePostBQP ⊆ PPromiseSBQP .
Proof. Suppose that D ∈ PromisePostBQP is a decision function and that it is implemented by a quantum
circuit. We recall the assumption that
max(a, b) > 2−n
where n = poly(|x|) and x is the input.
The construction is then similar to a rescaling argument in Aaronson’s proof that PostBQP = PP
(explained in [1, Thm. 3.4] in the second half of the main proof). We assume that either a > 8b or that
b > 8a. Then for each 0 ≤ k ≤ n, use PromiseSBQP to compare both a and b to 2−k . If a > 8b, then for
every k, PromiseSBQP will either reliably report that a > 2−k or that 2−k > b, and there will exist a k for
which it will do both. Meanwhile if b > 8a, it will report that b > 2−k or that 2−k > a, and both for at
least one k. These two outcomes are mutually exclusive.
The argument that PromisePostBPP ⊆ PPromiseSBP is the same, but simpler since the lower bound
on max(a, b) is immediate.
Finally, as noted by Aaronson, linear computation is another interesting interpretation of PostBQP.
(This is linear computation in the sense of non-unitary quantum computation, not Z/2-linear circuits or
numerical linear algebra!) Post-conditioning allows us to replace unitary gates by subunitary gates, and to
rescale subunitary gates arbitrarily. But every linear operator that acts on vector states |ψi is proportional
to a subunitary operator. Thus, PostBQP can also be defined by the class of polynomial-sized circuits
with linear gates, without the unitary restriction.
At first glance, the measurement probability (2.1) used for PostBQP still use the Hilbert space
structure, even if the gates do not. But this is not entirely true either. If circuits are evaluated in a form
such as h0n |C|0n i, and if the gates need not be unitary, then there is no need to equate the vector |0i with
the dual vector h0| using a Hermitian form. We can instead define h0| and h1| to be the dual basis to |0i
and |1i. The drawback to this computational model is that it does not have a reasonable notion of a mixed
state, nor partial trace that makes mixed states from pure states. We may define h0| using both |0i and |1i
(using the relations h0|0i = 1 and h0|1i = 0), but we cannot in general define hψ| or |ψihψ| from |ψi.
Indeed, we can more cleanly define linear computation as computation with libits (linear bits). By
definition, a libit is like a qubit in the sense that it is assigned a 2-dimensional complex state space V . But
unlike a qubit, V is just a vector space with no Hilbert space structure, so that there isn’t even any way to
say whether linear gates acting on libits are unitary. A libit has kets, which are vectors |ψi ∈ V , and it has
bras, which are dual vectors hψ| ∈ V ∗ . But V and V ∗ are simply different vector spaces.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 199
G REG K UPERBERG
3 The Jones polynomial
In this section we review the definition of the Jones polynomial and some theorems about it that lead to
a proof of Theorem 1.2. We will define the Jones polynomial using the Kauffman bracket formalism,
which in our opinion is one of the simplest and nicest definitions. For background see Kauffman [24];
also previous work by the author [27, §2] has a review of properties of the Kauffman bracket renamed as
the “A1 spider.”
3.1 The Kauffman bracket
Let t 1/4 ∈ C× be a non-zero complex number. (The reason for this notation is that all of the essential
mathematics of the Jones polynomial depends only t, even though it is convenient to choose a fourth
root t 1/4 to define it.) Then the Kauffman bracket is defined as a function on links projections, or link
diagrams, by the following recursive relations:
E E E
= −t 1/4 − t −1/4 , and (3.1)
D EK K K
= −t 1/2 − t −1/2 .
K
Relations of this type are called skein relations. (Kauffman writes (3.1) with a bracket h·i for all terms,
but a “ket” is more consistent with standard quantum notation; see Section 3.2.) What the relations mean
is that if three link diagrams L1 , L2 , and L3 are identical except that they differ in one place as indicated,
then their Kauffman bracket values satisfy the given linear relation:
hL1 iK = −t 1/4 hL2 iK − t −1/4 hL3 iK .
The second equation says that if L1 and L2 are two link diagrams that are the same except that L1 has an
extra circle, then
hL1 iK = −(t 1/2 + t −1/2 )hL2 iK .
The base of the recursion is given by saying that the Kauffman bracket of the empty link diagram is 1.
With this normalization, the Jones polynomial is given by
hLiK
V (L,t) =
−(t + t −1/2 )t 3w/4
1/2
where w is the writhe of the diagram L, i. e., the number of positive crossings minus the number of
negative crossings. It is a remarkable fact, although it is not difficult to check, that the Kauffman bracket
is invariant under the second and third Reidemeister moves [9, §1.C], and that the Jones polynomial is
invariant under all three Reidemeister moves and is therefore a link invariant.
3.2 Skein spaces
The importance of the skein relations is that they can be extend the Kauffman bracket to a “Kauffman ket”
for tangles. Here a tangle is an incomplete link, i. e., the intersection of a link and a ball whose boundary
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 200
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
is transverse to the link. By definition, the Kauffman ket of a tangle is a vector in a corresponding skein
space; actually the skein space itself is defined from the tangles. More precisely, given a 3-dimensional
ball with 2n marked points, let F(2n) be the formal vector space of linear combinations of all tangles
that end at the marked points. Then the skein space W (2n) = F(2n)/ ∼ is by definition the quotient of
the vector space F(2n) by the relations (3.1). Any element of W (2n), i. e., any linear combination of
tangles modulo the skein relations, is called a skein. In this construction, then, the Kauffman bracket |T i
of a tangle T is “itself,” i. e., the skein that it represents. If W (2n) is a skein space of tangles with 2n
endpoints, then the Kauffman relations imply that
1 2n
dimW (2n) = Cn = , (3.2)
n+1 n
the nth Catalan number, because the planar matchings of the 2n endpoints are a basis of the skein space.
When the parameter t is a root of unity, it is more important to look at a certain reduced skein space
X(2n). First, we take an explicit model of W (2n) as the skein space of tangles in the right half-plane
with end points at the integers 1, 2, . . . , 2n on the vertical number line. Then there is another skein space
W 0 (2n) consisting of tangles in the left half plane and with the same boundary. (W 0 (2n) is of course
equivalent to W (2n), but in more than one way: by reflection, by rotation by 180 degrees, etc.) Then
there is a bilinear pairing
h·, ·iK : W (2n) ×W 0 (2n) → C
given by gluing together one tangle on each side and evaluating the Kauffman bracket. For example:
W 0 (2n) 3 ∈ W (2n) .
Finally,
def
X(2n) = W (2n)/(kerh·, ·iK ) .
It is known that h·, ·iK is degenerate on W (2n) if and only if t is a root of unity of order r > 1 and
n ≥ r − 1. Moreover, if |t| = 1, then there is a conjugate-linear isomorphism between W (2n) and W 0 (2n)
given by reflecting the tangle across the horizontal line. (The reflection reverses crossings, so we need
|t| = 1 in order to have t ∗ = t −1 and thus have conjugate linearity.) Thus, if |t| = 1, then h·, ·iK is a
non-degenerate Hermitian form on the quotient space X(2n). It is further known that h·, ·iK is positive
definite if t = exp(2πi/r) is a principal root of unity. Thus, if t is a principal root of unity, X(2n) is a
finite-dimensional Hilbert space, so it and the Jones polynomial become relevant to quantum computation.
(See Section 3.3 for references and further explanation.)
The skein spaces W (2n) and X(2n) have an action of the braid group B2n on 2n strands. The action is
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 201
G REG K UPERBERG
given by attaching the braid to a tangle or skein to make a new tangle or skein:
.
This is the Jones braid representation on X(2n) [13]. In key cases X(2n) is a Hilbert space and the braid
representation is unitary (Section 3.3).
A variation of this theme is that if σ ∈ Bn is a braid on n strands, we can simply expand it as a skein
in W (2n), with n endpoints on the left and on the right. (Or in X(2n), but for the moment W (2n) is more
relevant.) We can also concatenate two elements of W (2n) in the same way that braids are multiplied.
I. e., having segregated the 2n endpoints into n each on the left and right, we can define a bilinear product
map
m : W (2n) ×W (2n) −→ W (2n)
where m(s,t) is given by attaching the right endpoints of s ∈ W (2n) to the left endpoints of t ∈ W (2n).
This makes W (2n) into an associative algebra called the Temperley-Lieb algebra [5]. The Jones braid
representation generalizes to a representation
ρ : W (4n) × X(2n) −→ X(2n)
of the Temperley-Lieb algebra W (4n), given by attaching s ∈ W (4n) to t ∈ X(2n) along half of the
endpoints of the former and all of the endpoints of the latter.
3.3 Other models of skein spaces
There are many ways to define the skein space W (2n) and the reduced skein space X(2n), and the braid
group action on them. One of the most important models is that, when t is not a root of unity, W (2n) is
the invariant subspace Inv(V ⊗2n ) of the representation V ⊗2n of the quantum group U√t (sl(2)), where V is
the standard 2-dimensional irreducible representation [23]. This model is well-known to be the equivalent
to the Kauffman skein space that we use here [14]. Moreover, it is well-known that as t approaches a
principal root of unity, the pairing h·, ·iK on W (2n) undergoes a degeneration, that the reduced skein
space X(2n) is a Hilbert space, and that the associated braid representation is unitary [26, 38]. In fact,
all of these facts are part of a larger theory for all quantum groups U√t (g) for any simple Lie algebra g.
Unfortunately, it is not practical to give a summarize the theory of quantum groups here.
Since Aharonov, Jones, and Landau [5] use the so-called path model, we want to relate our planar
matchings model to that one. In any case, the path model helps to compute the dimension of X(2n), and
it yields one proof that it is a Hilbert space. The rest of this section is a summary of calculations based on
more advanced points of the Kauffman skein theory [25]. We do not include complete proofs. The results
are not needed for our results, other than the one standard fact that X(2n) is a Hilbert space when t is a
principal root of unity.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 202
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
Model W (2n) with planar matchings in the upper half plane. These are equivalent to balanced strings
of parentheses, by matching the parentheses:
.
( ) ( ( ) ( ) )
Then, a balanced string of parentheses of length 2n is equivalent to a path from 0 to 0 in the non-negative
integers Z≥0 , given by stepping to the right at each left parenthesis and to the left at each right parenthesis.
It is known that the planar matchings corresponding to the paths that lie in the discrete interval
{0, 1, . . . , r − 2} are a basis of X(2n), when t is an rth root of unity with r > 1. Call these the admissible
matchings. They are not an orthogonal basis, but their Gram-Schmidt orthogonalization in a natural
partial ordering is the path basis used in [5]. (In other words, the admissible matchings are those whose
parentheses do not nest beyond a depth of r − 2.) The partial ordering can be expressed as a relation on
paths, that p q if the path p never crosses to the right of q.
In order to argue these facts, one employs a special skein with 2n endpoints called a Jones-Wenzl
projector, which is given by the following recurrence relation
n−1 n−2
n [n − 1] n − 1
= +
[n]
and the rule that the projector of order 1 is a plain strand. Here a strand labeled with n means n strands,
and [n] is a quantum integer defined by the formula
t n/2 − t −n/2
[n] = 1/2 −1/2 .
t −t
The Jones-Wenzl projector exists for all n when t is not a root of unity or t = 1, and it exists when n < r
when t is a root of unity of order r > 1. Also, the projector of order r − 1 vanishes in X(2r − 2). When
working with reduced skein spaces X(2k), we can assume, as a new skein relation, that the projector of
order r − 1 vanishes. This new skein relation allows us to express a planar matching whose path reaches
r − 1 in terms of earlier planar matchings. Thus, we can conclude that the admissible matchings are a
spanning set of X(2n), and we can ignore the inadmissible matchings.
Then, we can modify a planar matching by inserting a vertical projector between every pair of
endpoints:
.
( ) ( ( ) ( ) )
(The projectors of order 0 and 1 can be omitted, since they are trivial.) Call a skein of this form a path
vector. By expanding the projectors, one can show that path vectors are related to admissible planar
matchings by a triangular matrix. Since admissible matchings span X(2n), so do the path vectors; and if
the path vectors are linearly independent in X(2n), so are admissible matchings.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 203
G REG K UPERBERG
The path vectors, as vectors in W (2n) and W 0 (2n), have a Gram matrix using the bilinear form on
these two spaces. It is not hard to check, using various properties of Jones-Wenzl projectors, that this
Gram matrix is diagonal and that the diagonal entries are non-zero. Thus, the path vectors are a basis
of X(2n). When t is a principal root of unity, the diagonal entries are also positive real numbers, which
implies that X(2n) is a Hilbert space. Finally, the triangular change of basis from admissible matchings
to path vectors shows that the latter are the Gram-Schmidt orthogonalization of the former.
3.4 Quantum computation with braids
The idea, first explained by Freedman, Larsen, and Wang [12] is that when t is a principal root of unity,
the Hilbert space X(2n) can be interpreted as a quantum memory, and a braid σ ∈ B2n can be interpreted
as a quantum circuit. The question then is whether such a model is universal for quantum computation.
The well-known answer is yes when t is a non-lattice, principal root of unity, and the main technical tool
is the following theorem.
Theorem 3.1 (Freedman, Larsen, Wang [13]). Let t = exp(2πi/r) with r = 5 or r ≥ 7. Then Jones braid
representation of B2n is dense in PSU(X(2n)) for n ≥ 2, or for n ≥ 3 in the case r = 10.
Corollary 3.2. Let t = exp(2πi/r) with r = 5 or r ≥ 7. Let
p(x) > 2−poly(|x|)
be the probability that some polynomial-time quantum algorithm accepts an input x. Then the input x can
be encoded as a link L = L(x) with bridge number g, so that
|hLiK |2
p(x) ≈ , (3.3)
|t 1/2 + t −1/2 |2g .
where “≈” is in the FPTEAS sense.
Although Corollary 3.2 is essentially due to Freedman, Larsen, and Wang, we describe one way to
prove it, since it is relevant to our result.
Proof of Corollary 3.2. First, X(4) is always two-dimensional and it can be interpreted as a qubit. We
can define its computational basis simply by applying the Gram-Schmidt procedure to the basis of planar
matchings:
1
|0i = 1/2 −1/2 , (3.4)
t +t K
1 1
|1i = √ + 1/2 −1/2 .
t + 1 + t −1 K t +t K
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 204
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
Second, by Theorem 3.1 and Theorem 2.4, a quantum circuit C on n qubits can be encoded to
exponential tolerance as a braid σ ∈ B4n on 4n strands. Third, the amplitude h0n |C|0n i is proportional to
the Kauffman bracket of a link L, which is the braid σ capped with 2n U-turns at both ends:
n n 1
h0 |C|0 i ≈ 1/2 −1/2 2n . (3.5)
(t + t ) K
σ
A diagram of a link L in this form, a braid capped with U-turns, is called a plat diagram; the number of
U-turns at each end, g = 2n in this case, is its bridge number. Finally, by Equation (2.1), we can express
the acceptance probability as |h0n |C|0n i|2 where C has n = poly(|x|) qubits and poly(|x|) gates and can
be generated in deterministic polynomial time from x. Combining Equations (3.5) and (2.1), we obtain
(3.3), as desired.
Remark 3.3. In the proof of Corollary 3.2, it is easy to worry about leakage of amplitude into the unused
part of the Hilbert space X(4n). But using the plat diagram method, Theorem 3.1 and Theorem 2.4 applied
to the unitary group PSU(X(8)) ∼ = PSU(14) controls this leakage along with the intended amplitudes.
In some other encodings of quantum computation into the Jones polynomial, one might want a joint
denseness version of Theorem 3.1. It isn’t needed here, although it is needed in order to prove Theorem 3.1
itself by induction.
3.5 Proof of Theorem 1.2
Proof. Corollary 3.2 describes a way to approximately (FPTEAS) encode a circuit calculation h0n |C|0n i
as a plat braid with bridge number 2g. This type of circuit calculation is BQP-complete by Proposition 2.3.
Each gate of the circuit C (say a Toffoli or a Hadamard gate, if these standard generators are used) can be
approximated by a braid by Theorem 3.1 (Freedman-Larsen-Wang) and Theorem 2.4 (Solovay-Kitaev).
Thus the left side of (3.3) is BQP-complete in additive approximation. But the denominator is exponential
in g. This is not by itself a hardness result, but it is a strong indication that Theorem 1.1 does not usually
provide information about the Jones polynomial, and that a hardness result should be available.
The first hardness result to obtain is that multiplicative approximation to the Jones polynomial
norm |V (L,t)| is #P-hard. Almost by definition (more precisely, by Proposition 2.3), multiplicative
approximation to the left side is SBQP-hard, which by Proposition 2.14 is the same as PostBQP-hard.
The denominator on the right side is easily computable, so we obtain that multiplicative approximation to
the numerator is also PostBQP-hard. This numerator is the Kauffman bracket value |hLiK |2 , which equals
|V (L,t)|2 , which implies hardness of |V (L,t)|. Finally, Aaronson’s theorem tells us that PostBQP = PP,
and PP-hard implies #P-hard by Proposition 2.1.
To complete the proof, we need to refine the construction in two ways. We need to convert multiplica-
tive approximation to more general value-distinguishing approximation; and we need to change the link L
to a knot.
For the first refinement, let a > b > 0 be constants as in the statement of Theorem 1.2, and let p and c
be the polynomial and the constant in the modified definition of SBQP in Lemma 2.12. By that lemma
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 205
G REG K UPERBERG
and Equation (3.3), it is SBQP-complete and therefore #P-hard to determine whether
(
|hLiK |2 > c2−p(|x|)
.
|t 1/2 + t −1/2 |2g < 2−p(|x|)
We want to make a modified link L0 to make it hard to determine whether |hL0 iK |2 is more than a or less
than b. Recall that g = poly(|x|), and note that
|t 1/2 + t −1/2 | > 1 .
If
|t 1/2 + t −1/2 |2g 2 p(|x|)
when |x| is large, then we can add m = poly(|x|) copies of the unknot to L so that
|t 1/2 + t −1/2 |2g+2m 2−p(|x|)
is bounded. On the other hand, if
|t 1/2 + t −1/2 |2g 2 p(|x|)
then we can use denseness to first create a link L0 (say a 2-bridge link corresponding to a 1-qubit circuit)
such that |hL0 iK | is a small constant. Then we can add m copies of L0 to L so that
|hL0 iK |2m |t 1/2 + t −1/2 |2g 2−p(|x|)
is bounded. The constant c in the definition of SBQP can be chosen to overwhelm the bound in either
case as well as the specific values of a and b.
Finally, we want to further modify L0 into a link L00 that has only one component, i. e., is a knot. The
trick for this is that since the braid group is dense, the pure braid group is also dense. Thus we can switch
two strands, and then approximately cancel its effect with a pure braid that does not permute any strands.
The permutation induced by the braid is thus decoupled from the approximate value of hL00 iK , so L00 can
be chosen so that it has only one component.
4 The Tutte polynomial
4.1 Tutte and Potts
In order to define the Tutte polynomial, we will first define another graph invariant with equivalent
information known as the Potts model. The Potts model of a graph G depends on a positive integer q,
the number of colors; and on a variable y. The weight of a coloring of the vertices of G with q colors
is defined as yk if k of the edges of G connect two vertices of the same color. Then the Potts partition
function Z(G, y, q) is defined as the total weight of all vertex colorings. The Potts partition function yields
the Tutte polynomial T (G, x, y) by the formula
def
T (G, x, y) = (y − 1)−v (x − 1)−c Z(G, y, q)
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 206
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
where
q = (x − 1)(y − 1) , (4.1)
and G has v vertices and c components.
An important variation of the Potts model (or the Tutte polynomial) is the multivariate version, where
the weight y can be different for each edge of G, to make a weighted graph G(~y). Then the Potts partition
function is defined in the usual way as a multiplicative sum. Namely, the partition function Z(G(~y), q) is
defined as the total weight of all colorings c with n colors; the weight of c is defined as the product of the
weights ye for edges e whose vertices have the same color. Or, as a formula, if C is the set of colorings
and E is the set of edges of G, then
Z(G(~y), q) = ∑ ∏ y( j,k) .
c∈C ( j,k)∈E
c( j)=c(k)
Having generalized the parameter y to a weight assigned to each edge, we still want to make use of the
parameter x defined from y and q by the relation (4.1). To this end, if we assign a weight y to an edge, we
will also assign it the dual weight x using (4.1). The dual weight x is simply meant as another notation for
the weight y. Since the dual weight x is not the same number as the weight y, we will denote it in the
diagrams with parentheses.
The ordinary or multivariate Potts model can also be defined by a contraction-deletion formula,
together with the fact that its value for an isolated vertex is q:
y
... .. .
. = ..
.. .
. + (y − 1) ..
..
. , and (4.2)
= q.
(Tutte’s original definition of the Tutte polynomial uses an equivalent contraction-deletion formula.) This
second definition is important for two reasons.
First, it shows that the Potts partition function Z(G, y, q) or Z(G(~y), q) is a polynomial in all of its
parameters; it isn’t only defined when q is a positive integer. Note that we can only give the Tutte
polynomial or the Potts model a complexity if each parameter such as q or y has a computational
complexity. To this end, we assume that every parameter is a real number with an FPTEAS. For no
essential reason, we do not consider complex values.
Second, the contraction-deletion formula allows us to generalize the Potts model to a skein theory
with skein spaces, in the same sense as Section 3.2. More precisely, for each n we let F(n)P be the vector
space of formal linear combinations of weighted planar graphs with n marked boundary points on the
outside face. In fact, we would like to allow some of the marked boundary points to be identical, so
formally we consider a graph G(~y) together with a function from labels to vertices,
f : {1, . . . , n} → V (G(~y))
which need not be either injective or surjective. In the diagrams we draw the boundary vertices in red.
If a vertex is marked twice or more as a boundary, then it is drawn as multiple vertices connected by
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 207
G REG K UPERBERG
double edges to denote that the vertices are equal. Thus (4.2) can be written as follows, also using the ket
notation to signify that we are creating a skein theory:
y E E E
= + (y − 1) , and (4.3)
EP E P P
=q .
P P
We then define the skein space to be the quotient W (n)P = F(n)P / ∼, where the equivalence is given by
the relation (4.2).
To review, we have used (4.2) to define skein spaces W (n)P for planar graphs. It is easy to show that
one basis of W (n)P is given by noncrossing partitions of n points arranged in a circle, corresponding to
graphs with no edges (other than double edges):
.
P
It is well known that the number of noncrossing partitions is the nth Catalan number, so that
1 2n
dimW (n)P = Cn =
n+1 n
which is the same as the dimension of the Kauffman skein space W (2n)K as given in (3.2). In fact, the
two skein theories are equivalent, and we will make use of this coincidence to prove Theorem 1.3.
Remark 4.1. What matters the most for a result such as Theorem 1.3 is that the Potts model has some
skein theory. Although the terminology “skein theory” is not traditional in graph theory, graph theorists
have long used the idea of a skein theory, namely local recurrence relations such as the contraction-
deletion formula. In particular, if we let We (n)P be the skein space of all graphs with n boundary vertices,
not just planar graphs, then it is a standard graph theory fact that one basis for it is the set of partitions of
n points. The dimension of this skein space is the nth Bell number (by definition, the number of partitions
of a set with n elements) rather than the nth Catalan number in the planar case.
4.2 Circuits and braids
In this section, we will define Potts quantum circuits by analogy with the Jones braid representation and
its use in the proof of Corollary 3.2. In particular, we will encode the standard quantum circuit evaluation
h0n |C|0n i in Potts circuit by analogy with (3.5). Just as we did in Section 3.2, we define W (n)P using
graphs in the right half-plane and we denote elements as kets |ψi; we define W 0 (n)P using graphs in the
left half-plane and we denote its elements as bras hψ|. However, we will not define any Hilbert space
structures on our skein spaces. Instead, we will just use vector spaces and interpret them using the libit or
linear computation model defined at the end of Section 2.5. For concreteness, we define the initial state
|ψi ∈ W (n)P to be n disconnected dots, and the final state hψ| ∈ W 0 (n)P to also be n disconnected dots.
Having defined initial and final states for Potts circuits, we still need to define the circuits themselves.
We could define a Potts circuits to be any planar graph with left and right boundary vertices. This is the
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 208
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
more general possible choice; but we will define more specific quantum gate operators P(y), the parallel
gate, and S(x), the series gate. A gate P(y) is an edge with weight y, whose two vertices are both input
vertices and output vertices. A gate S(x) is an edge with dual weight x that connects an input vertex to an
output vertex. If there are n vertices, then there are n − 1 positions for P(y) and n positions for the gate
S(x); we number them P(y) j and S(x) j starting with j = 1. For example, if n = 4, then:
y (x)
P(y)1 = and S(x)2 = .
As an example of the full circuit construction, if n = 4, we can make a graph G composed of 8 gates
so that
Z(G(~y); q) = hψ|P(19)1 P(17)2 P(13)3 S(11)1 S(7)2 S(5)4 P(3)1 P(2)2 |ψi .
In this example, the graph G(~y) is:
(11)
3
19
G(~y) = 17 2 .
(7)
13
(5)
To conclude this section, we show that for certain values of the parameters x and y, the gates P(y) and
S(x) aren’t just analogous to the Jones braid representation; up to scalar factors, they are the Jones braid
representation.
Theorem 4.2. Let q and t 1/4 be parameters such that
q = t + 2 + t −1 .
Then for each n, there is a vector space isomorphism between the planar Potts skein space W (n)P and the
Kauffman skein space W (2n)K such that the operators P(−t) and S(−t) are proportional to half-twist
generators of the Jones braid representation.
Note that q > 4 in Theorem 1.3, the corresponding value of t is real and positive in Theorem 4.2, and
we can also take t 1/4 to be real and positive. Thus, in our use of Theorem 4.2, we can do all calculations
over the field R.
Theorem 4.2 and its proof are a version of one of the earliest constructions of the Jones polynomial
of a link L, as the Potts partition function of an associated graph G(~y) [21, §2]. First, the diagram of L
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 209
G REG K UPERBERG
should be given a checkerboard coloring:
.
Then we can make a weighted graph G(~y) by replacing the gray regions by vertices, and the crossings
by edges. There are two types of crossings, checkerboard-positive and checkerboard-negative, and they
can be replaced by edges with weight y = −t ±1 (and therefore dual weight x = −t ∓1 ):
−t −t −1
7−→ 7−→
checkerboard positive checkerboard negative
It turns out that
hLiK = t u/4 (−t 1/2 − t −1/2 )−v Z(G(~y), q)
where u is the number of checkerboard-positive crossings minus the number of checkerboard-negative
crossings, and v is the number of black regions of L.
Proof of Theorem 4.2. There is an evident bijection between non-crossing partitions of n points and
planar matchings of 2n points. Each part of the partition is represented by a polygon with some k sides,
and we can replace it by k arcs:
←→
We will use the same symbol m to denote either the partition or its corresponding matching. The vectors
|miP are a basis of W (n)P , while the vectors |miK are a basis of W (2n)K . We identify them using the
formula
|miP = (−t 1/2 − t −1/2 )c(m) |miK
where c(m) is the number of components of m as a partition, or the number of black regions of m read as
a planar matching.
With this choice of isomorphism, we claim that if R j is the jth left half-twist operator on W (n)K in
the Jones braid representation, then
S(−t) j = (t 1/4 + t −3/4 )R2 j−1 , and
P(−t) j = −t 1/4 R2 j .
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 210
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
The first of these relations is established as follows. We do the calculation in terms of kets; the reader can
check that it works the same way with operators. We obtain:
(−t) E −t −1 E
S(−t) = =
EP P
E
−1
= − (1 + t )
P P
E E
1/2 −1/2 −1
= −(t + t ) − (1 + t )
K K
E
= (t 1/4 + t −3/4 )
K
using (4.3) and (3.1). (The extra factor of −t 1/2 − t −1/2 in the first term arises from the change of basis
from Potts skeins to Kauffman skeins.) The calculation for P(−t) is similar.
Since the braid generators are proportional to the parallel and series operators, the latter generate the
same projective representation.
4.3 Parallel-series compositions
The statement of Theorem 1.3 only allows graphs with the same weight y for every edge. If we want to use
the gates P(y) and S(x) universal quantum computation, this is not even enough for the Solovay-Kitaev
theorem, if we don’t have the inverses of these two gates. In this section we use a technique used by
Goldberg and Jerrum in which edges are replaced by subgraph gadgets, to approximately allow any real
weight y for any edge [15]. This will give let use the Solovay-Kitaev theorem by the relations
P(y)−1 = P(y−1 ) and S(x)−1 ∝ S(x−1 )
which follow from (4.4) below. It will also make it easier to prove the dense generation criterion that is
also needed for the Solovay-Kitaev theorem.
The technique is as follows: If a graph G(~y) has two parallel edges with weight y1 and y2 , then they
are equivalent to a single edge with weight y1 y2 . Meanwhile, if G(~y) has two edges in series with dual
weight x1 and x2 , they are equivalent (up to changing the Potts value Z by a constant factor) to one edge
with weight x1 x2 . In other words,
P(y1 y2 ) = P(y1 )P(y2 ) and S(x1 x2 ) ∝ S(x1 )S(x2 ) . (4.4)
These transformations are called shift operations; they are also called compositions and implemented
weights. Note that series and parallel compositions preserve the value of q, and they preserve planarity.
Lemma 4.3. Consider graphs with the Potts model with q colors and with a single weight y which is
an FPTEAS number. Suppose that q > 4 and that x, y < 0. Then all weights y0 6= 1 that are FPTEAS
numbers, can be FPTEAS approximated by parallel and series compositions.
Lemma 4.3 is a refinement of one proved by Goldberg and Jerrum [15]. (The refinement is that they
did not establish is the FPTEAS property.)
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 211
G REG K UPERBERG
y
q=8
q=5
1
−1 0 1 x
−1
q=8
q=5
Figure 1: The Tutte plane with level curves of q.
Proof. Figure 1 shows a diagram of curves in the x-y plane (the Tutte plane) with constant values of q.
Given that q > 4 and x, y < 0, we must have either that x < −1 or y < −1 or both. Parallel composition
has the same effect on y as series composition has on x, and vice versa; so we can assume without loss of
generality that x < −1. As a first step, we can create the dual weight xn with a series composition with n
edges. This creates a sequence of weights yn that satisfies the estimate
log(yn ) = qx−n (1 + o(1))
as n → ∞. Now suppose that y0 > 1 is some other weight. We claim that we can efficiently approximate
y0 as a product of weights y2n . Equivalently, we claim that we can efficiently approximate log(y0 ) as a
sum of terms log(y2n ):
log(y0 ) = log(y2n1 ) + log(y2n2 ) + · · · .
This can be viewed as a bin packing problem, because both log(y0 ) and each term log(y2n ) are positive.
The claim is established by using a greedy bin-packing algorithm. I. e., choose each term log(y2nk ) to be
as large as possible, but so that the partial sum does not exceed log(y0 ). Since the terms log(y2n ) decrease
exponentially (and no faster), and since the graph complexity of each term is linear in n, the result is a
parallel-series composition which is an FPTEAS for the weight y0 .
The same bin-packing argument works for 0 < y0 < 1, using the odd-numbered weights y2n+1 . So
every desired weight y0 > 0 has an FPTEAS-strength parallel-series composition. In addition, we also
have the original weight y < 0, so the values of y0 > 0, y0 = y00 y with y00 > 0, and y itself reach every desired
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 212
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
value other than y0 = 0. Since we also want the remaining weight y0 = 0, we can at this point achieve its
dual weight x0 = 1 − q with a series composition with the dual weights x0 = −1 and x0 = q − 1.
4.4 Densely generating PSL(W (n)P )
In this section, we will prove that if q > 4, then there are FPTEAS numbers x, y1 , and y2 , such that the
gates S(x), P(y1 ), and P(y2 ) and their inverses densely generate the group PSL(W (n)P ) for any n ≥ 2.
Lemma 4.3 says that we can obtain any such gates in FPTEAS approximation using subgraph gadgets.
Our argument borrows from the author’s previous work [28] and makes crucial use of the Zariski topology
on the group PSL(W (n)P ).
The Zariski topology on an algebraic group (or any algebraic variety) is by definition the topology in
which the closed sets are solutions to polynomial equations. The Zariski topology on Rn or on PSL(n, R)
is much coarser than the standard topology, which in this context is called the analytic topology. It is
easier for a subgroup or a subset to be Zariski dense, and it is easier to prove Zariski denseness in this
algebraically adapted topology. In particular:
Theorem 4.4 ([28, Cor. 1.2]). Let n > 1 be an integer and let t > 1 be real. Then the Jones braid
representation of B2n acting on W (2n)K = X(2n)K with parameter t is Zariski dense in PSL(X(2n)).
On the other hand, in some circumstances we can get the best of both worlds:
Proposition 4.5 ([28, §3]). A subgroup Γ of a connected, simple Lie group G is analytically dense if and
only if it is both analytically indiscrete and Zariski dense.
(Proposition 4.5 is a baby version of a more famous result known as the Zassenhaus neighborhood
theorem [39, 22].) √
To finish the construction, let q = t + 2 +t −1 , let x = y1 = −t and y2 = t 2 . (The the only requirement
is that y2 should be an irrational power of t with an FPTEAS exponent.) Then the gates P(y1 ) and P(y2 )
generate an indiscrete group by (4.4); their products
√ √
P(−t)a P(t 2 )b = P((−1)at a+ 2b )
for all a, b ∈ Z are a dense subset of all P(y). By Theorem 4.2, the gates S(x) and P(y1 ) acting on
W (n)P = W (2n)K generate the Jones braid representation of B2n . By Theorem 4.4, this group action is
Zariski dense. With the addition of the gate P(y2 ), it is also indiscrete and therefore analytically dense by
Proposition 4.5.
Remark 4.6. A self-contained proof of Theorem 1.3 would be simpler if we applied some of the
techniques involved in Theorem 4.4 directly to the group generated by gates of the form P(y) and S(x).
However, these techniques involve yet another set of mathematical tools that we prefer to relegate to [28].
4.5 Proof of Theorem 1.3
Proof. Following Corollary 3.2 and its proof, let
p(x) > 2−poly(|x|)
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 213
G REG K UPERBERG
be the probability that some polynomial-time quantum algorithm accepts an input x. Then
p(x) = |h0n |C(x)|0n i|2
for some a quantum circuit C(x) that can be generated from x in (classical) polynomial time. We can
use the 2-dimensional skein space W (2)P as a libit, and let |0i = |ψi be the state √
of two dots as in
2
Section 4.2. By Lemma 4.3, we can approximate the gates S(−t), P(−t), and P(t ) and their inverses.
By Section 4.4, these gates densely generate PSL(W (4)P ) ∼ = PSL(14, R) in the case n = 4. Then we can
apply Solovay-Kitaev, Theorem 2.4, to approximately encode the gates of C(x) as a circuit acting on
PSL(W (2n)P ). Then we finalize the circuit with the states h0|, which can also be defined as the state hψ|
of two dots.
The result is a graph G(x) such that the Potts value Z(G(x), q, y) satisfies
p(x) ≈ N(x)|Z(G(x), q, y)|2
where the extra factor N(x) is a polynomial-time computable normalization that depends on the con-
struction of G(x). (The factor of N(x) appears because we are working up a scalar factor in all of
our computations. Note also that the x here is the decision problem input and not the Potts parame-
ter.) It follows that for every c > 1, multiplicative approximation of Z(G(x), q, y) up to a factor of c is
PostBQP-hard, and thus #P-hard.
5 Final remarks and questions
5.1 Other properties of knots
Theorem 1.2 says that value-distinguishing approximation of certain values of the Jones polynomial are
#P-hard even when the link L is taken to be a knot. We conjecture that L could in addition be a prime
knot or even an atoroidal knot. (A prime knot is one which is not a composite of two knots; an atoroidal
knot is one which is not a satellite [9, §2.C].) Maybe other such restrictions on the structure of L could be
imposed. But without a result such as that distinguishing the unknot (say) is hard, it is not feasible to add
arbitrary interesting topological restrictions on L to Theorem 1.2. Maybe recognizing the unknot is in
P or BQP. The Jones polynomial would then be easy to compute for knots that are recognized as the
unknot or recognized as some other specific knots.
In fact, recognizing the unknot is in NP [18], and in coNP assuming the generalized Riemann
hypothesis [29]. Thus, unless the polynomial hierarchy collapses, recognizing the unknot has lower
qualitative computational complexity than approximating the Jones polynomial. (But the Jones polynomial
could still have competitive quantitative complexity, i. e., asymptotic time complexity in a realistic
computational model.)
5.2 Other kinds of approximation
There are many other kinds of partial information about the Jones polynomial without any interesting
complexity bound to our knowledge. Is the degree of the Jones polynomial intractable? Is it intractable to
determine when some value of the Jones polynomial vanishes? What if the Jones polynomial is reduced
mod p for some prime p?
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 214
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
5.3 Denseness may be more than necessary
It is easiest to see that a set of gates is universal for linear computation if they densely generate an
appropriate Lie group. For instance, they might generate PSL(2n , C) if they act on n libits, or PSL(2n , R)
inside it. But dense generation is more than necessary for certain types of universality. For example,
k-libit gates with integer matrices always generate a discrete group, even when acting on n > k libits.
Nonetheless, both the Hadamard and Toffoli gates are proportional to integer gates, and they are universal
for quantum computation. Thus, multiplicative approximation of amplitudes in linear computation with
integer gates is #P-hard. We do not know the right criteria on linear gates to establish #P-hardness results.
5.4 Solovay-Kitaev without inverses
It is a long-standing open problem to generalize the celebrated Solovay-Kitaev theorem to gate sets
that are not closed under inverses. This problem could be peripheral in the context of designing actual
quantum computers or realistic quantum algorithms. However, it could be important for the purpose of
establishing hardness results.
5.5 Morse algorithms may be optimal
It is common practice to compute the Jones polynomial by a strategy known variously as a Morse
algorithm, dynamic programming, a scanline algorithm, or a divide-and-conquer algorithm. (Morse
theory in geometric topology is a theory of analyzing a topological object by dividing it into horizontal
slices.) For a knot in a plat diagram, the strategy is to numerically compute the action of the braid group
on the skein space. This type of algorithm requires simple exponential time and space in the number of
strands of the braid, or for other kinds of knot diagrams, the width of the diagram. This is much better
than a direct recursive evaluation of the Jones polynomial using a finite set of skein relations; the time
complexity of any such direct algorithm is instead exponential in the number of crossings.
It is natural to wonder whether there are other clever algorithms that can compute the Jones polynomial
even faster. The proof of Theorem 1.2 could be evidence that Morse algorithms are essentially optimal
for many kinds of knot diagrams. In short, if braids are evaluated using the Jones polynomial at the dense
roots of unity of Theorem 1.2, then they are a model of general planar quantum circuits.
In more detail, consider a typical hard search problem based on classical circuits, and an analogous
problem based on quantum circuits. For instance, let (z, w) = C(x, y) be a reversible circuit whose input
(x, y) and output (z, w) are each divided into two registers of equal length. Then it is NP-hard to determine
whether there is a solution to (z, 0) = C(x, 0). We conjecture that there are linear-depth, planar circuits
C for which this problem requires exponential time in |x|, in other words that full cryptography can be
achieved with linear depth, planar circuits.
Using denseness at a non-lattice root of unity and Solovay-Kitaev, Theorem 2.4, this circuit problem
can be encoded in a braid with polynomial overhead. (Again, the Solovay-Kitaev theorem has poly-
logarithmic overhead for BQP, but polynomial overhead for PostBQP.) We conjecture that this extra
polynomial overhead is not essential for hardness. We have in mind that there could be cryptographic
methods to make linear-depth plat diagrams of knots, for which the Jones polynomial requires exponential
time in the bridge number g to estimate at a non-lattice root of unity. (Note that the depth of a braid is not
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 215
G REG K UPERBERG
the same as its length; to calculate the depth, commuting half-twists can be applied in parallel.) Such
conjectures are very difficult to prove unconditionally, because they would imply that #P is not contained
in FP. Nonetheless, if there were a believable theory of cryptography for the Jones representation of
linear-depth braids, then one would also believe that Morse algorithms to compute or estimate the Jones
polynomial are essentially optimal.
References
[1] S COTT A ARONSON: Quantum computing, postselection, and probabilistic polynomial time.
Proc. Royal Soc. A, 461(2063):3473–3482, 2005. Preliminary versions in arXiv and ECCC.
[doi:10.1098/rspa.2005.1546] 185, 187, 194, 198, 199
[2] L EONARD M. A DLEMAN , J ONATHAN D EMARRAIS , AND M ING -D EH A. H UANG: Quantum
computability. SIAM J. Comput., 26(5):1524–1540, 1997. [doi:10.1137/S0097539795293639] 189
[3] D ORIT A HARONOV AND I TAI A RAD: The BQP-hardness of approximating the Jones polynomial.
New J. Phys., 13:035019, 2011. [doi:10.1088/1367-2630/13/3/035019, arXiv:quant-ph/0605181]
184
[4] D ORIT A HARONOV, I TAI A RAD , E LAD E BAN , AND Z EPH L ANDAU: Polynomial quantum
algorithms for additive approximations of the Potts model and other points of the Tutte plane, 2007.
[arXiv:quant-ph/0702008] 185, 189
[5] D ORIT A HARONOV, VAUGHAN J ONES , AND Z EPH L ANDAU: A polynomial quantum algorithm
for approximating the Jones polynomial. Algorithmica, 55(3):395–421, 2009. Preliminary version
in STOC’06. [doi:10.1007/s00453-008-9168-0, arXiv:quant-ph/0511096] 184, 202, 203
[6] E LMAR B ÖHLER , C HRISTIAN G LASSER , AND DANIEL M EISTER: Error-bounded probabilistic
computations between MA and AM. J. Comput. System Sci., 72(6):1043–1076, 2006. Preliminary
version in MFCS’03. [doi:10.1016/j.jcss.2006.05.001] 197
[7] M AGNUS B ORDEWICH , M ICHAEL H. F REEDMAN , L ÁSZLÓ L OVÁSZ , AND D OMINIC W ELSH:
Approximate counting and quantum computation. Combin. Probab. Comput., 14(5-6):737–754,
2005. [doi:10.1017/S0963548305007005, arXiv:0908.2122] 184, 185
[8] R ICHARD P. B RENT: Fast multiple-precision evaluation of elementary functions. J. ACM, 23(2):242–
251, 1976. [doi:10.1145/321941.321944] 187
[9] G ERHARD B URDE AND H EINER Z IESCHANG: Knots. Volume 5 of De Gruyter Studies in Mathe-
matics. Walter de Gruyter, 1985. 184, 200, 214
[10] S AMUEL R. B USS AND L OUISE H AY: On truth-table reducibility to SAT. Inform. and Comput.,
91(1):86–102, 1991. [doi:10.1016/0890-5401(91)90075-D] 195
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 216
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
[11] M ICHAEL H. F REEDMAN , A LEXEI K ITAEV, AND Z HENGHAN WANG: Simulation of topo-
logical field theories by quantum computers. Comm. Math. Phys., 227(3):587–603, 2002.
[doi:10.1007/s002200200635, arXiv:quant-ph/0001071] 184
[12] M ICHAEL H. F REEDMAN , M ICHAEL J. L ARSEN , AND Z HENGHAN WANG: A modular func-
tor which is universal for quantum computation. Comm. Math. Phys., 227(3):605–622, 2002.
[doi:10.1007/s002200200645, arXiv:quant-ph/0001108] 204
[13] M ICHAEL H. F REEDMAN , M ICHAEL J. L ARSEN , AND Z HENGHAN WANG: The two-eigenvalue
problem and density of Jones representation of braid groups. Comm. Math. Phys., 228(1):177–199,
2002. [doi:10.1007/s002200200636, arXiv:math/0103200] 184, 202, 204
[14] I GOR F RENKEL AND M IKHAIL K HOVANOV: Canonical bases in tensor products and graphical
calculus for Uq (sl2 ). Duke Math. J., 87(3):409–480, 1995. [doi:10.1215/S0012-7094-97-08715-9]
202
[15] L ESLIE A NN G OLDBERG AND M ARK J ERRUM: Inapproximability of the Tutte polyno-
mial. Inform. and Comput., 206(7):908–929, 2008. Preliminary version in STOC’07.
[doi:10.1016/j.ic.2008.04.003, arXiv:cs/0605140] 185, 211
[16] L ESLIE A NN G OLDBERG AND M ARK J ERRUM: Inapproximability of the Tutte polynomial of a
planar graph. Comput. Complexity, 21(4):605–642, 2012. [doi:10.1007/s00037-012-0046-4] 186
[17] Y ENJO H AN , L ANE A. H EMASPAANDRA , AND T HOMAS T HIERAUF: Threshold computation and
cryptographic security. SIAM J. Comput., 26(1):59–78, 1997. Preliminary version in ISAAC’93.
[doi:10.1137/S0097539792240467] 195
[18] J OEL H ASS , J EFFREY C. L AGARIAS , AND N ICHOLAS P IPPENGER: The computational complexity
of knot and link problems. J. ACM, 46(2):185–211, 1999. Preliminary version in FOCS’97.
[doi:10.1145/301970.301971, arXiv:math.GT/9807016] 214
[19] L ANE A. H EMACHANDRA: The strong exponential hierarchy collapses. J. Comput. System Sci.,
39(3):299–322, 1989. Preliminary version in STOC’87. [doi:10.1016/0022-0000(89)90025-1] 195
[20] F RANÇOIS JAEGER , D IRK L. V ERTIGAN , AND D OMINIC W ELSH: On the computational com-
plexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc., 108(1):35–53,
1990. [doi:10.1017/S0305004100068936] 185, 186
[21] VAUGHAN F. R. J ONES: On knot invariants related to some statistical mechanical models. Pacific J.
Math., 137(2):311–334, 1989. Available online at Project Euclid. 209
[22] M ICHAEL K APOVICH: Hyperbolic Manifolds and Discrete Groups. Modern Birkhäuser Classics.
Birkhäuser, 2010. Available online at Springer. 213
[23] C HRISTIAN K ASSEL: Quantum Groups. Volume 155 of Graduate Texts in Mathematics. Springer,
1995. 202
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 217
G REG K UPERBERG
[24] L OUIS H. K AUFFMAN: Spin networks and knot polynomials. Internat. J. Modern Phys. A, 5(1):93–
115, 1990. [doi:10.1142/S0217751X90000039] 200
[25] L OUIS H. K AUFFMAN AND S OSTENES L. L INS: Temperley-Lieb Recoupling Theory and Invariants
of 3-Manifolds. Annals of Math. Studies. Princeton Univ. Press, 1994. 202
[26] A LEXANDER A. K IRILLOV, J R .: On an inner product in modular tensor categories. J. Amer. Math.
Soc., 9(4):1135–1169, 1996. [doi:10.1090/S0894-0347-96-00210-X, arXiv:q-alg/9508017] 202
[27] G REG K UPERBERG: Spiders for rank 2 Lie algebras. Comm. Math. Phys., 180(1):109–151, 1996.
[doi:10.1007/BF02101184, arXiv:q-alg/9712003] 200
[28] G REG K UPERBERG: Denseness and Zariski denseness of Jones braid representations. Geom. Topol.,
15(1):11–39, 2011. [doi:10.2140/gt.2011.15.11, arXiv:0909.1881] 213
[29] G REG K UPERBERG: Knottedness is in NP, modulo GRH. Adv. Math., 256:493–506, 2014.
[doi:10.1016/j.aim.2014.01.007, arXiv:1112.0845] 214
[30] M ICHAEL A. N IELSEN AND I SAAC L. C HUANG: Quantum Computation and Quantum Information.
Cambridge Univ. Press, 2000. 185, 186, 189, 190
[31] PAUL -É MILE PARADAN: Symmetric spaces of the non-compact type: Lie groups. In Géométries à
Courbure Négative ou Nulle, Groupes Discrets et Rigidités, volume 18 of Sémin. Congr., pp. 39–76.
Soc. Math. France, Paris, 2009. Available on HAL archives ouvertes. 189, 193
[32] E RIC C. ROWELL: Two paradigms for topological quantum computation. In Adv. in
Quantum Comput., volume 482 of Contemp. Math., pp. 165–177. Amer. Math. Soc., 2009.
[doi:10.1090/conm/482/09418, arXiv:0803.1258]
[33] RONEN S HALTIEL AND C HRISTOPHER U MANS: Pseudorandomness for approximate count-
ing and sampling. Comput. Complexity, 15(4):298–341, 2006. Preliminary version in CCC’05.
[doi:10.1007/s00037-007-0218-9] 195
[34] S EINOSUKE T ODA: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–
877, 1991. Preliminary version in FOCS’89. [doi:10.1137/0220053] 187
[35] V EERAVALLI S ESHADRI VARADARAJAN: Lie Groups, Lie Algebras, and Their Representations.
Volume 102 of Graduate Texts in Mathematics. Springer, 1984. Reprint of the 1974 edition. 189,
190
[36] D IRK L. V ERTIGAN: The computational complexity of Tutte invariants for planar graphs. SIAM J.
Comput., 35(3):690–712, 2005. [doi:10.1137/S0097539704446797] 185
[37] M IKHAIL N. V YALY Ĭ: QMA = PP implies that PP contains PH. Electron. Colloq. on Comput.
Complexity (ECCC), TR03-021, 2003. 197, 198
[38] H ANS W ENZL: C∗ tensor categories from quantum groups. J. Amer. Math. Soc., 11(2):261–282,
1998. [doi:10.1090/S0894-0347-98-00253-7] 202
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 218
H OW H ARD I S I T TO A PPROXIMATE THE J ONES P OLYNOMIAL ?
[39] H ANS Z ASSENHAUS: Beweis eines Satzes über diskrete Gruppen. Abh. Math. Sem. Hamburg,
12(1):289–312, 1937. [doi:10.1007/BF02948950] 213
[40] The Complexity Zoo. https://complexityzoo.uwaterloo.ca. 184, 186, 187
AUTHOR
Greg Kuperberg
Professor
University of California, Davis
greg math ucdavis edu
http://www.math.ucdavis.edu/~greg
ABOUT THE AUTHOR
G REG K UPERBERG graduated from Harvard University in 1987 and received a Ph. D. in
mathematics from UC Berkeley in 1991. His advisor was Andrew Casson. He joined the
mathematics department at UC Davis in 1996. He believes that a day without bicycling
is not a perfect day.
T HEORY OF C OMPUTING, Volume 11 (6), 2015, pp. 183–219 219