Approximation of the Jones Polynomial
In this chapter, we outline the quantum algorithm to efficiently 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
is a Laurent polynomial
with integer coefficients. Given L and a root of unity q, we wish to compute
the Jones evaluation J(L; q)
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}
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,
Can we compute J(L; q) efficiently? 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
σ as the plat closure of a braid
σ B2n, and q =
Question: What is J(ˆplat; σ q)/[2]n
For CEJr, the relevant complexity class is
class of functions polynomial
time Turing reducible to a function in #P. Since #P is not as well-known as
Previous Page Next Page