Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cambridge University Press eBooks

The Jones polynomial algorithm

Jiannis K. Pachos

Published Apr 12, 2012• 0 citations
Publisher

Abstract

The study of anyonic systems as computational means has led to the exciting discovery of a new quantum algorithm. This algorithm provides a novel paradigm that fundamentally differs from searching (Grover, 1996) and factoring (Shor, 1997) algorithms. It is based on the particular behaviour of anyons and its goal is to evaluate Jones polynomials (Jones, 1985, 2005). These polynomials are topological invariants of knots and links, i.e., they depend on the global characteristics of their strands and not on their local geometry. The Jones polynomials were first connected to topological quantum field theories by Edward Witten (1989). Since then they have found applications in various areas of research, such as biology for DNA reconstruction (Nechaev, 1996) and statistical physics (Kauffman, 1991).

DOI
10.1017/cbo9780511792908.008

Related papers

A polynomial quantum algorithm for approximating the Jones polynomial

Dorit Aharonov, Vaughan F. R. Jones, Zeph A. Landau

The Jones polynomial, discovered in 1984 [18], is an important knot invariant in topology. Among its many connections to various mathematical and physical areas, it is known (due to Witten [32]) to be intimately connected to Topological Quantum Field Theory (TQFT). The works of Freedman, Kitaev, Larsen and Wang [13, 14] provide an efficient simulation of TQFT by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient 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 BQP-complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results in [13, 14] are heavily based on 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 TQFT, on well known mathematical results (specifically, the path model representation of the braid group and the uniqueness of the Markov trace for the Temperly Lieb algebra). By the results of [14], our algorithm solves a BQP complete problem.The algorithm we provide exhibits a structure which we hope is generalizable to other quantum algorithmic problems. Candidates of particular interest are the approximations of other downwards self-reducible P-hard problems, most notably, the Potts model.

ACM Symposium on Theory of Computing (STOC)•May 21, 2006•145 citations

Quantum knitting

Silvano Garnerone, Annalisa Marzuoli, Mario Rasetti

We analyze the connections between the mathematical theory of knots and quantum physics by addressing a number of algorithmic questions related to both knots and braid groups. Knots can be distinguished by means of “knot invariants,” among which the Jones polynomial plays a prominent role, since it can be associated with observables in topological quantum field theory. Although the problem of computing the Jones polynomial is intractable in the framework of classical complexity theory, it has been recently recognized that a quantum computer is capable of approximating it in an efficient way. The quantum algorithms discussed here represent a breakthrough for quantum computation, since approximating the Jones polynomial is actually a “universal problem,” namely, the hardest problem that a quantum computer can efficiently handle.

arXiv:quant-ph/0606137•Laser Physics•Oct 30, 2006•14 citations

Introduction to topological quantum computation with non-Abelian anyons

Bernard Field, Tapio Simula

Abstract Topological quantum computers promise a fault tolerant means to perform quantum computation. Topological quantum computers use particles with exotic exchange statistics called non-Abelian anyons, and the simplest anyon model which allows for universal quantum computation by particle exchange or braiding alone is the Fibonacci anyon model. One classically hard problem that can be solved efficiently using quantum computation is finding the value of the Jones polynomial of knots at roots of unity. We aim to provide a pedagogical, self-contained, review of topological quantum computation with Fibonacci anyons, from the braiding statistics and matrices to the layout of such a computer and the compiling of braids to perform specific operations. Then we use a simulation of a topological quantum computer to explicitly demonstrate a quantum computation using Fibonacci anyons, evaluating the Jones polynomial of a selection of simple knots. In addition to simulating a modular circuit-style quantum algorithm, we also show how the magnitude of the Jones polynomial at specific points could be obtained exactly using Fibonacci or Ising anyons. Such an exact algorithm seems ideally suited for a proof of concept demonstration of a topological quantum computer.

arXiv:1802.06176•Quantum Science and Technology•Jun 6, 2018•142 citations

Jones Polynomial from Quantum R-Matrices: Unifying Knot Theory and Topological Quantum Computation — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: The Jones polynomial is a knot invariant constructible from quantum R-matrices (braid group representations), and its evaluation at roots of unity yields the computational resource for topological quantum computation — the same algebraic structure underlies both knot theory and TQFT. | MATH: Jones polynomial V_K(t) ∈ ℤ[t^{±1/2}]; skein relation: t⁻¹V(L₊) − tV(L₋) = (t^{1/2} − t^{−1/2})V(L₀). Braid group representation: ρ: B_n → GL(V^⊗n) via R-matrix satisfying Yang-Baxter equation (R⊗I)(I⊗R)(R⊗I) = (I⊗R)(R⊗I)(I⊗R). At t = e^{2πi/k}, the representation factors through Temperley-Lieb algebra TL_n(q) with q + q⁻¹ = −(t^{1/2} + t^{−1/2}). Quantum dimension d = −(q + q⁻¹) = [2]_q. Modular tensor category (MTC) data: fusion rules N_{ij}^k, S-matrix, T-matrix (topological spin), satisfying (ST)³ = e^{2πic/8}·S² (modularity). | CONNECTION: Root-of-unity evaluation t = e^{2πi/k} connects to: (1) quantum group U_q(sl₂) at q = e^{iπ/k} — deformation parameter is a root of unity, truncati Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 29, 2026•0 citations

