Efficient quantum circuits for approximating the Jones polynomial  (pp0489-0500)
          Yumi Nakajima, Yasuhito Kawano, and Hiroshi Sekigawa
          doi: https://doi.org/10.26421/QIC8.5-8
Abstracts: Freedman, Kitaev, and Wang proved the equivalence between quantum field theory and quantum computation, and consequently showed that the problem of approximating the Jones polynomial (a knot invariant) at the fifth root of unity is BQP-complete. Recently, Aharonov, Jones, and Landau proposed a concrete quantum algorithm, called the AJL algorithm, that approximates the Jones polynomial at the kth root of unity in polynomial time. In this paper, we propose a new method for implementing the AJL algorithm, which improves the performance from O(mn log2 k) to O(mn). Here, n is the number of strands, m is the number of the crossings in a braid. Since, in the AJL algorithm, m and k are assumed to be given as polynomials in n, the difference in the performance between the original implementation and our design is significant if k is a large-degree polynomial.
Key words: quantum circuit, Jones polynomial approximation, the Aharonov-JonesLandau (AJL) algorithm