2007/02/01 by Dorit Aharonov, Aharonov, Dorit, Itai Arad +5 · 2 citations
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0702008
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
arxiv created 2007/02/01 · arxiv updated 2009/12/01
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.