Student or educator? Sign up with your school email and get 6 months of Pro free.
Cited by 270

The DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.

A Polynomial Quantum Algorithm for Approximating the Jones Polynomial

Aharonov, Dorit, Jones, Vaughan, Landau, Zeph·2009·Algorithmica

Abstract

AbstractThe 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 ( ${\sf{TQFT}}$ ). The works of Freedman, Kitaev, Larsen and Wang provide an efficient simulation of ${\sf{TQFT}}$ by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient (namely, polynomial) quantum algorithm that provides a certain additive approximation of the Jones polynomial at the fifth root of unity, e2πi/5, and moreover, that this problem is ${\sf{BQP}}$ -complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results of Freedman et al. are heavily based on ${\sf{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 e2πi/k, where the running time of the algorithm is polynomial in m, n and k. Our algorithm is based, rather than on ${\sf{TQFT}}$ , on well known mathematical results (specifically, the path model representation of the braid group and the uniqueness of the Markov trace for the Temperley-Lieb algebra). By the results of Freedman et al., our algorithm solves a ${\sf{BQP}}$ complete problem.Our algorithm works by encoding the local structure of the problem into the local unitary gates which are applied by the circuit. This structure is significantly different from previous quantum algorithms, which are mostly based on the Quantum Fourier transform. Since the results of the current paper were presented in their preliminary form, these ideas have been extended and generalized in several interesting directions. Most notably, Aharonov, Arad, Eban and Landau give a simplification and extension of these results that provides additive approximations for all points of the Tutte polynomial, including the Jones polynomial at any point, and the Potts model partition function at any temperature and any set of coupling strengths. We hope and believe that the ideas presented in this work will have other extensions and generalizations.

Overview

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1007/s00453-008-9168-0

Cites

31 of 31 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 31 references

Cited by

See all 270

Metadata

Authors
Aharonov, D., Jones, V., & Landau, Z.
Venue
Algorithmica
Published
2008-03-19
Volume
55
Issue
3
Pages
395-421
ISSN
  • 0178-4617 (ISSN-L)
  • 1432-0541
OpenAlex
W2069525126
Cited by
270
References
31
FWCI
23.32
Type
journal article
Language
en
Open access
closed

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: A Polynomial Quantum Algorithm for Approximating the Jones Polynomial. https://app.cochat.ai/papers/10.1007/s00453-008-9168-0
The paper
Aharonov, D., Jones, V., & Landau, Z. (2009). A Polynomial Quantum Algorithm for Approximating the Jones Polynomial. Algorithmica. https://doi.org/10.1007/s00453-008-9168-0

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.