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:2210.11127 · Physical Review Research

Estimating the Jones polynomial for Ising anyons on noisy quantum computers

Chris N. Self, S. Iblisdir, Gavin K. Brennen, Konstantinos Meichanetzidis

Published Mar 2, 2026• 3 citations
arXivHTMLPDF

Abstract

The evaluation of the Jones polynomial at roots of unity is a paradigmatic problem for quantum computers. In this work, we present experimental results obtained from existing noisy quantum computers for special cases of this problem, where it is classically tractable. Our approach relies on the reduction of the problem of evaluating the Jones polynomial of a knot at lattice roots of unity to the problem of computing quantum amplitudes of qudit stabilizer circuits, which are classically efficiently simulatable. More specifically, we focus on evaluation at the fourth root of unity, which is a lattice root of unity, where the problem reduces to evaluating amplitudes of qubit stabilizer circuits. To estimate the real and imaginary parts of the amplitudes up to additive error we use the Hadamard test, yielding non-Clifford circuits that nevertheless we can always efficiently compute the correct output of. Hence, we further argue that this setup defines a standard benchmark for near-term noisy quantum processors. Additionally, we study the benefit of performing quantum error mitigation with the method of zero-noise extrapolation.

DOI
10.1103/zqzv-zzrp

Related papers

End-to-End Quantum Algorithms for the Jones Polynomial

Tuomas Laakkonen, Enrico Rinaldi, Chris N. Self +6 more

We present an end-to-end algorithmic pipeline where a noisy digital quantum computer is used to approximate the value of the Jones polynomial at the fifth root of unity for any input link, i.e., a closed braid. This problem is DQC1-complete for Markov-closed braids and BQP-complete for Plat-closed braids, and we accommodate both versions of the problem. Even though it is widely believed that DQC1 is strictly contained in BQP, and so is “less quantum,” the resource requirements of classical algorithms for the DQC1 version are at least as high as for the BQP version, and so we potentially gain “more advantage” by focusing on Markov-closed braids in our exposition. We demonstrate our quantum algorithm on Quantinuum’s H2-2 quantum computer and show the effect of problem-tailored error-mitigation techniques. Further, leveraging that the Jones polynomial is a link invariant, we construct an efficiently verifiable benchmark to characterize the effect of noise present in a given quantum processor. In parallel, we develop and benchmark the state-of-the-art tensor-network-based classical algorithms for computing the Jones polynomial. The reconfigurable tools provided in this work allow for precise resource estimation to identify minimum link sizes for near-term quantum advantage in practice for a meaningful quantum-native problem in knot theory, if a candidate set of links are provided.

arXiv:2503.05625•PRX Quantum•Feb 19, 2026•8 citations

The Jones polynomial: quantum algorithms and applications in quantum complexity theory

Paweł Wocjan, Jon Yard

We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al.\ that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude with direct proofs that evaluating the Jones polynomial of the plat closure at most primitive roots of unity is a \#P-hard problem, while learning its most significant bit is PP-hard, circumventing the usual route through the Tutte polynomial and graph coloring.

arXiv:quant-ph/0603069•Quantum Information and Computation•Jan 1, 2008•79 citations

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

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

Jones Polynomial Knot Invariants Realized as Quantum Circuits via A_n Root Systems — E8 Intelligence Research

Andrew Stewart Caldin

FINDING: Jones polynomial knot invariants are directly realizable as quantum computing circuits, linking A_n root system representations to topological quantum gates. | MATH: Jones polynomial \( V_L(t) \) evaluated at roots of unity (e.g., \( t = e^{2\pi i / r} \)) yields unitary representations of braid groups; A_n root system has Cartan matrix \( A_{ij} = 2(\alpha_i,\alpha_j)/(\alpha_j,\alpha_j) \), with simple roots \( \alpha_i \) in \( \mathbb{R}^n \), Weyl group order \( |W(A_n)| = (n+1)! \). | CONNECTION: A_n root lattice is the \( n \)-dimensional hypercubic lattice \( \mathbb{Z}^n \) with all permutations; the golden ratio \( \varphi = 1.618 \) appears in the quantum dimension \( d = [2]_q = q + q^{-1} \) for \( q = e^{i\pi/5} \) (Fibonacci anyons), related to \( A_1 \) at level 3; base-60 emerges in the cyclic structure of \( \mathbb{Z}_n \) actions on braid groups. | DEPTH: 8 Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Jul 30, 2026•0 citations

Estimating Jones polynomials is a complete problem for one clean qubit

Peter W. Shor, Stephen P. Jordan

It is known that evaluating a certain approximation to the Jones polynomial for the plat closure of a braid is a BQP-complete problem. That is, this problem exactly captures the power of the quantum circuit model. The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maximally mixed state. One clean qubit computers are believed to be strictly weaker than standard quantum computers, but still capable of solving some classically intractable problems. Here we show that evaluating a certain approximation to the Jones polynomial at a fifth root of unity for the trace closure of a braid is a complete problem for the one clean qubit complexity class. That is, a one clean qubit computer can approximate these Jones polynomials in time polynomial in both the number of strands and number of crossings, and the problem of simulating a one clean qubit computer is reducible to approximating the Jones polynomial of the trace closure of a braid.

