A polynomial quantum algorithm for approximating the Jones polynomial

ABSTRACT

The Jones polynomial, discovered in 1984 [18], is an important knot invariant in topology. Among its many connections to various mathematical and physical areas, it is known (due to Witten [32]) to be intimately connected to Topological Quantum Field Theory (TQFT). The works of Freedman, Kitaev, Larsen and Wang [13, 14] provide an efficient simulation of TQFT by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient quantum algorithm that provides a certain additive approximation of the Jones polynomial at the fifth root of unity, e²π i/5, and moreover, that this problem is BQP-complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results in [13, 14] are heavily based on 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 TQFT, on well known mathematical results (specifically, the path model representation of the braid group and the uniqueness of the Markov trace for the Temperly Lieb algebra). By the results of [14], our algorithm solves a BQP complete problem.The algorithm we provide exhibits a structure which we hope is generalizable to other quantum algorithmic problems. Candidates of particular interest are the approximations of other downwards self-reducible P-hard problems, most notably, the Potts model.

REFERENCES

• 1: Aharonov D. and Arad I., On the BQP-hardness of Approximating the Jones Polynomial, preprint, 2006
• 2: Alexander, J. W. Topological invariants of knots and links. Trans. Amer. Math. Soc. 30 (1928), no. 2, 275--306.
• 3: Artin, E. (1947). Theory of braids. Annals of Mathematics, 48 101--126.
• 4: Ethan Bernstein , Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, v.26 n.5, p.1411-1473, Oct. 1997 [doi>10.1137/S0097539796300921]
• 5: Birman, J. (1974). Braids, links and mapping class groups. Annals of Mathematical Studies, 82.
• 6: D. Bisch and V. Jones, Algebras associated to intermediate subfactors, Invent. Math. 128 (1997), 89--157.
• 7: M. Bordewich , M. Freedman , L. Lovász , D. Welsh, Approximate Counting and Quantum Computation, Combinatorics, Probability and Computing, v.14 n.5-6, p.737-754, November 2005 [doi>10.1017/S0963548305007005]
• 8: Andrew M. Childs , Richard Cleve , Enrico Deotto , Edward Farhi , Sam Gutmann , Daniel A. Spielman, Exponential algorithmic speedup by a quantum walk, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780552]
• 9: J.H. Conway An enumeration of knots and links,and some of their algebraic properties. Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) (1970) 329--358
• 10: W. van Dam and S. Hallgren, Efficient quantum algorithms for shifted quadratic character problems. In quant-ph/0011067.
• 11: B. Ewing and K.C. Millett, A load balanced algorithm for the calculation of the polynomial knot and link invariants. The mathematical heritage of C. F. Gauss, 225--266, World Sci. Publishing, River Edge, NJ, 1991.
• 12: M. Freedman, P/NP and the quantum field computer, Proc. Natl. Acad. Sci., USA, 95, (1998), 98--101
• 13: M. Freedman, A.Kitaev, M. Larsen, Z. Wang, Topological quantum computation. Mathematical challenges of the 21st century (Los Angeles, CA, 2000). Bull. Amer. Math. Soc. (N.S.) 40 (2003), no. 1, 31--38
• 14: M. H. Freedman, A. Kitaev, Z. Wang Simulation of topological field theories by quantum computers Commun.Math.Phys. 227 (2002) 587--603
• 15: M. H. Freedman, M. Larsen, Z. Wang A modular Functor which is universal for quantum computation Commun.Math.Phys. 227 (2002) no. 3, 605--622
• 16: F.M. Goodman, P. de la Harpe, and V.F.R. Jones, Coxeter graphs and towers of algebras, Springer-Verlag,1989.
• 17: Sean Hallgren, Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510001]
• 18: Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc. 108 (1990), no. 1, 35--53.
• 19: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.712-721, July 2001, Hersonissos, Greece [doi>10.1145/380752.380877]
• 20: V.F.R Jones, A polynomial invariant for knots via von Neumann algebras. Bull. Amer. Math. Soc. 12 (1985), no. 1 103--111.
• 21: V.F.R. Jones, Index for subfactors, Invent. Math 72 (1983), 1--25.
• 22: V.F.R. Jones, Braid groups, Hecke Algebras and type II factors, in Geometric methods in Operator Algebras, Pitman Research Notes in Math., 123 (1986), 242--273
• 23: L.Kauffman, State models and the Jones polynomial. Topology 26,(1987),395--407.
• 24: L. Kauffman, Quantum computing and the Jones polynomial. Quantum computation and information Contemp. Math. 305, 101--137.
• 25: G. Kuperberg, A subexponential-time quantum algorithm for the dihedral hidden subgroup problem, arXiv:quant-ph/0302112.
• 26: Markov, A. (1935). Über de freie Aquivalenz geschlossener Zöpfe. Rossiiskaya Akademiya Nauk, Matematicheskii Sbornik, 1, 73--78.
• 27: Quantum computation and quantum information, Cambridge University Press, New York, NY, 2000
• 28: A. Podtelezhnikov, N. Cozzarelli, A. Vologodskii, Equilibrium distributions of topological states in circular DNA: interplay of supercoiling and knotting. Proc. Natl. Acad. Sci. USA 96 (1999), no. 23, 12974--12979.
• 29: Preskill J., Topological quantum computation, Lecture notes for Caltech course 219 in Physics, http://www.theory.caltech.edu/~preskill/ph229/#lecture
• 30: V. Subramaniam, P. Ramadevi, Quantum Computation of Jones' Polynomials, quant-ph/0210095
• 31: Daniel R. Simon, On the Power of Quantum Computation, SIAM Journal on Computing, v.26 n.5, p.1474-1483, Oct. 1997 [doi>10.1137/S0097539796298637]
• 32: Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM Journal on Computing, v.26 n.5, p.1484-1509, Oct. 1997 [doi>10.1137/S0097539795293172]
• 33: P. Vogel, representation of links by braids: A new algorithm, In Comment. math. Helvetici, 65 (1) pp. 104--113, 1990
• 34: John Watrous, Quantum algorithms for solvable groups, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.60-67, July 2001, Hersonissos, Greece [doi>10.1145/380752.380759]
• 35: D. J. A. Welsh, "The Computational Complexity of Some Classical Problems from Statistical Physics," Disorder in Physical Systems, Clarendon Press, Oxford, 1990, pp. 307--321.
• 36: E. Witten, Quantum field theory and the Jones polynomial. Comm. Math. Phys. 121 (1989), no. 3, 351--399.
• 37: F. Y. Wu, Knot Theory and statistical mechanics, Rev. Mod. Phys. 64, No. 4., October 1992

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
Jones Polynomial, Temperley-Lieb, algorithm, approximation, braids, knots, quantum, unitary representation