skip to main content
10.1145/1132516.1132579acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

A polynomial quantum algorithm for approximating the Jones polynomial

Published: 21 May 2006 Publication History

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, e2π 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 e2π 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]
Bernstein E and Vazirani U, Quantum complexity theory, SIAM Journal of Computation 26 5 pp 1411--1473 October, 1997
[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]
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
[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
[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]
S. Hallgren, Polynomial-time quantum algorithms for Pell's Equation and the principal ideal problem. STOC 2002, pp. 653--658.
[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 and Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries, STOC 2001, 712--721.
[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]
Neilsen, Chuang, Quantum Computation and Quantum Information, Cambridge press, 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]
Simon D, On the power of quantum computation, SIAM J. Comp., 26, No. 5, pp 1474--1483, October 1997
[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.
[33]
P. Vogel, representation of links by braids: A new algorithm, In Comment. math. Helvetici, 65 (1) pp. 104--113, 1990
[34]
J. Watrous, Quantum algorithms for solvable groups. STOC 2001, pp. 60--67.
[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

Cited By

View all

Index Terms

  1. A polynomial quantum algorithm for approximating the Jones polynomial

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing
    May 2006
    786 pages
    ISBN:1595931341
    DOI:10.1145/1132516
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 21 May 2006

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. Jones Polynomial
    2. Temperley-Lieb
    3. algorithm
    4. approximation
    5. braids
    6. knots
    7. quantum
    8. unitary representation

    Qualifiers

    • Article

    Conference

    STOC06
    Sponsor:
    STOC06: Symposium on Theory of Computing
    May 21 - 23, 2006
    WA, Seattle, USA

    Acceptance Rates

    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)82
    • Downloads (Last 6 weeks)5
    Reflects downloads up to 27 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)OB IZMERENII TOPOLOGIChESKOGO ZARYaDA ENIONOVProblemy peredači informacii10.31857/S055529232401005460:1(33-40)Online publication date: 15-Dec-2024
    • (2024)Noisy-intermediate-scale quantum power system state estimationiEnergy10.23919/IEN.2024.00193:3(135-141)Online publication date: Sep-2024
    • (2024)Triply-heavy/strange baryons with Cornell potential on a quantum computerThe European Physical Journal A10.1140/epja/s10050-024-01430-360:11Online publication date: 4-Nov-2024
    • (2024)On Measuring the Topological Charge of AnyonsProblems of Information Transmission10.1134/S003294602401004660:1(28-34)Online publication date: 7-Aug-2024
    • (2024) Gapped Clique Homology on Weighted Graphs is QMA 1 -Hard and Contained in QMA 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS61266.2024.00039(493-504)Online publication date: 27-Oct-2024
    • (2024)Phase-Sensitive Quantum Measurement without Controlled OperationsPhysical Review Letters10.1103/PhysRevLett.132.220601132:22Online publication date: 28-May-2024
    • (2024)A Perspective on Protein Structure Prediction Using Quantum ComputersJournal of Chemical Theory and Computation10.1021/acs.jctc.4c0006720:9(3359-3378)Online publication date: 4-May-2024
    • (2024)Which Options Exist for NISQ-Friendly Linear Response Formulations?Journal of Chemical Theory and Computation10.1021/acs.jctc.3c0140220:9(3551-3565)Online publication date: 25-Apr-2024
    • (2024)Quantum algorithm for computing distances between subspacesPhysics Letters A10.1016/j.physleta.2024.129610(129610)Online publication date: May-2024
    • (2024)Finding eigenvectors with a quantum variational algorithmQuantum Information Processing10.1007/s11128-024-04461-323:7Online publication date: 25-Jun-2024
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media