arXiv:0707.2831•Quantum Information and Computation•Sep 1, 2008•150 citations
The evaluation of the Jones polynomial at roots of unity is a paradigmatic problem for quantum computers. In this work, we present experimental results obtained from existing noisy quantum computers for special cases of this problem, where it is classically tractable. Our approach relies on the reduction of the problem of evaluating the Jones polynomial of a knot at lattice roots of unity to the problem of computing quantum amplitudes of qudit stabilizer circuits, which are classically efficiently simulatable. More specifically, we focus on evaluation at the fourth root of unity, which is a lattice root of unity, where the problem reduces to evaluating amplitudes of qubit stabilizer circuits. To estimate the real and imaginary parts of the amplitudes up to additive error we use the Hadamard test, yielding non-Clifford circuits that nevertheless we can always efficiently compute the correct output of. Hence, we further argue that this setup defines a standard benchmark for near-term noisy quantum processors. Additionally, we study the benefit of performing quantum error mitigation with the method of zero-noise extrapolation.
We present an end-to-end algorithmic pipeline where a noisy digital quantum computer is used to approximate the value of the Jones polynomial at the fifth root of unity for any input link, i.e., a closed braid. This problem is DQC1-complete for Markov-closed braids and BQP-complete for Plat-closed braids, and we accommodate both versions of the problem. Even though it is widely believed that DQC1 is strictly contained in BQP, and so is “less quantum,” the resource requirements of classical algorithms for the DQC1 version are at least as high as for the BQP version, and so we potentially gain “more advantage” by focusing on Markov-closed braids in our exposition. We demonstrate our quantum algorithm on Quantinuum’s H2-2 quantum computer and show the effect of problem-tailored error-mitigation techniques. Further, leveraging that the Jones polynomial is a link invariant, we construct an efficiently verifiable benchmark to characterize the effect of noise present in a given quantum processor. In parallel, we develop and benchmark the state-of-the-art tensor-network-based classical algorithms for computing the Jones polynomial. The reconfigurable tools provided in this work allow for precise resource estimation to identify minimum link sizes for near-term quantum advantage in practice for a meaningful quantum-native problem in knot theory, if a candidate set of links are provided.
We analyze relationships between quantum computation and a family of generalizations of the Jones polynomial. Extending recent work by Aharonov et al., we give efficient quantum circuits for implementing the unitary Jones-Wenzl representations of the braid group. We use these to provide new quantum algorithms for approximately evaluating a family of specializations of the HOMFLYPT two-variable polynomial of trace closures of braids. We also give algorithms for approximating the Jones polynomial of a general class of closures of braids at roots of unity. Next we provide a self-contained proof of a result of Freedman et al.\ that any quantum computation can be replaced by an additive approximation of the Jones polynomial, evaluated at almost any primitive root of unity. Our proof encodes two-qubit unitaries into the rectangular representation of the eight-strand braid group. We then give QCMA-complete and PSPACE-complete problems which are based on braids. We conclude with direct proofs that evaluating the Jones polynomial of the plat closure at most primitive roots of unity is a \#P-hard problem, while learning its most significant bit is PP-hard, circumventing the usual route through the Tutte polynomial and graph coloring.
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.
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.
FINDING: Jones polynomial knot invariants are directly realizable as quantum computing circuits, linking A_n root system representations to topological quantum gates. | MATH: Jones polynomial VL(t) V_L(t) VL​(t) evaluated at roots of unity (e.g., t=e2πi/r t = e^{2\pi i / r} t=e2πi/r) yields unitary representations of braid groups; A_n root system has Cartan matrix Aij=2(αi,αj)/(αj,αj) A_{ij} = 2(\alpha_i,\alpha_j)/(\alpha_j,\alpha_j) Aij​=2(αi​,αj​)/(αj​,αj​), with simple roots αi \alpha_i αi​ in Rn \mathbb{R}^n Rn, Weyl group order ∣W(An)∣=(n+1)! |W(A_n)| = (n+1)! ∣W(An​)∣=(n+1)!. | CONNECTION: A_n root lattice is the n n n-dimensional hypercubic lattice Zn \mathbb{Z}^n Zn with all permutations; the golden ratio φ=1.618 \varphi = 1.618 φ=1.618 appears in the quantum dimension d=[2]q=q+q−1 d = [2]_q = q + q^{-1} d=[2]q​=q+q−1 for q=eiπ/5 q = e^{i\pi/5} q=eiπ/5 (Fibonacci anyons), related to A1 A_1 A1​ at level 3; base-60 emerges in the cyclic structure of Zn \mathbb{Z}_n Zn​ actions on braid groups. | DEPTH: 8 Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com
It is known that evaluating a certain approximation to the Jones polynomial for the plat closure of a braid is a BQP-complete problem. That is, this problem exactly captures the power of the quantum circuit model. The one clean qubit model is a model of quantum computation in which all but one qubit starts in the maximally mixed state. One clean qubit computers are believed to be strictly weaker than standard quantum computers, but still capable of solving some classically intractable problems. Here we show that evaluating a certain approximation to the Jones polynomial at a fifth root of unity for the trace closure of a braid is a complete problem for the one clean qubit complexity class. That is, a one clean qubit computer can approximate these Jones polynomials in time polynomial in both the number of strands and number of crossings, and the problem of simulating a one clean qubit computer is reducible to approximating the Jones polynomial of the trace closure of a braid.