  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.
