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.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
Jerrum, M., Sinclair, A., & Vigoda, E. (2004) · Journal of the ACM · doi:10.1145/1008731.1008738 · Cited by 792
An enumeration of knots and links, and some of their algebraic properties
Conway, J. (1970) · Elsevier eBooks · doi:10.1016/b978-0-08-012975-4.50034-5 · Cited by 704
Topological quantum computation
Freedman, M., Kitaev, A., Larsen, M., & Wang, Z. (2002) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-02-00964-3 · Cited by 669
Topological Quantum Computation
Wang, Z. (2010) · CBMS Regional Conference Series in Mathematics · doi:10.1090/cbms/112 · Cited by 576
A Modular Functor Which is Universal¶for Quantum Computation
Freedman, M. H., Larsen, M., & Wang, Z. (2002) · Communications in Mathematical Physics · doi:10.1007/s002200200645 · Cited by 573 · cited 3×
“A model of quantum computation based on Topological Quantum Field Theory (TQFT) and Chern-Simons theory was defined in [10, 11], and Kitaev, Larsen, Freedman and Wang showed that this model is polynomially equivalent in computational power to the standard quantum computation model in [12, 13 ].”
BackgroundMethodInfluentialOn the computational complexity of the Jones and Tutte polynomials
Jaeger, F., Vertigan, D. L., & Welsh, D. J. A. (1990) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100068936 · Cited by 481
A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
Kuperberg, G. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539703436345 · Cited by 347
Simulation of Topological Field Theories¶by Quantum Computers
Freedman, M. H., Kitaev, A., & Wang, Z. (2002) · Communications in Mathematical Physics · doi:10.1007/s002200200635 · Cited by 259
P/NP, and the quantum field computer
Freedman, M. H. (1998) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.95.1.98 · Cited by 221
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem
Hallgren, S. (2002) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/509907.510001 · Cited by 164
The BQP-hardness of approximating the Jones polynomial
Aharonov, D., & Arad, I. (2011) · New Journal of Physics · doi:10.1088/1367-2630/13/3/035019 · Cited by 123
Self-citationKnot theory and statistical mechanics
Wu, F. Y. (1992) · Reviews of Modern Physics · doi:10.1103/revmodphys.64.1099 · Cited by 102
Quantum algorithms for solvable groups
Watrous, J. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380759 · Cited by 99
Estimating Jones polynomials is a complete problem for one clean qubitPreprint
Shor, P. W., & Jordan, S. P. (2008) · doi:10.5555/2017011.2017012 · Cited by 95
q-DEFORMED SPIN NETWORKS, KNOT POLYNOMIALS AND ANYONIC TOPOLOGICAL QUANTUM COMPUTATION
Kauffman, L. H., & Lomonaco, S. J. (2007) · Journal of Knot Theory and Its Ramifications · doi:10.1142/s0218216507005282 · Cited by 75
Approximate Counting and Quantum Computation
Bordewich, M., Freedman, M. H., Lovász, L., & Welsh, D. J. A. (2005) · Combinatorics Probability Computing · doi:10.1017/s0963548305007005 · Cited by 62
Quantum computing and the Jones polynomial
Kauffman, L. H. (2002) · Contemporary mathematics - American Mathematical Society · doi:10.1090/conm/305/05218 · Cited by 55
Efficient Quantum Algorithms for Shifted Quadratic Character ProblemsPreprint
van Dam, W., & Hallgren, S. (2000) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2020.86 · Cited by 54
Topological quantum computing and the Jones polynomial
Lomonaco, S. J., & Kauffman, L. H. (2006) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.665361 · Cited by 33
Quantum Computation of Jones' PolynomialsPreprint
Subramaniam, V., & Ramadevi, P. (2002) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0210095 · Cited by 10
Trading Inverses for an Irrep in the Solovay-Kitaev TheoremPreprint
Bouland, A., & Ozols, M. (2017) · arXiv (Cornell University) · doi:10.4230/lipics.tqc.2018.6 · Cited by 9
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
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.