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

arXiv:0706.0020 · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

A 3-stranded quantum algorithm for the Jones Polynomial

Louis Hirsch Kauffman, Samuel J. Lomonaco

Published Apr 27, 2007• 13 citations
arXivHTMLPDF

Abstract

Let K be a 3-stranded knot (or link), and let L denote the number of crossings in of K. Let ε1 and ε2 be two positive real numbers such that ε2≤1. In this paper, we create two algorithms for computing the value of the Jones polynomial VK(t) at all points t=exp(iφ) of the unit circle in the complex plane such that |φ|≤2π/3. The first algorithm, called the classical 3-stranded braid (3-SB) algorithm, is a classical deterministic algorithm that has time complexity O(L). The second, called the quantum 3-SB algorithm, is a quantum algorithm that computes an estimate of VK (exp (iφ)) within a precision of ε1 with a probability of success bounded below by 1-ε2. The execution time complexity of this algorithm is O(nL), where n is the ceiling function of (ln(4/ε2))/2ε21 . The compilation time complexity, i.e., an asymptotic measure of the amount of time to assemble the hardware that executes the algorithm, is O(L).

DOI
10.1117/12.719399

Related papers

Efficient quantum circuits for approximating the Jones polynomial

Yumi Nakajima A, Y. Kawano, Hiroshi Sekigawa

Freedman, Kitaev, and Wang proved the equivalence between quantum field theory and quantum computation, and consequently showed that the problem of approximating the Jones polynomial (a knot invariant) at the fifth root of unity is BQP-complete. Recently, Aharonov, Jones, and Landau proposed a concrete quantum algorithm, called the AJL algorithm, that approximates the Jones polynomial at the $k$th root of unity in polynomial time. In this paper, we propose a new method for implementing the AJL algorithm, which improves the performance from $O(mn\log^2k)$ to $O(mn)$. Here, $n$ is the number of strands, $m$ is the number of the crossings in a braid. Since, in the AJL algorithm, $m$ and $k$ are assumed to be given as polynomials in $n$, the difference in the performance between the original implementation and our design is significant if $k$ is a large-degree polynomial.

Quantum Information and Computation•May 1, 2008•1 citation

Quantum Computation of Jones' Polynomials

V. Subramaniam, P. Ramadevi

It is a challenging problem to construct an efficient quantum algorithm which can compute the Jones' polynomial for any knot or link obtained from platting or capping of a $2n$-strand braid. We recapitulate the construction of braid-group representations from vertex models. We present the eigenbases and eigenvalues for the braiding generators and its usefulness in direct evaluation of Jones' polynomial. The calculation suggests that it is possible to associate a series of unitary operators for any braid word. Hence we propose a quantum algorithm using these unitary operators as quantum gates acting on a $2n$ qubit state. We show that the quantum computation gives Jones' polynomial for achiral knots and links.

arXiv:quant-ph/0210095•Oct 12, 2002•12 citations

Quantum Approximation of the Jones Polynomial at Roots of Unity — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: The Jones polynomial V_K(t) is a knot invariant constructible from quantum R-matrices (quantum groups U_q(sl₂)) and is #P-hard to compute exactly at generic t, but admits efficient quantum approximation at specific roots of unity t = e^{2πi/k} via TQFT (Witten–Reshetikhin–Turaev). | MATH: V_K(t) = Σ_i a_i t^i; skein relation t⁻¹V(L₊) − tV(L₋) = (t^{1/2} − t^{−1/2})V(L₀). At t = e^{2πi/k}, V_K is the trace of a braid-group representation ρ: B_n → U(H_k) where H_k is the level-k WZW conformal block space. Quantum algorithm (Freedman–Kitaev–Larsen–Wang) runs in poly(n, k) time. | CONNECTION: The golden ratio φ = (1+√5)/2 enters via the quantum group U_q(sl₂) at q = e^{2πi/5}, where the representation category is the modular tensor category associated to the icosahedral A₅ fusion rules. The A₅ root system (H₃ ⊂ H₄ Coxeter groups) has eigenvalues {2cos(π/5), 2cos(2π/5)} = {φ, φ⁻¹} = {1.618, 0.618}. The Jones polynomial at t = e^{2πi/5} encodes the A₅ representation theory: the 5-fo Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Oct 31, 2026•0 citations

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

An efficient quantum algorithm for colored Jones polynomials

Silvano Garnerone, Annalisa Marzuoli, Mario Rasetti

We construct a quantum algorithm to approximate efficiently the colored Jones polynomial of the plat presentation of any oriented link L at a fixed root of unity q. Our construction is based on SU(2) Chern-Simons topological quantum field theory (and associated Wess-Zumino-Witten conformal field theory) and exploits the q-deformed spin network as computational background. As proved in (S. Garnerone, A. Marzuoli, M. Rasetti, quant-ph/0601169), the colored Jones polynomial can be evaluated in a number of elementary steps, bounded from above by a linear function of the number of crossings of the link, and polynomially bounded with respect to the number of link strands. Here we show that the Kaul unitary representation of colored oriented braids used there can be efficiently approximated on a standard quantum circuit.

