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

Quantum Algorithms Beyond the Jones Polynomial

Elad Eban, Dorit Aharonov

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

The quantum algorithm of AJL [3] (following the work of Freedman et al. [10]) to approximate the Jones polynomial, is of a new type: rather than using the quantum Fourier transform, it encodes the local combinatorial structure of the problem by the relations of an algebra, called the Temperley-Lieb algebra, whose matrix representation is then applied, using a quantum computer. By the results of [11], the problems this algorithm solves are the first non trivial BQP-complete problems. A natural question is whether it is possible to generalize this algorithm to other points of the famous Tutte polynomial, of which the Jones polynomial is a special case. However, the only points for which

Related papers

Polynomial Quantum Algorithms for Additive approximations of the Potts model and other Points of the Tutte Plane

Dorit Aharonov, Itai Arad, Elad Eban +1 more

In the first 36 pages of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes as special cases the AJL algorithm for the Jones polynomial, the partition function of the Potts model for any weighted planer graph at any temperature, and many other combinatorial graph properties. In the second part of the paper we prove the quantum universality of many of the problems for which we provide an algorithm, thus providing a large set of new quantum-complete problems. Unfortunately, we do not know that this holds for the Potts model case; this is left as an important open problem. The main progress in this work is in our ability to handle non-unitary representations of the Temperley Lieb algebra, both when applying them in the algorithm, and, more importantly, in the proof of universality, when encoding quantum circuits using non-unitary operators. To this end we develop many new tools, that allow proving density and applying the Solovay Kitaev theorem in the case of non-unitary matrices. We hope that these tools will open up new possibilities of using non-unitary reps in other quantum computation contexts.

arXiv:quant-ph/0702008•Feb 1, 2007•59 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.

Quantum Information and Computation•Jan 1, 2008•56 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•Journal of International Crisis and Risk Communication Research•Mar 8, 2006•18 citations

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

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-cornplete 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.

Journal of International Crisis and Risk Communication Research•Jan 1, 2008•0 citations

Polynomial Quantum algorithms for additive approximations of the Potts model and other points of the Tutte plane Preliminary Version

Dorit Aharonov, Itai Arad, Elad Eban +1 more

In the first part of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes an additive approximation of the partition function of the Potts model for any weighted planer graph at any temperature, as well as approximations to many other combinatorial graph properties described by the (multivariate or not) Tutte polynomial. To achieve these algorithms, we generalize the Temperley Lieb algebra representations, used in [6], to apply for any graph (not necessarily coming from a braid). Moreover, our representations are non-unitary, as are all representations of the Temperley Lieb algebra not corresponding to Jones polynomial related parameters. It might seem at first sight that this makes it impossible to apply them by a quantum circuit. We show how to do this nevertheless. The approximation window size turns out to be inverse polynomial in |G| times the product of the norms of the operators we apply. Additive approximations are tricky; the range of the possible outcomes, might be smaller than the size of the approximation window, in which case the outcome is meaningless. Unfortunately, ruling out this possibility is difficult: If we want to argue that our a are meaningful, we have to provide an estimate of the scale of the problem, which is difficult here exactly because no efficient algorithm for the problem exists! In the second part of the paper we provide an indirect but very convincing proof that our approximation is meaningful for a large range of parameters, by showing that in those cases, the problems

•Jan 1, 2008•1 citation

Quantum Computing and the Jones Polynomial

Louis Hirsch Kauffman

This paper is an exploration of relationships between the Jones polynomial and quantum computing. We discuss the structure of the Jones polynomial in relation to representations of the Temperley Lieb algebra, and give an example of a unitary representation of the braid group. We discuss the evaluation of the polynomial as a generalized quantum amplitude and show how the braiding part of the evaluation can be construed as a quantum computation when the braiding representation is unitary. The question of an efficient quantum algorithm for computing the whole polynomial remains open.

arXiv:math/0105255•May 31, 2001•0 citations
The quantum algorithm of AJL [3] (following the work of Freedman et al. [10]) to approximate the Jones polynomial, is of a new type: rather than using the quantum Fourier transform, it encodes the local combinatorial structure of the problem by the relations of an algebra, called the Temperley-Lieb algebra, whose matrix representation is then applied, using a quantum computer. By the results of [11], the problems this algorithm solves are the first non trivial BQP-complete problems. A natural question is whether it is possible to generalize this algorithm to other points of the famous Tutte polynomial, of which the Jones polynomial is a special case. However, the only points for which
In the first 36 pages of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes as special cases the AJL algorithm for the Jones polynomial, the partition function of the Potts model for any weighted planer graph at any temperature, and many other combinatorial graph properties. In the second part of the paper we prove the quantum universality of many of the problems for which we provide an algorithm, thus providing a large set of new quantum-complete problems. Unfortunately, we do not know that this holds for the Potts model case; this is left as an important open problem. The main progress in this work is in our ability to handle non-unitary representations of the Temperley Lieb algebra, both when applying them in the algorithm, and, more importantly, in the proof of universality, when encoding quantum circuits using non-unitary operators. To this end we develop many new tools, that allow proving density and applying the Solovay Kitaev theorem in the case of non-unitary matrices. We hope that these tools will open up new possibilities of using non-unitary reps in other quantum computation contexts.
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.
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.
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-cornplete 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.
In the first part of this paper, we provide polynomial quantum algorithms for additive approximations of the Tutte polynomial, at any point in the Tutte plane, for any planar graph. This includes an additive approximation of the partition function of the Potts model for any weighted planer graph at any temperature, as well as approximations to many other combinatorial graph properties described by the (multivariate or not) Tutte polynomial. To achieve these algorithms, we generalize the Temperley Lieb algebra representations, used in [6], to apply for any graph (not necessarily coming from a braid). Moreover, our representations are non-unitary, as are all representations of the Temperley Lieb algebra not corresponding to Jones polynomial related parameters. It might seem at first sight that this makes it impossible to apply them by a quantum circuit. We show how to do this nevertheless. The approximation window size turns out to be inverse polynomial in |G| times the product of the norms of the operators we apply. Additive approximations are tricky; the range of the possible outcomes, might be smaller than the size of the approximation window, in which case the outcome is meaningless. Unfortunately, ruling out this possibility is difficult: If we want to argue that our a are meaningful, we have to provide an estimate of the scale of the problem, which is difficult here exactly because no efficient algorithm for the problem exists! In the second part of the paper we provide an indirect but very convincing proof that our approximation is meaningful for a large range of parameters, by showing that in those cases, the problems
This paper is an exploration of relationships between the Jones polynomial and quantum computing. We discuss the structure of the Jones polynomial in relation to representations of the Temperley Lieb algebra, and give an example of a unitary representation of the braid group. We discuss the evaluation of the polynomial as a generalized quantum amplitude and show how the braiding part of the evaluation can be construed as a quantum computation when the braiding representation is unitary. The question of an efficient quantum algorithm for computing the whole polynomial remains open.