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
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.
Integrity signals
Registry
Cites
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.
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
Quantum Computation and Quantum Information
Nielsen, M. A., Chuang, I., & Grover, L. K. (2002) · American Journal of Physics · doi:10.1119/1.1463744 · Cited by 21,895
Quantum computation and quantum information
Law, J. (2001) · ACM SIGSOFT Software Engineering Notes · doi:10.1145/505482.505499 · Cited by 18,842
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Quantum field theory and the Jones polynomial
Witten, E. (1989) · Communications in Mathematical Physics · doi:10.1007/bf01217730 · Cited by 4,758
A polynomial invariant for knots via von Neumann algebras
Jones, V. F. R. (1985) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-1985-15304-2 · Cited by 1,618
Self-citationBernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503
State models and the jones polynomial
H. Kauffman, L. (1987) · Topology · doi:10.1016/0040-9383(87)90009-7 · Cited by 1,394
Jones, V. F. R. (1983) · Inventiones mathematicae · doi:10.1007/bf01389127 · Cited by 1,375
Self-citationArtin, E. (1947) · The Annals of Mathematics · doi:10.2307/1969218 · Cited by 969
Exponential algorithmic speedup by a quantum walk
Childs, A. M., Cleve, R., Deotto, E., Farhi, E., Gutmann, S., & Spielman, D. A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780552 · Cited by 825
Cited by
Moore, C., & Mertens, S. (2011) · doi:10.1093/acprof:oso/9780199233212.001.0001 · Cited by 347
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344
The future of quantum computing with superconducting qubits
Bravyi, S., Dial, O., Gambetta, J. M., Gil, D., & Nazario, Z. (2022) · Journal of Applied Physics · doi:10.1063/5.0082975 · Cited by 334
Quantum computing and the entanglement frontier
Preskill, J. (2012) · arXiv · doi:10.48550/arxiv.1203.5813 · Cited by 308
Gate-count estimates for performing quantum chemistry on small quantum computers
Wecker, D., Bauer, B., Clark, B. K., Hastings, M. B., & Troyer, M. (2014) · Physical Review A · doi:10.1103/physreva.90.022305 · Cited by 296
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.