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
-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.
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 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)
T\inTLn(d)
tr(T)=da-n
a
T
TLn(d)
The Markov trace is a trace operator in the sense that
\operatorname{tr}(1)=1
\operatorname{tr}(XY)=\operatorname{tr}(YX)
X,Y\inTLn(d)
X
\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)
Bn
TLn(d)
For a complex number
A
\rhoA:Bn\toTLn(d)
\sigmai\mapsto
-1 | |
AE | |
i+A |
I
A
d=-A2-A-2
\rhoA
Given a braind
B\inBn
Btr
V | |
Btr |
V | |
Btr |
(A-4
3w(Btr) | |
)=(-A) |
dn-1\operatorname{tr}(\rhoA(B))
where
w
TLn(d)
We wish to construct a complex representation
\tau
TLn(d)
\tau\circ\rhoA
Bn
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\}
Vn,k=C[Qn,k]
Qn,k
We choose define a linear map
\tau:TLn(d)\toVn,k
\{1,E1,\ldots,En-1\}
\tau(Ei)q,q'
q,q'\inQn,k
We say that
q
q'
q(j)=q'(j)
j\nei+1
q(i)=q(i+2)
q
q'
If
q
q'
\tau(Ei)q,q'=0
l
q(i)
q(i+2)
\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 | |
where
λl=\sin(\pil/k)
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
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
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
Ei
We represent each path as a sequence of moves, where
0
1
1,2,3,2
\left|001\right\rangle
This encodes
C[Qn,k]
k-1
We define the operators
\varphii
\Phii\left|w\right\rangle=\begin{cases} 0&wi=wi+1\\
| |||||||||||||||
|
\left|w\right\rangle+
| |||||||||||
where
Xi
i
zi
\left|w\right\rangle
i
We arbitrarily extend
\varphii
We note that mapping
Ei\mapsto\varphii
\varphi
Bn
\varphii
poly\left(n,k\right)
\varphi(B)
B\inBn
poly\left(m,n,k\right)
m
B
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
l{H}n,k,l
l
Note that each of the operators
\varphii
l{H}n,k,l
W\inIm\Phi\left(TLn\left(d\right)\right)
W|l:=W|l{Hn,k,l
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}
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
algorithm Approximate-Jones-Trace-Closure is input
B\inBn
m
k
s
|s-V | |
Btr |
(e2\pi/k)|<1/poly(n,k,m)
j=1
poly(n,m,k)
l\in\{1,\ldots,k-1\}
l
λl
q\inQn,k
l
xj
E\left[xj\right]=l{Re}\left\langle\alpha\midQ\left(B\right)\mid\beta\right\rangle
yj
E\left[yj\right]=l{Im}\left\langle\alpha\midQ\left(B\right)\mid\beta\right\rangle
r
xj+iyj
3w(Btr) | |
(-A) |
dn-1r
Note that the parameter
d
k
The correctness of this algorithm is established by applying the Hoeffding bound to
xj
yj