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:quant-ph/0511096 · Algorithmica

A Polynomial Quantum Algorithm for Approximating the Jones Polynomial

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

Published Mar 18, 2008• 369 citations
arXivHTMLPDF
DOI
10.1007/s00453-008-9168-0

Related papers

A permanent formula for the Jones polynomial

Martin Loebl, Iain Moffatt

arXiv:0705.4548•Advances in Applied Mathematics•Apr 15, 2011•4 citations

Knot Theory, Jones Polynomial and Quantum Computing

Rūsiņš Freivalds

Lecture notes in computer science•Jan 1, 2005•4 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

Robust Polynomials and Quantum Algorithms

Harry Buhrman, Ilan Newman, Hein Röhrig +1 more

Lecture notes in computer science•Jan 1, 2005•16 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

An efficient quantum algorithm for simulating polynomial dynamical systems

Amit Surana, Abeynaya Gnanasekaran, Tuhin Sahai

arXiv:2212.10775•Quantum Information Processing•Mar 13, 2024•22 citations
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.
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.