Aharonov–Jones–Landau algorithm explained

In computer science, the Aharonov–Jones–Landau algorithm is an efficient quantum algorithm for obtaining an additive approximation of the Jones polynomial of a given link at an arbitrary root of unity. Finding a multiplicative approximation is a

  1. P
-hard problem,[1] so a better approximation is considered unlikely. However, it is known that computing an additive approximation of the Jones polynomial is a BQP-complete problem.[2]

The algorithm was published in 2009 in a paper written by Dorit Aharonov, Vaughan Jones and Zeph Landau.

History

In the early 2000s, a series of papers by Michael Freedman, Alexei Kitaev, Michael J. Larsen, and Zhenghan Wang demonstrated that topological quantum computers based on topological quantum field theory had the same computational power as quantum circuits. In particular, they showed that the braiding of Fibonacci anyons could be used to approximate the Jones polynomial evaluated at a primitive 5th root of unity. They then showed that this problem was BQP-complete.

Putting these results together, this implies that there is a polynomial length quantum circuit which approximates the Jones polynomial at 5th roots of unity. This algorithm was completely inaccessible to ordinary quantum computer scientists, however, since the papers by Freedman-Kitaev-Larsen-Wang used heavy machinery from manifold topology. The contribution of Aharanov-Jones-Landau was to simplify this complicated implicit algorithm in such a way that it would be palatable to a larger audience.

The Markov trace

The first idea behind the algorithm is to find a more tractable description for the operation of evaluating the Jones polynomial. This is done by means of the Markov trace.

TLn(d)

as follows: given a

T\inTLn(d)

which is a single Kauffman diagram, let

tr(T)=da-n

where

a

is the number of loops attained by identifying each point in the bottom of

T

's Kauffman diagram with the corresponding point on top. This extends linearly to all of

TLn(d)

.

The Markov trace is a trace operator in the sense that

\operatorname{tr}(1)=1

and

\operatorname{tr}(XY)=\operatorname{tr}(YX)

for any

X,Y\inTLn(d)

. It also has the additional property that if

X

is a Kauffman diagram whose rightmost strand goes straight up then

\operatorname{tr}(XEn-1)=

1
d

\operatorname{tr}(X)

.

A useful fact exploited by the AJL algorithm is that the Markov trace is the unique trace operator on

TLn(d)

with that property.[3]

Representing

Bn

in

TLn(d)

For a complex number

A

we define the map

\rhoA:Bn\toTLn(d)

via

\sigmai\mapsto

-1
AE
i+A

I

. It follows by direct calculation that if

A

satisfies that

d=-A2-A-2

then

\rhoA

is a representation.

Given a braind

B\inBn

let

Btr

be the link attained by identifying the bottom of the diagram with its top like in the definition of a Markov trace, and let
V
Btr
be the result link's Jones polynomial. The following relation holds:
V
Btr

(A-4

3w(Btr)
)=(-A)

dn-1\operatorname{tr}(\rhoA(B))

where

w

is the writhe. As the writhe can be easily calculated classically, this reduces the problem of approximating the Jones polynomial to that of approximating the Markov trace.

The path model representation of

TLn(d)

We wish to construct a complex representation

\tau

of

TLn(d)

such that the representation

\tau\circ\rhoA

of

Bn

will be unitary. We also wish that our representation will have a straightforward encoding into qubits.

Let

Qn,k=\left\{q\in\left\{1,\ldots,k-1\right\}n+1\midq(1)=1,\left|q(i)-q(i+1)\right|=1\right\}

and let

Vn,k=C[Qn,k]

be the vector space which has

Qn,k

as an orthonormal basis.

We choose define a linear map

\tau:TLn(d)\toVn,k

by defining it on the base of generators

\{1,E1,\ldots,En-1\}

. To do so we need to define the matrix element

\tau(Ei)q,q'

for any

q,q'\inQn,k

.

We say that

q

and

q'

are 'compatible' if

q(j)=q'(j)

for any

j\nei+1

and

q(i)=q(i+2)

. Geometrically this means that if we put

q

and

q'

below and above the Kauffman diagram in the gaps between the strands then no connectivity component will touch two gaps which are labeled by different numbers.

If

q

and

q'

are incompatible set

\tau(Ei)q,q'=0

. Else, let

l

be either

q(i)

or

q(i+2)

(at least one of these number must be defined, and if both are defined they must be equal) and set

\tau\left(Ei\right)q,q'=\begin{cases}

λl+1
λl

&q\left(i+1\right)=q'(i+1)>l\\

\sqrt{λl-1λl+1
} & q\left(i+1\right)\ne q'(i+1)\\\frac & q\left(i+1\right)=q'(i+1)

where

λl=\sin(\pil/k)

. Finally set

d=2\cos(\pi/k)

.

