Title
On The Quantum Complexity Of Evaluating The Tutte Polynomial
Keywords
link invariants; Quantum algorithm; quantum complexity; Tutte polynomial
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 (e2πi/5, e-2πi/5) is DQC1-complete and at points (qk, 1+1-q-k/(q1/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 JonesWenzl representations of the Hecke algebra have finite order. We show that for each braid b we can efficiently construct a braid b̃ 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̃ are alternating links. © 2010 World Scientific Publishing Company.
Publication Date
6-1-2010
Publication Title
Journal of Knot Theory and its Ramifications
Volume
19
Issue
6
Number of Pages
727-737
Document Type
Article
Personal Identifier
scopus
DOI Link
https://doi.org/10.1142/S021821651000808X
Copyright Status
Unknown
Socpus ID
77954768510 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/77954768510
STARS Citation
Ahmadi, Hamed and Wocjan, Pawel, "On The Quantum Complexity Of Evaluating The Tutte Polynomial" (2010). Scopus Export 2010-2014. 634.
https://stars.library.ucf.edu/scopus2010/634