dorsal/arxiv
View SchemaPolynomial Quantum Algorithms for Additive approximations of the Potts model and other Points of the Tutte Plane
| Authors | Dorit Aharonov, Itai Arad, Elad Eban, Zeph Landau |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0702008 |
| URL | https://arxiv.org/abs/quant-ph/0702008 |
Abstract
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.
{
"annotation_id": "1ac2f199-3827-4c75-b4ca-e3240e612558",
"date_created": "2026-03-02T18:02:34.048000Z",
"date_modified": "2026-03-02T18:02:34.048000Z",
"file_hash": "66998809862fd63bdca72c2d2cc69fccf42bb2838e73547266fcb3af23fe7bfa",
"private": false,
"record": {
"abstract": "In the first 36 pages of this paper, we provide polynomial quantum algorithms\nfor additive approximations of the Tutte polynomial, at any point in the Tutte\nplane, for any planar graph. This includes as special cases the AJL algorithm\nfor the Jones polynomial, the partition function of the Potts model for any\nweighted planer graph at any temperature, and many other combinatorial graph\nproperties. In the second part of the paper we prove the quantum universality\nof many of the problems for which we provide an algorithm, thus providing a\nlarge set of new quantum-complete problems. Unfortunately, we do not know that\nthis holds for the Potts model case; this is left as an important open problem.\nThe main progress in this work is in our ability to handle non-unitary\nrepresentations of the Temperley Lieb algebra, both when applying them in the\nalgorithm, and, more importantly, in the proof of universality, when encoding\nquantum circuits using non-unitary operators. To this end we develop many new\ntools, that allow proving density and applying the Solovay Kitaev theorem in\nthe case of non-unitary matrices. We hope that these tools will open up new\npossibilities of using non-unitary reps in other quantum computation contexts.",
"arxiv_id": "quant-ph/0702008",
"authors": [
"Dorit Aharonov",
"Itai Arad",
"Elad Eban",
"Zeph Landau"
],
"categories": [
"quant-ph"
],
"title": "Polynomial Quantum Algorithms for Additive approximations of the Potts model and other Points of the Tutte Plane",
"url": "https://arxiv.org/abs/quant-ph/0702008"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b8f1483b-35e9-4ad6-b1ee-3254530365d9",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}