dorsal/arxiv
View SchemaThe BQP-hardness of approximating the Jones Polynomial
| Authors | Dorit Aharonov, Itai Arad |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0605181 |
| URL | https://arxiv.org/abs/quant-ph/0605181 |
| DOI | 10.1088/1367-2630/13/3/035019 |
| Journal | New J. Phys. 13 (2011) 035019 |
| License | http://arxiv.org/licenses/nonexclusive-distrib/1.0/ |
Abstract
A celebrated important result due to Freedman, Larsen and Wang states that providing additive approximations of the Jones polynomial at the k'th root of unity, for constant k=5 and k>6, is BQP-hard. Together with the algorithmic results of Freedman et al and Aharonov et al, this gives perhaps the most natural BQP-complete problem known today and motivates further study of the topic. In this paper we focus on the universality proof; we extend the universality result of Freedman et al to k's that grow polynomially with the number of strands and crossings in the link, thus extending the BQP-hardness of Jones polynomial approximations to all values for which the AJL algorithm applies, proving that for all those values, the problems are BQP-complete. As a side benefit, we derive a fairly elementary proof of the Freedman et al density result, without referring to advanced results from Lie algebra representation theory, making this important result accessible to computer science audience. We make use of two general lemmas we prove, the Bridge lemma and the Decoupling lemma, which provide tools for establishing density of subgroups in SU(n). Those tools seem to be of independent interest in more general contexts of proving quantum universality. Our result also implies a completely classical statement, that the_multiplicative_ approximations of the Jones polynomial, at exactly the same values, are #P-hard, via a recent result due to Kuperberg. Since the first publication of those results in their preliminary form (arXiv:quant-ph/0605181v2), the methods we present here were used in several other contexts. This paper is an improved and extended version of the original results, and also includes discussions of the developments since then.
{
"annotation_id": "0dee8d03-bff0-4806-a5e6-b26ce36508c0",
"date_created": "2026-03-02T18:02:27.495000Z",
"date_modified": "2026-03-02T18:02:27.495000Z",
"file_hash": "e33762836c8f2e5dcf1610cae8e825cad7171ec4964bff30d83b3d372c0683a3",
"private": false,
"record": {
"abstract": "A celebrated important result due to Freedman, Larsen and Wang states that\nproviding additive approximations of the Jones polynomial at the k\u0027th root of\nunity, for constant k=5 and k\u003e6, is BQP-hard. Together with the algorithmic\nresults of Freedman et al and Aharonov et al, this gives perhaps the most\nnatural BQP-complete problem known today and motivates further study of the\ntopic. In this paper we focus on the universality proof; we extend the\nuniversality result of Freedman et al to k\u0027s that grow polynomially with the\nnumber of strands and crossings in the link, thus extending the BQP-hardness of\nJones polynomial approximations to all values for which the AJL algorithm\napplies, proving that for all those values, the problems are BQP-complete. As a\nside benefit, we derive a fairly elementary proof of the Freedman et al density\nresult, without referring to advanced results from Lie algebra representation\ntheory, making this important result accessible to computer science audience.\nWe make use of two general lemmas we prove, the Bridge lemma and the Decoupling\nlemma, which provide tools for establishing density of subgroups in SU(n).\nThose tools seem to be of independent interest in more general contexts of\nproving quantum universality. Our result also implies a completely classical\nstatement, that the_multiplicative_ approximations of the Jones polynomial, at\nexactly the same values, are #P-hard, via a recent result due to Kuperberg.\nSince the first publication of those results in their preliminary form\n(arXiv:quant-ph/0605181v2), the methods we present here were used in several\nother contexts. This paper is an improved and extended version of the original\nresults, and also includes discussions of the developments since then.",
"arxiv_id": "quant-ph/0605181",
"authors": [
"Dorit Aharonov",
"Itai Arad"
],
"categories": [
"quant-ph",
"cs.CC"
],
"doi": "10.1088/1367-2630/13/3/035019",
"journal_ref": "New J. Phys. 13 (2011) 035019",
"license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
"title": "The BQP-hardness of approximating the Jones Polynomial",
"url": "https://arxiv.org/abs/quant-ph/0605181"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c1aa5dd5-c931-4766-b922-4ba8d35a7c03",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}