Aharonov, Dorit; Jones, Vaughan; Landau, Zeph A polynomial quantum algorithm for approximating the Jones polynomial. (English) Zbl 1301.68129 Kleinberg, Jon M. (ed.), Proceedings of the 38th annual ACM symposium on theory of computing, STOC 2006. Seattle, WA, USA, May 21–23, 2006. New York, NY: ACM Press (ISBN 1-59593-134-1). 427-436 (2006). Cited in 1 ReviewCited in 21 Documents MSC: 68Q12 Quantum algorithms and complexity in the theory of computing 57M27 Invariants of knots and \(3\)-manifolds (MSC2010) 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 68W25 Approximation algorithms 81P68 Quantum computation Keywords:Jones polynomial; Temperley-Lieb algebra; polynomial quantum algorithm; approximation; braids; knots; unitary representation Citations:Zbl 0747.57006; Zbl 1005.11507; Zbl 1019.81008; Zbl 1014.81006 × Cite Format Result Cite Review PDF Full Text: DOI arXiv 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. · JFM 54.0603.03 [3] Artin, E. (1947). Theory of braids. Annals of Mathematics, 48 101-126. · Zbl 0030.17703 [4] Bernstein E and Vazirani U, Quantum complexity theory, SIAM Journal of Computation 26 5 pp 1411-1473 October, 1997 10.1137/S0097539796300921 · Zbl 0895.68042 [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. · Zbl 0891.46035 [7] Bordewich M, Freedman M, Lovasz L, and Welsh D., Approximate counting and Quantum computation, Combinatorics, Probability and Computing, 14, Issue 5-6, pp: 737 – 754, 2005 10.1017/S0963548305007005 · Zbl 1089.68040 [8] A. Childs and R. Cleve and E. Deotto and E. Farhi and S. Gutmann and D. Spielman, Exponential algorithmic speedup by quantum walk, STOC 2003 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 · Zbl 0202.54703 [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. · Zbl 0789.57002 [12] M. Freedman, P/NP and the quantum field computer, Proc. Natl. Acad. Sci., USA, 95, (1998), 98-101 · Zbl 0895.68053 [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 · Zbl 1019.81008 [14] M. H. Freedman, A. Kitaev, Z. Wang Simulation of topological field theories by quantum computers Commun.Math.Phys. 227 (2002) 587-603 · Zbl 1014.81006 [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 · Zbl 1012.81007 [16] F.M. Goodman, P. de la Harpe, and V.F.R. Jones, Coxeter graphs and towers of algebras, Springer-Verlag,1989. · Zbl 0698.46050 [17] S. Hallgren, Polynomial-time quantum algorithms for Pell’s Equation and the principal ideal problem. STOC 2002, pp. 653-658. 10.1145/509907.510001 · Zbl 1192.81069 [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. · Zbl 0747.57006 [19] Mark Jerrum, Alistair Sinclair and Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, STOC 2001, 712-721. 10.1145/380752.380877 · Zbl 1323.68571 [20] V.F.R Jones, A polynomial invariant for knots via von Neumann algebras. Bull. Amer. Math. Soc. 12 (1985), no. 1 103-111. · Zbl 0564.57006 [21] V.F.R. Jones, Index for subfactors, Invent. Math 72 (1983), 1-25. · Zbl 0508.46040 [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 · Zbl 0659.46054 [23] L.Kauffman, State models and the Jones polynomial. Topology 26,(1987),395-407. · Zbl 0622.57004 [24] L. Kauffman, Quantum computing and the Jones polynomial. Quantum computation and information Contemp. Math. 305, 101-137. · Zbl 1063.81032 [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. · JFM 62.0658.01 [27] Neilsen, Chuang, Quantum Computation and Quantum Information, Cambridge press, 2000 · Zbl 1049.81015 [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. · Zbl 0967.92008 [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] Simon D, On the power of quantum computation, SIAM J. Comp., 26, No. 5, pp 1474-1483, October 1997 10.1137/S0097539796298637 · Zbl 0883.03024 [32] P. W. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput. 26(5) 1997, pp. 1484-1509. 10.1137/S0097539795293172 · Zbl 1005.11065 [33] P. Vogel, representation of links by braids: A new algorithm, In Comment. math. Helvetici, 65 (1) pp. 104-113, 1990 · Zbl 0703.57004 [34] J. Watrous, Quantum algorithms for solvable groups. STOC 2001, pp. 60-67. 10.1145/380752.380759 · Zbl 1323.68289 [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. · Zbl 0737.60094 [36] E. Witten, Quantum field theory and the Jones polynomial. Comm. Math. Phys. 121 (1989), no. 3, 351-399. · Zbl 0667.57005 [37] F. Y. Wu, Knot Theory and statistical mechanics, Rev. Mod. Phys. 64, No. 4., October 1992 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.