dorsal/arxiv
View SchemaA Polynomial Quantum Algorithm for Approximating the Jones Polynomial
| Authors | Dorit Aharonov, Vaughan Jones, Zeph Landau |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0511096 |
| URL | https://arxiv.org/abs/quant-ph/0511096 |
| Journal | STOC 2006 |
Abstract
The Jones polynomial, discovered in 1984, is an important knot invariant in topology. Among its many connections to various mathematical and physical areas, it is known (due to Witten) to be intimately connected to Topological Quantum Field Theory (TQFT). The works of Freedman, Kitaev, Larsen and Wang provide an efficient simulation of TQFT by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient quantum algorithm that provides a certain additive approximation of the Jones polynomial at the fifth root of unity, e^{2\pi i/5}, and moreover, that this problem is BQP-complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results mentioned are heavily based on TQFT, which makes the algorithm essentially inaccessible to computer scientists. We provide an explicit and simple polynomial quantum algorithm to approximate the Jones polynomial of an n-strands braid with m crossings at any primitive root of unity e^{2\pi i/k}, where the running time of the algorithm is polynomial in m,n and k. Our algorithm is based, rather than on TQFT, on well known mathematical results. By the results of Freedman et. al., our algorithm solves a BQP complete problem. The algorithm we provide exhibits a structure which we hope is generalizable to other quantum algorithmic problems. Candidates of particular interest are the approximations of other #P-hard problems, most notably, the partition function of the Potts model, a model which is known to be tightly connected to the Jones polynomial.
{
"annotation_id": "573050d4-8625-499a-bb6b-158567eaa5de",
"date_created": "2026-03-02T18:02:20.752000Z",
"date_modified": "2026-03-02T18:02:20.752000Z",
"file_hash": "0783c3cc95efcc66666b198574b45b6b42b16922cc647fe95034b1131b31729b",
"private": false,
"record": {
"abstract": "The Jones polynomial, discovered in 1984, is an important knot invariant in\ntopology. Among its many connections to various mathematical and physical\nareas, it is known (due to Witten) to be intimately connected to Topological\nQuantum Field Theory (TQFT). The works of Freedman, Kitaev, Larsen and Wang\nprovide an efficient simulation of TQFT by a quantum computer, and vice versa.\nThese results implicitly imply the existence of an efficient quantum algorithm\nthat provides a certain additive approximation of the Jones polynomial at the\nfifth root of unity, e^{2\\pi i/5}, and moreover, that this problem is\nBQP-complete. Unfortunately, this important algorithm was never explicitly\nformulated. Moreover, the results mentioned are heavily based on TQFT, which\nmakes the algorithm essentially inaccessible to computer scientists.\n We provide an explicit and simple polynomial quantum algorithm to approximate\nthe Jones polynomial of an n-strands braid with m crossings at any primitive\nroot of unity e^{2\\pi i/k}, where the running time of the algorithm is\npolynomial in m,n and k. Our algorithm is based, rather than on TQFT, on well\nknown mathematical results. By the results of Freedman et. al., our algorithm\nsolves a BQP complete problem.\n The algorithm we provide exhibits a structure which we hope is generalizable\nto other quantum algorithmic problems. Candidates of particular interest are\nthe approximations of other #P-hard problems, most notably, the partition\nfunction of the Potts model, a model which is known to be tightly connected to\nthe Jones polynomial.",
"arxiv_id": "quant-ph/0511096",
"authors": [
"Dorit Aharonov",
"Vaughan Jones",
"Zeph Landau"
],
"categories": [
"quant-ph"
],
"journal_ref": "STOC 2006",
"title": "A Polynomial Quantum Algorithm for Approximating the Jones Polynomial",
"url": "https://arxiv.org/abs/quant-ph/0511096"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "4cdd808f-305b-47af-97d0-ebce5e3169e4",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}