Classical simulation of a topological quantum computer

B.O. Field, Tapio Simula

Topological quantum computers promise a fault tolerant means to perform quantum computation. Topological quantum computers use particles with exotic exchange statistics called non-Abelian anyons, and the simplest anyon model which allows for universal quantum computation by particle exchange or braiding alone is the Fibonacci anyon model. One classically hard problem that can be solved efficiently using quantum computation is finding the value of the Jones polynomial of knots at roots of unity. We aim to provide a pedagogical, self-contained, review of topological quantum computation with Fibonacci anyons, from the braiding statistics and matrices to the layout of such a computer and the compiling of braids to perform specific operations. Then we use a simulation of a topological quantum computer to explicitly demonstrate a quantum computation using Fibonacci anyons, evaluating the Jones polynomial of a selection of simple knots.

•Feb 17, 2018•1 citation

Possible universal quantum algorithms for generalized Turaev-Viro invariants

Mario E. Vélez, Juan Ospina

An emergent trend in quantum computation is the topological quantum computation (TQC). Briefly, TQC results from the application of quantum computation with the aim to solve the problems of quantum topology such as topological invariants for knots and links (Jones polynomials, HOMFLY polynomials, Khovanov polynomials); topological invariants for graphs (Tutte polynomial and Bollobás-Riordan polynomial); topological invariants for 3-manifolds (Reshetiskin-Turaev, Turaev-Viro and Turaer-Viro-Ocneanu invariants) and topological invariants for 4-manifolds( Crane-Yetter invariants). In a few words, TQC is concerned with the formulation of quantum algorithms for the computation of these topological invariants in quantum topology. Given that one of the fundamental achievements of quantum topology was the discovery of strong connections between monoidal categories and 3-dimensional manifolds, in TQC is possible and necessary to exploit such connections with the purpose to formulate universal quantum algorithms for topological invariants of 3-manifolds. In the present work we make an exploration of such possibilities. Specifically we search for universal quantum algorithms for generalized Turaev-Viro invariants of 3-manifolds such as the Turaev-Viro-Ocneanu invariants, the Kashaev-Baseilhac-Benedetti invariants of 3-manifolds with links and the Geer-Kashaev-Turaev invariants of 3-manifolds with a link and a principal bundle. We also look for physical systems (three dimensional topological insulators and three-dimensional gravity) over which implement the resulting universal topological quantum algorithms.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 13, 2011•0 citations
The study of anyonic systems as computational means has led to the exciting discovery of a new quantum algorithm. This algorithm provides a novel paradigm that fundamentally differs from searching (Grover, 1996) and factoring (Shor, 1997) algorithms. It is based on the particular behaviour of anyons and its goal is to evaluate Jones polynomials (Jones, 1985, 2005). These polynomials are topological invariants of knots and links, i.e., they depend on the global characteristics of their strands and not on their local geometry. The Jones polynomials were first connected to topological quantum field theories by Edward Witten (1989). Since then they have found applications in various areas of research, such as biology for DNA reconstruction (Nechaev, 1996) and statistical physics (Kauffman, 1991).
The Jones polynomial, discovered in 1984 [18], is an important knot invariant in topology. Among its many connections to various mathematical and physical areas, it is known (due to Witten [32]) to be intimately connected to Topological Quantum Field Theory (TQFT). The works of Freedman, Kitaev, Larsen and Wang [13, 14] provide an efficient simulation of TQFT by a quantum computer, and vice versa. These results implicitly imply the existence of an efficient 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 BQP-complete. Unfortunately, this important algorithm was never explicitly formulated. Moreover, the results in [13, 14] are heavily based on 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 TQFT, on well known mathematical results (specifically, the path model representation of the braid group and the uniqueness of the Markov trace for the Temperly Lieb algebra). By the results of [14], our algorithm solves a BQP complete problem.The algorithm we provide exhibits a structure which we hope is generalizable to other quantum algorithmic problems. Candidates of particular interest are the approximations of other downwards self-reducible P-hard problems, most notably, the Potts model.
We analyze the connections between the mathematical theory of knots and quantum physics by addressing a number of algorithmic questions related to both knots and braid groups. Knots can be distinguished by means of “knot invariants,” among which the Jones polynomial plays a prominent role, since it can be associated with observables in topological quantum field theory. Although the problem of computing the Jones polynomial is intractable in the framework of classical complexity theory, it has been recently recognized that a quantum computer is capable of approximating it in an efficient way. The quantum algorithms discussed here represent a breakthrough for quantum computation, since approximating the Jones polynomial is actually a “universal problem,” namely, the hardest problem that a quantum computer can efficiently handle.
Abstract Topological quantum computers promise a fault tolerant means to perform quantum computation. Topological quantum computers use particles with exotic exchange statistics called non-Abelian anyons, and the simplest anyon model which allows for universal quantum computation by particle exchange or braiding alone is the Fibonacci anyon model. One classically hard problem that can be solved efficiently using quantum computation is finding the value of the Jones polynomial of knots at roots of unity. We aim to provide a pedagogical, self-contained, review of topological quantum computation with Fibonacci anyons, from the braiding statistics and matrices to the layout of such a computer and the compiling of braids to perform specific operations. Then we use a simulation of a topological quantum computer to explicitly demonstrate a quantum computation using Fibonacci anyons, evaluating the Jones polynomial of a selection of simple knots. In addition to simulating a modular circuit-style quantum algorithm, we also show how the magnitude of the Jones polynomial at specific points could be obtained exactly using Fibonacci or Ising anyons. Such an exact algorithm seems ideally suited for a proof of concept demonstration of a topological quantum computer.
FINDING: The Jones polynomial is a knot invariant constructible from quantum R-matrices (braid group representations), and its evaluation at roots of unity yields the computational resource for topological quantum computation — the same algebraic structure underlies both knot theory and TQFT. | MATH: Jones polynomial V_K(t) ∈ ℤ[t^{±1/2}]; skein relation: t⁻¹V(L₊) − tV(L₋) = (t^{1/2} − t^{−1/2})V(L₀). Braid group representation: ρ: B_n → GL(V^⊗n) via R-matrix satisfying Yang-Baxter equation (R⊗I)(I⊗R)(R⊗I) = (I⊗R)(R⊗I)(I⊗R). At t = e^{2πi/k}, the representation factors through Temperley-Lieb algebra TL_n(q) with q + q⁻¹ = −(t^{1/2} + t^{−1/2}). Quantum dimension d = −(q + q⁻¹) = [2]_q. Modular tensor category (MTC) data: fusion rules N_{ij}^k, S-matrix, T-matrix (topological spin), satisfying (ST)³ = e^{2πic/8}·S² (modularity). | CONNECTION: Root-of-unity evaluation t = e^{2πi/k} connects to: (1) quantum group U_q(sl₂) at q = e^{iπ/k} — deformation parameter is a root of unity, truncati Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
Topological quantum computers promise a fault tolerant means to perform quantum computation. Topological quantum computers use particles with exotic exchange statistics called non-Abelian anyons, and the simplest anyon model which allows for universal quantum computation by particle exchange or braiding alone is the Fibonacci anyon model. One classically hard problem that can be solved efficiently using quantum computation is finding the value of the Jones polynomial of knots at roots of unity. We aim to provide a pedagogical, self-contained, review of topological quantum computation with Fibonacci anyons, from the braiding statistics and matrices to the layout of such a computer and the compiling of braids to perform specific operations. Then we use a simulation of a topological quantum computer to explicitly demonstrate a quantum computation using Fibonacci anyons, evaluating the Jones polynomial of a selection of simple knots.
An emergent trend in quantum computation is the topological quantum computation (TQC). Briefly, TQC results from the application of quantum computation with the aim to solve the problems of quantum topology such as topological invariants for knots and links (Jones polynomials, HOMFLY polynomials, Khovanov polynomials); topological invariants for graphs (Tutte polynomial and Bollobás-Riordan polynomial); topological invariants for 3-manifolds (Reshetiskin-Turaev, Turaev-Viro and Turaer-Viro-Ocneanu invariants) and topological invariants for 4-manifolds( Crane-Yetter invariants). In a few words, TQC is concerned with the formulation of quantum algorithms for the computation of these topological invariants in quantum topology. Given that one of the fundamental achievements of quantum topology was the discovery of strong connections between monoidal categories and 3-dimensional manifolds, in TQC is possible and necessary to exploit such connections with the purpose to formulate universal quantum algorithms for topological invariants of 3-manifolds. In the present work we make an exploration of such possibilities. Specifically we search for universal quantum algorithms for generalized Turaev-Viro invariants of 3-manifolds such as the Turaev-Viro-Ocneanu invariants, the Kashaev-Baseilhac-Benedetti invariants of 3-manifolds with links and the Geer-Kashaev-Turaev invariants of 3-manifolds with a link and a principal bundle. We also look for physical systems (three dimensional topological insulators and three-dimensional gravity) over which implement the resulting universal topological quantum algorithms.