How Hard Is It to Approximate the Jones Polynomial?

by Greg Kuperberg

Theory of Computing, Volume 11(6), pp. 183-219, 2015

Bibliography with links to cited articles

[1]   Scott Aaronson: Quantum computing, postselection, and probabilistic polynomial time. Proc. Royal Soc. A, 461(2063):3473–3482, 2005. Preliminary versions in arXiv and ECCC. [doi:10.1098/rspa.2005.1546]

[2]   Leonard M. Adleman, Jonathan Demarrais, and Ming-Deh A. Huang: Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997. [doi:10.1137/S0097539795293639]

[3]   Dorit Aharonov and Itai Arad: The BQP-hardness of approximating the Jones polynomial. New J. Phys., 13:035019, 2011. [doi:10.1088/1367-2630/13/3/035019, arXiv:quant-ph/0605181]

[4]   Dorit Aharonov, Itai Arad, Elad Eban, and Zeph Landau: Polynomial quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane, 2007. [arXiv:quant-ph/0702008]

[5]   Dorit Aharonov, Vaughan Jones, and Zeph Landau: A polynomial quantum algorithm for approximating the Jones polynomial. Algorithmica, 55(3):395–421, 2009. Preliminary version in STOC’06. [doi:10.1007/s00453-008-9168-0, arXiv:quant-ph/0511096]

[6]   Elmar Böhler, Christian Glaßer, and Daniel Meister: Error-bounded probabilistic computations between MA and AM. J. Comput. System Sci., 72(6):1043–1076, 2006. Preliminary version in MFCS’03. [doi:10.1016/j.jcss.2006.05.001]

[7]   Magnus Bordewich, Michael H. Freedman, László Lovász, and Dominic Welsh: Approximate counting and quantum computation. Combin. Probab. Comput., 14(5-6):737–754, 2005. [doi:10.1017/S0963548305007005, arXiv:0908.2122]

[8]   Richard P. Brent: Fast multiple-precision evaluation of elementary functions. J. ACM, 23(2):242–251, 1976. [doi:10.1145/321941.321944]

[9]   Gerhard Burde and Heiner Zieschang: Knots. Volume 5 of De Gruyter Studies in Mathematics. Walter de Gruyter, 1985.

[10]   Samuel R. Buss and Louise Hay: On truth-table reducibility to SAT. Inform. and Comput., 91(1):86–102, 1991. [doi:10.1016/0890-5401(91)90075-D]

[11]   Michael H. Freedman, Alexei Kitaev, and Zhenghan Wang: Simulation of topological field theories by quantum computers. Comm. Math. Phys., 227(3):587–603, 2002. [doi:10.1007/s002200200635, arXiv:quant-ph/0001071]

[12]   Michael H. Freedman, Michael J. Larsen, and Zhenghan Wang: A modular functor which is universal for quantum computation. Comm. Math. Phys., 227(3):605–622, 2002. [doi:10.1007/s002200200645, arXiv:quant-ph/0001108]

[13]   Michael H. Freedman, Michael J. Larsen, and Zhenghan Wang: The two-eigenvalue problem and density of Jones representation of braid groups. Comm. Math. Phys., 228(1):177–199, 2002. [doi:10.1007/s002200200636, arXiv:math/0103200]

[14]   Igor Frenkel and Mikhail Khovanov: Canonical bases in tensor products and graphical calculus for Uq(sl2). Duke Math. J., 87(3):409–480, 1995. [doi:10.1215/S0012-7094-97-08715-9]

[15]   Leslie Ann Goldberg and Mark Jerrum: Inapproximability of the Tutte polynomial. Inform. and Comput., 206(7):908–929, 2008. Preliminary version in STOC’07. [doi:10.1016/j.ic.2008.04.003, arXiv:cs/0605140]

[16]   Leslie Ann Goldberg and Mark Jerrum: Inapproximability of the Tutte polynomial of a planar graph. Comput. Complexity, 21(4):605–642, 2012. [doi:10.1007/s00037-012-0046-4]

[17]   Yenjo Han, Lane A. Hemaspaandra, and Thomas Thierauf: Threshold computation and cryptographic security. SIAM J. Comput., 26(1):59–78, 1997. Preliminary version in ISAAC’93. [doi:10.1137/S0097539792240467]