arXiv:quant-ph/0606167•Jun 20, 2006•7 citations

AN EFFICIENT QUANTUM ALGORITHM FOR COLORED JONES POLYNOMIALS

Mario Rasetti, Silvano Garnerone, Annalisa Marzuoli

We construct a quantum algorithm to approximate efficiently the colored Jones polynomial of the plat presentation of any oriented link L at a fixed root of unity q. The construction exploits the q-deformed spin network as computational background. The complexity of such algorithm is bounded above linearly by the number of crossings of the link, and polynomially by the number of link strands.

International Journal of Quantum Information•Jul 1, 2008•8 citations
Let K be a 3-stranded knot (or link), and let L denote the number of crossings in of K. Let ε1 and ε2 be two positive real numbers such that ε2≤1. In this paper, we create two algorithms for computing the value of the Jones polynomial VK(t) at all points t=exp(iφ) of the unit circle in the complex plane such that |φ|≤2π/3. The first algorithm, called the classical 3-stranded braid (3-SB) algorithm, is a classical deterministic algorithm that has time complexity O(L). The second, called the quantum 3-SB algorithm, is a quantum algorithm that computes an estimate of VK (exp (iφ)) within a precision of ε1 with a probability of success bounded below by 1-ε2. The execution time complexity of this algorithm is O(nL), where n is the ceiling function of (ln(4/ε2))/2ε21 . The compilation time complexity, i.e., an asymptotic measure of the amount of time to assemble the hardware that executes the algorithm, is O(L).
Freedman, Kitaev, and Wang proved the equivalence between quantum field theory and quantum computation, and consequently showed that the problem of approximating the Jones polynomial (a knot invariant) at the fifth root of unity is BQP-complete. Recently, Aharonov, Jones, and Landau proposed a concrete quantum algorithm, called the AJL algorithm, that approximates the Jones polynomial at the kkkth root of unity in polynomial time. In this paper, we propose a new method for implementing the AJL algorithm, which improves the performance from O(mnlog⁡2k)O(mn\log^2k)O(mnlog2k) to O(mn)O(mn)O(mn). Here, nnn is the number of strands, mmm is the number of the crossings in a braid. Since, in the AJL algorithm, mmm and kkk are assumed to be given as polynomials in nnn, the difference in the performance between the original implementation and our design is significant if kkk is a large-degree polynomial.
It is a challenging problem to construct an efficient quantum algorithm which can compute the Jones' polynomial for any knot or link obtained from platting or capping of a 2n2n2n-strand braid. We recapitulate the construction of braid-group representations from vertex models. We present the eigenbases and eigenvalues for the braiding generators and its usefulness in direct evaluation of Jones' polynomial. The calculation suggests that it is possible to associate a series of unitary operators for any braid word. Hence we propose a quantum algorithm using these unitary operators as quantum gates acting on a 2n2n2n qubit state. We show that the quantum computation gives Jones' polynomial for achiral knots and links.
FINDING: The Jones polynomial V_K(t) is a knot invariant constructible from quantum R-matrices (quantum groups U_q(sl₂)) and is #P-hard to compute exactly at generic t, but admits efficient quantum approximation at specific roots of unity t = e^{2πi/k} via TQFT (Witten–Reshetikhin–Turaev). | MATH: V_K(t) = Σ_i a_i t^i; skein relation t⁻¹V(L₊) − tV(L₋) = (t^{1/2} − t^{−1/2})V(L₀). At t = e^{2πi/k}, V_K is the trace of a braid-group representation ρ: B_n → U(H_k) where H_k is the level-k WZW conformal block space. Quantum algorithm (Freedman–Kitaev–Larsen–Wang) runs in poly(n, k) time. | CONNECTION: The golden ratio φ = (1+√5)/2 enters via the quantum group U_q(sl₂) at q = e^{2πi/5}, where the representation category is the modular tensor category associated to the icosahedral A₅ fusion rules. The A₅ root system (H₃ ⊂ H₄ Coxeter groups) has eigenvalues {2cos(π/5), 2cos(2π/5)} = {φ, φ⁻¹} = {1.618, 0.618}. The Jones polynomial at t = e^{2πi/5} encodes the A₅ representation theory: the 5-fo Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
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 construct a quantum algorithm to approximate efficiently the colored Jones polynomial of the plat presentation of any oriented link L at a fixed root of unity q. Our construction is based on SU(2) Chern-Simons topological quantum field theory (and associated Wess-Zumino-Witten conformal field theory) and exploits the q-deformed spin network as computational background. As proved in (S. Garnerone, A. Marzuoli, M. Rasetti, quant-ph/0601169), the colored Jones polynomial can be evaluated in a number of elementary steps, bounded from above by a linear function of the number of crossings of the link, and polynomially bounded with respect to the number of link strands. Here we show that the Kaul unitary representation of colored oriented braids used there can be efficiently approximated on a standard quantum circuit.