This representation, known as the path model representation, induces a unitary representation of the braid group.[4] [5] Moreover, it holds that

d=-A2-A-2

for

A=ie-i\pi/2k

.

This implies that if we could approximate the Markov trace in this representation this will allow us to approximate the Jones polynomial in

A-4=e2\pi

.

A quantum version of the path model representation

In order to be able to act on elements of the path model representation by means of quantum circuits, we need to encode the elements of

Qn,k

into qubits in a way which allows us to easily describe the images of the generators

Ei

.

We represent each path as a sequence of moves, where

0

indicates a move to the right and

1

indicates a move to the left. For example, the path

1,2,3,2

will be represented by the state

\left|001\right\rangle

.

This encodes

C[Qn,k]

as a subspace of the state space on

k-1

qubits.

We define the operators

\varphii

within this subspace we define

\Phii\left|w\right\rangle=\begin{cases} 0&wi=wi+1\\

λ
z
wi
-\left(-1\right)
i
λ
zi

\left|w\right\rangle+

\sqrt{λ
λ
zi+1
zi-1
}X_X_\left|w\right\rangle & w_\ne w_\end

where

Xi

is the Pauli matrix flipping the

i

th bit and

zi

is the position of the path represented by

\left|w\right\rangle

after

i

steps.

We arbitrarily extend

\varphii

to be the identity on the rest of the space.

We note that mapping

Ei\mapsto\varphii

retains all the properties of the path model representation. Specifically, it induces a unitary representation

\varphi

of

Bn

. It is fairly straightforward to show that

\varphii

can be implemented by

poly\left(n,k\right)

gates, so it follows that

\varphi(B)

can be implemented for any

B\inBn

using

poly\left(m,n,k\right)

where

m

is the number of crossings in

B

.

A quantum version of the Markov trace

The benefit of this construction is that it gives us a way to represent the Markov trace in a way which can be easily approximated.

Let

l{H}n,k

be the subspace of paths we described in the previous clause, and let

l{H}n,k,l

be the subspace spanned by basis elements which represent walks which end on the

l

-th position.

Note that each of the operators

\varphii

fix

l{H}n,k,l

setwise, and so this holds for any

W\inIm\Phi\left(TLn\left(d\right)\right)

, hence the operator

W|l:=W|l{Hn,k,l

} is well defined.

We define the following operator:

\operatorname{Tr}n\left(W\right)=

1
N
k-1
\sum
l=1

λl\operatorname{Tr}\left(W|l\right)

where

\operatorname{Tr}

is the usual matrix trace.

It turns out that this operator is a trace operator with the Markov property, so by the theorem stated above it has to be the Markov trace. This finishes the required reductions as it establishes that to approximate the Jones polynomial it suffices to approximate

\operatorname{Tr}n

.

The algorithm

algorithm Approximate-Jones-Trace-Closure is input

B\inBn

with

m

crossings An integer

k

output a number

s

such that
|s-V
Btr

(e2\pi/k)|<1/poly(n,k,m)

with all but exponentially small probability repeat for

j=1

to

poly(n,m,k)

1. Pick a random

l\in\{1,\ldots,k-1\}

such that the probability to choose a particular

l

is proportional to

λl

2. Randomly pick

q\inQn,k

which ends in position

l

3. Using the Hadamard test create a random variable

xj

with

E\left[xj\right]=l{Re}\left\langle\alpha\midQ\left(B\right)\mid\beta\right\rangle

Do the same to create

yj

with

E\left[yj\right]=l{Im}\left\langle\alpha\midQ\left(B\right)\mid\beta\right\rangle

let

r

be the average of

xj+iyj

return
3w(Btr)
(-A)

dn-1r

Note that the parameter

d

used in the algorithm depends on

k

.

The correctness of this algorithm is established by applying the Hoeffding bound to

xj

and

yj

separately.

References

  1. D. Aharonov, V. Jones, Z. Landau - A Polynomial Quantum Algorithm for Approximating the Jones Polynomial

Notes and References

  1. Kuperberg . Greg . 2009 . How hard is it to approximate the Jones polynomial? . 0908.0512 .
  2. Michael . Freedman . Michael . Larsen . Zhenghan . Wang . 2000 . A modular functor which is universal for quantum computation . quant-ph/0001108 .
  3. V.F.R . Jones . Index for subfactors . Invent Math . 1 . 72 . 1983 . 10.1007/BF01389127. 1983InMat..72....1J .
  4. V.F.R . Jones . A polynomial invariant for knots via von Neumann algebras . Bull. Amer. Math. Soc. . 12 . 1985 . 103–111 . 10.1090/s0273-0979-1985-15304-2. free .
  5. V.F.R . Jones . Braid groups, Hecke Algebras and type II factors. Geometric methods in Operator Algebras . 123 . 1986 . 242-273 .