The Jones polynomial, discovered in 1984, is an important knot invariant in topology. Among its many connections to various mathematical and physical areas, it is known (due to Witten) to be intimately connected to Topological Quantum Field Theory ( sfTQFT{sf{TQFT}} ). The works of Freedman, Kitaev, Larsen and Wang provide an efficient simulation of sfTQFT{sf{TQFT}} by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient (namely, polynomial) quantum algorithm that provides a certain additive approximation of the Jones polynomial at the fifth root of unity, e 2π i/5, and moreover, that this problem is sfBQP{sf{BQP}} -complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results of Freedman et al. are heavily based on sfTQFT{sf{TQFT}} , which makes the algorithm essentially inaccessible to computer scientists. We provide an explicit and simple polynomial quantum algorithm to approximate the Jones polynomial of an n strands braid with m crossings at any primitive root of unity e 2π i/k , where the running time of the algorithm is polynomial in m, n and k. Our algorithm is based, rather than on sfTQFT{sf{TQFT}} , on well known mathematical results (specifically, the path model representation of the braid group and the uniqueness of the Markov trace for the Temperley-Lieb algebra). By the results of Freedman et al., our algorithm solves a sfBQP{sf{BQP}} complete problem.
展开▼