ON THE QUANTUM COMPLEXITY OF EVALUATING THE TUTTE POLYNOMIAL

    Authors

    H. Ahmadi;P. Wocjan

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    J. Knot Theory Ramifications

    Keywords

    Quantum algorithm; quantum complexity; Tutte polynomial; link invariants; JONES; COMPUTATION; Mathematics

    Abstract

    We show that the problem of approximately evaluating the Tutte polynomial of triangular graphs at the points (q, 1/q) of the Tutte plane is BQP-complete for (most) roots of unity q. We also consider circular graphs and show that the problem of approximately evaluating the Tutte polynomial of these graphs at the point (e(2 pi i/5), e(-2 pi i/5)) is DQC1-complete and at points (q(k), 1 + 1-q(-k)/(q(1/2)-q(-1/2))(2)) for some integer k is in BQP. To show that these problems can be solved by a quantum computer, we rely on the relation of the Tutte polynomial of a planar G graph with the Jones and HOMFLY polynomial of the alternating link D(G) given by the medial graph of G. In the case of our graphs the corresponding links are equal to the plat and trace closures of braids. It is known how to evaluate the Jones and HOMFLY polynomial for closures of braids. To establish the hardness results, we use the property that the images of the generators of the braid group under the irreducible Jones-Wenzl representations of the Hecke algebra have finite order. We show that for each braid b we can efficiently construct a braid (b) over tilde such that the evaluation of the Jones and HOMFLY polynomials of their closures at a fixed root of unity leads to the same value and that the closures of (b) over tilde are alternating links.

    Journal Title

    Journal of Knot Theory and Its Ramifications

    Volume

    19

    Issue/Number

    6

    Publication Date

    1-1-2010

    Document Type

    Article

    Language

    English

    First Page

    727

    Last Page

    737

    WOS Identifier

    WOS:000280853300002

    ISSN

    0218-2165

    Share

    COinS