A permanent formula for the Jones polynomial

Dorit Aharonov, Vaughan F. R. Jones, Zeph A. Landau

Rūsiņš Freivalds

Martin Loebl, Iain Moffatt

Abstract. The permanent of a square matrix is defined in a way similar to the determinant, but without using signs. The exact computation of the permanent is hard, but there are Monte-Carlo algorithms that can estimate general permanents. Given a planar diagram of a link L with n crossings, we define a 7n×7n matrix whose permanent equals to the Jones polynomial of L. This result accompanied with recent work of Freedman, Kitaev, Larson and Wang ([FKLW]) provides a Monte-Carlo algorithm to any decision problem belonging to the class BQP, i.e. such that it can be computed with bounded error in polynomial time using quantum resources. 1.

HAMED AHMADI, Paweł Wocjan

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 [Formula: see text] 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 [Formula: see text] 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 [Formula: see text] are alternating links.

Valeriya Akhmedova, Emil Tofik ogly Akhmedov

Louis Hirsch Kauffman

In this paper we give a quantum statistical interpretation for the bracket polynomial state sum and for the Jones polynomial. We use this quantum mechanical interpretation to give a new quantum algorithm for computing the Jones polynomial. This algorithm is useful for its conceptual simplicity, and it applies to all values of the polynomial variable that lie on the unit circle in the complex plane. Letting C(K) denote the Hilbert space for this model, there is a natural unitary transformation U from C(K) to itself such that = where |F> is a sum over basis states for C(K). The quantum algorithm arises directly from this formula via the Hadamard Test. We then show that the framework for our quantum model for the bracket polynomial is a natural setting for Khovanov homology. The Hilbert space C(K) of our model has basis in one-to-one correspondence with the enhanced states of the bracket state summmation and is isomorphic with the chain complex for Khovanov homology with coefficients in the complex numbers. We show that for the Khovanov boundary operator d defined on C(K) we have the relationship dU + Ud = 0. Consequently, the unitary operator U acts on the Khovanov homology, and we therefore obtain a direct relationship between Khovanov homology and this quantum algorithm for the Jones polynomial. The formula for the Jones polynomial as a graded Euler characteristic is now expressed in terms of the eigenvalues of U and the Euler characteristics of the eigenspaces of U in the homology. The quantum algorithm given here is inefficient, and so it remains an open problem to determine better quantum algorithms that involve both the Jones polynomial and the Khovanov homology.