Polynomial Quantum Algorithms for Additive approximations of the Potts model and other Points of the Tutte Plane
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
82 pages. Up to page 36: the algorithm. From there on: The universality proof. Most readers will want to read only the first part. Presented at QIP 2007, Brisbane, Australia
82 pages. Up to page 36: the algorithm. From there on: The universality proof. Most readers will want to read only the first part. Presented at QIP 2007, Brisbane, Australia