Aharonov–Jones–Landau algorithm

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. It should be noted that finding a multiplicative approximation is a #P-hard problem , so a better approximation is considered unlikely. However, it is known that an additive approximation of the Jones polynomial is BQP-complete.

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.

The 'Markov trace' is a trace operator defined on the Temperley-Lieb algebra $TL_{n}(d)$ as such: given a $T\in TL_{n}(d)$ which has a unique Kauffman diagram let $tr(T)=d^{a-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 $TL_{n}(d)$.

The Markov trace is a trace operator in the sense that $tr(1)=1$ and $tr(XY)=tr(YX)$ for any $X,Y\in TL_{n}(d)$. It also has the additional property that if $X$ is a Kauffman diagram whose rightmost strand goes straight up then $tr(XE_{n-1})={\frac {1}{d}}tr(X)$.

A useful fact exploited by the AJL algorithm is that the Markov trace is the unique trace operator on $TL_{n}(d)$ with that property.

Representing $B_{n}$ in $TL_{n}(d)$

For a complex number $A$ we define the map $\rho _{A}:B_{n}\to TL_{n}(d)$ via $\sigma _{i}\mapsto AE_{i}+A^{-1}I$. It follows by direct calculation that if $A$ satisfies that $d=-A^{2}-A^{-2}$ then $\rho_A$ is a representation.

Given a braind $B\in B_{n}$ let $B^{tr}$ 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_{B^{tr}}$ be the result link's Jones polynomial. The following relation holds:

$V_{B^{tr}}(A^{-4})=(-A)^{3w(B^{tr})}d^{n-1}tr(\rho _{A}(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.