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 algorithm was published by...

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 is a single 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.

The path model representation of $TL_{n}(d)$

We wish to construct a complex representation $\tau$ of $TL_{n}(d)$ such that the representation $\tau \circ \rho _{A}$ of $B_n$ will be unitary. We also wish that our representation will have a straightforward encoding into qubits.

Let

$Q_{n,k}=\left\{q\in \left\{1,\ldots ,k-1\right\}^{n}\mid q(1)=1,\left|q(i)-q(i+1)\right|=1\right\}$

and let $V_{n,k}=\mathbb {C} [Q_{n,k}]$ be the vector space which has $Q_{n,k}$ as an orthonormal basis.

We choose define a linear map $\tau :TL_{n}(d)\to V_{n,k}$ by defining it on the base of generators $\{1,E_{1},\ldots ,E_{n-1}\}$. To do so we need to define the matrix element $\tau (E_{i})_{q,q'}$ for any $q,q'\in Q_{n,k}$.

We say that $q$ and $q'$ are 'compatible' if $q(j)=q'(j)$ for any $j\neq i+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 (E_{i})_{q,q'}=0$. Else, let $l$ be either $q(i)$ or $q(i+1)$ (at least one of these number must be defined, and if both are defined they must be equal) and set

$\tau \left(E_{i}\right)_{q,q'}={\begin{cases}{\frac {\lambda _{l}}{\lambda _{l-1}}}&q\left(i+1\right)=q'(i+1)>l\\{\frac {\lambda _{l}}{\sqrt {\lambda _{l-1}\lambda _{l+1}}}}&q\left(i+1\right)\neq q'(i+1)\\{\frac {\lambda _{l}}{\lambda _{l-1}}}&q\left(i+1\right)=q'(i+1)<l\end{cases}}$

where $\lambda _{l}=\sin(\pi l/k)$. Finally set $d=2\cos(\pi /k)$.

This turns out to be a unitary representation. Moreover, it holds that $d=-A^{2}-A^{-2}$ for $A=ie^{-\pi /2k}$.