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. Finding a multiplicative approximation is a #P-hard problem, 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.
The algorithm was published in 2009 in a paper written by Dorit Aharonov, Vaughan Jones and Zeph Landau.
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 formula_1 as follows: given a formula_2 which is a single Kauffman diagram, let formula_3 where formula_4 is the number of loops attained by identifying each point in the bottom of formula_5's Kauffman diagram with the corresponding point on top. This extends linearly to all of formula_1.
The Markov trace is a trace operator in the sense that formula_7 and formula_8 for any formula_9. It also has the additional property that if formula_10 is a Kauffman diagram whose rightmost strand goes straight up then formula_11.
A useful fact exploited by the AJL algorithm is that the Markov trace is the unique trace operator on formula_1 with that property.
Representing formula_13 in formula_1.
For a complex number formula_15 we define the map formula_16 via formula_17. It follows by direct calculation that if formula_15 satisfies that formula_19 then formula_20 is a representation.
Given a braind formula_21 let formula_22 be the link attained by identifying the bottom of the diagram with its top like in the definition of a Markov trace, and let formula_23 be the result link's Jones polynomial. The following relation holds:
where formula_25 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 formula_1.
We wish to construct a complex representation formula_27 of formula_1 such that the representation formula_29 of formula_13 will be unitary. We also wish that our representation will have a straightforward encoding into qubits.
Let 
and let formula_32 be the vector space which has formula_33 as an orthonormal basis.
We choose define a linear map formula_34 by defining it on the base of generators formula_35. To do so we need to define the matrix element formula_36 for any formula_37.
We say that formula_38 and formula_39 are 'compatible' if formula_40 for any formula_41 and formula_42. Geometrically this means that if we put formula_38 and formula_39 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 formula_38 and formula_39 are incompatible set formula_47. Else, let formula_48 be either formula_49 or formula_50 (at least one of these number must be defined, and if both are defined they must be equal) and set
where formula_52. Finally set formula_53.
This representation, known as the "path model representation", induces a unitary representation of the braid group. Moreover, it holds that formula_54 for formula_55.
This implies that if we could approximate the Markov trace in this representation this will allow us to approximate the Jones polynomial in formula_56.
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 formula_33 into qubits in a way which allows us to easily describe the images of the generators formula_58.
We represent each path as a sequence of moves, where formula_59 indicates a move to the right and formula_60 indicates a move to the left. For example, the path formula_61 will be represented by the state formula_62.
This encodes formula_63 as a subspace of the state space on formula_64 qubits.
We define the operators formula_65 within this subspace we define
where formula_67 is the Pauli matrix flipping the formula_68th bit and formula_69 is the position of the path represented by formula_70 after formula_68 steps.
We arbitrarily extend formula_65 to be the identity on the rest of the space.
We note that mapping formula_73 retains all the properties of the path model representation. Specifically, it induces a unitary representation formula_74 of formula_13. It is fairly straightforward to show that formula_65 can be implemented by formula_77 gates, so it follows that formula_78 can be implemented for any formula_21 using formula_80 where formula_81 is the number of crossings in formula_82.
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 formula_83 be the subspace of paths we described in the previous clause, and let formula_84 be the subspace spanned by basis elements which represent walks which end on the formula_48-th position.
Note that each of the operators formula_65 fix formula_84 setwise, and so this holds for any formula_88, hence the operator formula_89 is well defined.
We define the following operator:
where formula_91 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 formula_92.
The algorithm.
 algorithm Approximate-Jones-Trace-Closure is
 input formula_21 with formula_81 crossings
 An integer formula_95
 output a number formula_96 such that formula_97 
 with all but exponentially small probability
 repeat for formula_98 to formula_99
 1. Pick a random formula_100 such that the probability
 to choose a particular formula_48 is proportional to formula_102
 2. Randomly pick formula_103 which ends in position formula_48
 3. Using the Hadamard test create a random variable formula_105 with
 formula_106
 Do the same to create formula_107 with formula_108
 let formula_109 be the average of formula_110
 return formula_111
Note that the parameter formula_112 used in the algorithm depends on formula_95.
The correctness of this algorithm is established by applying the Hoeffding bound to formula_105 and formula_107 separately.