A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
By Dorit Aharonov, Vaughan F. R. Jones, Zeph Landau. Symposium on the Theory of Computing, 2005
389 citations recorded by the source corpus.
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.
Subfields: Computational Theory and Mathematics, Geometry and Topology
View Paper: https://www.semanticscholar.org/paper/bb9b6f5c0a14b0eebf0153093d8d2f83fba0f783
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Geometry and Topology
Citations in the corpus
- Universal Blind Quantum Computation (2008, background): “Following this, Abadi, Feigenbaum and Kilian [1] gave an impossibility result: no NP -hard function can be computed with encrypted data (even probabilistically and with polynomial interaction), unless the polynomial hierarchy collapses at the third level.”
- The future of quantum computing with superconducting qubits (2022, methodology): “…speedup include simulation of quantum many-body systems 19 , number theoretic problems such as integer factoring 5 , solving certain types of linear systems 20 , estimation of Betti numbers used in topological data analysis 21–23 , and computing topological invariants of knots and links 24 .”
- Quantum circuits and low-degree polynomials over F2 (2016, methodology): “Several such examples are known (e.g. [30, 4, 23, 44]), but approximately computing the number of zeroes of degree-3 polynomials would arguably be the simplest yet.”