CHAPTER 3

Approximation of the Jones Polynomial

In this chapter, we outline the quantum algorithm to eﬃciently approximate

Jones evaluations and discuss their distribution in the plane. The algorithm applies

equally to colored Jones evaluations and, with adequate notation, to all quantum

invariants of links from RFCs.

3.1. Jones evaluation as a computing problem

The Jones polynomial J(L; t) of an oriented link L in

S3

is a Laurent polynomial

of

t±1/2

with integer coeﬃcients. Given L and a root of unity q, we wish to compute

the Jones evaluation J(L; q) ∈

Z[q±1/2]

⊂ C. Since J(L; q) is a partition function of

a unitary topological quantum field theory (TQFT) only when q = e±2πi/r, r ∈ Z+,

we will focus on these special roots of unity.

Computation of J(L; q) is a map

J(L; q): {oriented links L} →

Z[q±1/2]

But computing problems are maps f : {0, 1}∗ → {0, 1}∗, so we must encode the

input L and the output J(L; q) as bit strings. L can be given in many ways, e.g.,

by a link diagram or the plat or trace closure of a braid. Any such presentation

can be encoded as a bit string. Over the basis of Q(q±1/2) given by powers of q1/2,

we may write J(L; q) as a string of integers, which is easily encoded as bit string.

Hence with encodings the computation of J(L; q) is a map

J(L; q): {0,

1}∗

→ {0,

1}∗

Can we compute J(L; q) eﬃciently? The computation can be either quantum me-

chanical or classical. Moreover rather than the exact answer we can ask for an

approximation according to various approximation schemes. Therefore there are

many ways to formulate the computation of the Jones polynomial as a computing

problem. We will study two of them:

(1) Classical exact computation of J(L; q)

• Problem: CEJ

• Instance: An oriented link L, and q = e±2πi/r.

• Question: What is J(L; q) as a bit string?

(2) Quantum approximation of J(L; q)

• Problem: QAJr

• Instance: An unoriented link

ˆplat

σ as the plat closure of a braid

σ ∈ B2n, and q =

e±2πi/r.

• Question: What is J(ˆplat; σ q)/[2]n

2

approximately?

For CEJr, the relevant complexity class is

FP#P—the

class of functions polynomial

time Turing reducible to a function in #P. Since #P is not as well-known as

35

http://dx.doi.org/10.1090/cbms/112/03