A celebrated important result due to (2002 Commun. Math. Phys. 227 605–22) states that providing additive approximations of the Jones polynomial at the kth root of unity, for constant k=5 and k≥7, is BQP-hard. Together with the algorithmic results of (2005) and (2002 Commun. Math. Phys. 227 587–603), this gives perhaps the most natural BQP-complete problem known today and motivates further study of the topic. In this paper, we focus on the universality proof; we extend the result of (2002) to ks that grow polynomially with the number of strands and crossings in the link, thus extending the BQP-hardness of Jones polynomial approximations to all values to which the AJL algorithm applies ( 2005), proving that for all those values, the problems are BQP-complete. As a side benefit, we derive a fairly elementary proof of the density result, without referring to advanced results from Lie algebra representation theory, making this important result accessible to a wider audience in the computer science research community. We make use of two general lemmas we prove, the bridge lemma and the decoupling lemma, which provide tools for establishing the density of subgroups in SU(n). Those tools seem to be of independent interest in more general contexts of proving the quantum universality. Our result also implies a completely classical statement, that the multiplicative approximations of the Jones polynomial, at exactly the same values, are #P-hard, via a recent result due to Kuperberg (2009 arXiv:0908.0512). Since the first publication of those results in their preliminary form (Aharonov and Arad 2006 arXiv:quant-ph 0605181), the methods we present here have been used in several other contexts (Aharonov and Arad 2007 arXiv:quant-ph 0702008; Peter and Stephen 2008 Quantum Inf. Comput. 8 681). The present paper is an improved and extended version of the results presented by Aharonov and Arad (2006) and includes discussions of the developments since then.
Since the first publication of the results presented here (in preliminary form) @cite_26 , they were already used in several contexts: Shor and Jordan @cite_15 built on the methods we develop here to prove universality of a variant of the Jones polynomial approximation problem, in the model of quantum computation with one clean qubit. In the extension of the AJL algorithm @cite_21 to the Potts model @cite_36 , Aharonov build on those methods to prove universality of approximating the Jones polynomial in many other values, and even in values which correspond to non-unitary representations. We hope that the method we present here will be useful is future other contexts as well.
@cite_36 @cite_15 @cite_26 @cite_21
1632584182 1616071251 2137459590 45689951
In the first 36 pages of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes as special cases the AJL algorithm for the Jones polynomial, the partition function of the Potts model for any weighted planer graph at any temperature, and many other combinatorial graph properties. In the second part of the paper we prove the quantum universality of many of the problems for which we provide an algorithm, thus providing a large set of new quantum-complete problems. Unfortunately, we do not know that this holds for the Potts model case; this is left as an important open problem. The main progress in this work is in our ability to handle non-unitary representations of the Temperley Lieb algebra, both when applying them in the algorithm, and, more importantly, in the proof of universality, when encoding quantum circuits using non-unitary operators. To this end we develop many new tools, that allow proving density and applying the Solovay Kitaev theorem in the case of non-unitary matrices. We hope that these tools will open up new possibilities of using non-unitary reps in other quantum computation contexts. It is known that evaluating a certain approximation to the Jones polynomial for the plat closure of a braid is a BQP-complete problem. That is, this problem exactly captures the power of the quantum circuit model[13, 3, 1]. The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maximally mixed state. One clean qubit computers are believed to be strictly weaker than standard quantum computers, but still capable of solving some classically intractable problems [21]. Here we show that evaluating a certain approximation to the Jones polynomial at a fifth root of unity for the trace closure of a braid is a complete problem for the one clean qubit complexity class. That is, a one clean qubit computer can approximate these Jones polynomials in time polynomial in both the number of strands and number of crossings, and the problem of simulating a one clean qubit computer is reducible to approximating the Jones polynomial of the trace closure of a braid. IN THIS PAPER I construct a state model for the (original) Jones polynomial [5]. (In [6] a state model was constructed for the Conway polynomial.) As we shall see, this model for the Jones polynomial arises as a normalization of a regular isotopy invariant of unoriented knots and links, called here the bracket polynomial, and denoted 〈K〉 for a link projectionK . The concept of regular isotopy will be explained below. The bracket polynomial has a very simple state model. In §2 (Theorem 2.10) I use the bracket polynomial to prove (via Proposition 2.9 and an observation of Kunio Murasugi) that the number of crossings in a connected, reduced alternating projection of a link L is a topological invariant of L. (A projection is reduced if it has no isthmus in the sense of Fig. 5.) In other words, any two connected, reduced alternating projections of the link L have the same number of crossings. This is a remarkable application of our technique. It solves affirmatively a conjecture going back to the knot tabulations of Tait, Kirkman and Little over a century ago (see [6], [9], [10]). Along with this application to alternating links, we also use the bracket polynomial to obtain a necessary condition for an alternating reduced link diagram to be ambient isotopic to its mirror image (Theorem 3.1). One consequence of this theorem is that a reduced alternating diagram with twist number greater than or equal to one-third the number of crossings is necessarily chiral. The paper is organized as follows. In §2 the bracket polynomial is developed, and its relationship with the Jones polynomial is explained. This provides a self-contained introduction to the Jones polynomial and to our techniques. The last part of §2 contains the applications to alternating knots, and to bounds on the minimal and maximal degrees of the polynomial. §3 contains the results about chirality of alternating knots. §4 discusses the structure of our state model in the case of braids. Here the states have an algebraic structure related to Jones’s representation of the braid group into a Von Neumann Algebra.