[18]   Joel Hass, Jeffrey C. Lagarias, and Nicholas Pippenger: The computational complexity of knot and link problems. J. ACM, 46(2):185–211, 1999. Preliminary version in FOCS’97. [doi:10.1145/301970.301971, arXiv:math.GT/9807016]

[19]   Lane A. Hemachandra: The strong exponential hierarchy collapses. J. Comput. System Sci., 39(3):299–322, 1989. Preliminary version in STOC’87. [doi:10.1016/0022-0000(89)90025-1]

[20]   François Jaeger, Dirk L. Vertigan, and Dominic Welsh: On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc., 108(1):35–53, 1990. [doi:10.1017/S0305004100068936]

[21]   Vaughan F. R. Jones: On knot invariants related to some statistical mechanical models. Pacific J. Math., 137(2):311–334, 1989. Available online at Project Euclid.

[22]   Michael Kapovich: Hyperbolic Manifolds and Discrete Groups. Modern Birkhäuser Classics. Birkhäuser, 2010. Available online at Springer.

[23]   Christian Kassel: Quantum Groups. Volume 155 of Graduate Texts in Mathematics. Springer, 1995.

[24]   Louis H. Kauffman: Spin networks and knot polynomials. Internat. J. Modern Phys. A, 5(1):93–115, 1990. [doi:10.1142/S0217751X90000039]

[25]   Louis H. Kauffman and Sostenes L. Lins: Temperley-Lieb Recoupling Theory and Invariants of 3-Manifolds. Annals of Math. Studies. Princeton Univ. Press, 1994.

[26]   Alexander A. Kirillov, Jr.: On an inner product in modular tensor categories. J. Amer. Math. Soc., 9(4):1135–1169, 1996. [doi:10.1090/S0894-0347-96-00210-X, arXiv:q-alg/9508017]

[27]   Greg Kuperberg: Spiders for rank 2 Lie algebras. Comm. Math. Phys., 180(1):109–151, 1996. [doi:10.1007/BF02101184, arXiv:q-alg/9712003]

[28]   Greg Kuperberg: Denseness and Zariski denseness of Jones braid representations. Geom. Topol., 15(1):11–39, 2011. [doi:10.2140/gt.2011.15.11, arXiv:0909.1881]

[29]   Greg Kuperberg: Knottedness is in NP, modulo GRH. Adv. Math., 256:493–506, 2014. [doi:10.1016/j.aim.2014.01.007, arXiv:1112.0845]

[30]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge Univ. Press, 2000.

[31]   Paul-Émile Paradan: Symmetric spaces of the non-compact type: Lie groups. In Géométries à Courbure Négative ou Nulle, Groupes Discrets et Rigidités, volume 18 of Sémin. Congr., pp. 39–76. Soc. Math. France, Paris, 2009. Available on HAL archives ouvertes.

[32]   Eric C. Rowell: Two paradigms for topological quantum computation. In Adv. in Quantum Comput., volume 482 of Contemp. Math., pp. 165–177. Amer. Math. Soc., 2009. [doi:10.1090/conm/482/09418, arXiv:0803.1258]

[33]   Ronen Shaltiel and Christopher Umans: Pseudorandomness for approximate counting and sampling. Comput. Complexity, 15(4):298–341, 2006. Preliminary version in CCC’05. [doi:10.1007/s00037-007-0218-9]

[34]   Seinosuke Toda: PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865–877, 1991. Preliminary version in FOCS’89. [doi:10.1137/0220053]

[35]   Veeravalli Seshadri Varadarajan: Lie Groups, Lie Algebras, and Their Representations. Volume 102 of Graduate Texts in Mathematics. Springer, 1984. Reprint of the 1974 edition.

[36]   Dirk L. Vertigan: The computational complexity of Tutte invariants for planar graphs. SIAM J. Comput., 35(3):690–712, 2005. [doi:10.1137/S0097539704446797]

[37]   Mikhail N. Vyalyĭ: QMA = PP implies that PP contains PH. Electron. Colloq. on Comput. Complexity (ECCC), TR03-021, 2003.

[38]   Hans Wenzl: C* tensor categories from quantum groups. J. Amer. Math. Soc., 11(2):261–282, 1998. [doi:10.1090/S0894-0347-98-00253-7]

[39]   Hans Zassenhaus: Beweis eines Satzes über diskrete Gruppen. Abh. Math. Sem. Hamburg, 12(1):289–312, 1937. [doi:10.1007/BF02948950]

[40]   The Complexity Zoo. https://complexityzoo.uwaterloo.ca.