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

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Quantum algorithms for virtual Jones polynomials via Thistlethwaite theorems

Mario E. Vélez, Juan Ospina

Published Mar 31, 2010• 0 citations
Publisher

Abstract

Recently a quantum algorithm for the Jones polynomial of virtual links was proposed by Kauffman and Dye via the implementation of the virtual braid group in anyonic topological quantum computation when the virtual crossings are considered as generalized swap gates. Also recently, a mathematical method for the computation of the Jones polynomial of a given virtual link in terms of the relative Tuttle polynomial of its face (Tait) graph with some suitable variable substitutions was proposed by Diao and Hetyei. The method of Diao and Hetyei is offered as an alternative to the ribbon graph approach according to which the Tutte polynomial of a given virtual link is computed in terms of the Bollobás- Riordan polynomial of the corresponding ribbon graph. The method of Diao and Hetyei can be considered as an extension of the celebrated Thistlethwaite theorem according to which invariant polynomials for knots and links are derived from invariant polynomials for graphs. Starting from these ideas we propose a quantum algorithm for the Jones polynomial of a given virtual link in terms of the generalized Tutte polynomials by exploiting the Thistlethwaite theorem and the Kauffman algorithm . Our method is claimed as the quantum version of the Diao-Hetyei method. Possible supersymmetric implementations of our algortihm are discussed jointly with its formulations using topological quantum lambda calculus.

DOI
10.1117/12.849776

Related papers

Possible universal quantum algorithms for generalized Khovanov homology and the Rasmussen's invariant

Mario E. Vélez, Juan Ospina

Possible quantum algorithms for generalized Khovanov homology and the Rasmussen's invariant are proposed. Such algorithms are resulting from adaptations of the recently proposed Kauffman's algorithm for the standard Khovanov homology. The method that was applied consists in to write the relevant quantum invariant as the trace of a certain unitary operator and then to compute the trace using the Hadamard test. We apply such method to the quantum computation of the Jones polynomial, HOMFLY polynomial, Chromatic polynomial, Tutte polynomial and Bollobàs- Riordan polynomial. These polynomials are quantum topological invariants for knots, links, graphs and ribbon graphs respectively. The Jones polynomial is categorified by the standard Khovanov homology and the others polynomials are categorified by generalized Khovanov homologies, such as the Khovanov-Rozansky homology and the graph homologies. The algorithm for the Rasmussen's invariant is obtained using the gauge theory; and the recently introduced program of homotopyfication is linked with the super-symmetric quantum mechanics. It is claimed that a new program of analytification could be development from the homotopyfication using the celebrated Atiyah-Singer theorem and its super-symmetric interpretations. It is hoped that the super-symmetric quantum mechanics provides the hardware for the implementation of the proposed quantum algorithms.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 1, 2012•0 citations

Possible quantum algorithms for the Bollobas-Riordan-Tutte polynomial of a ribbon graph

Mario E. Vélez, Juan Ospina

Three possible quantum algorithms, for the computation of the Bollobás-Riordan-Tutte polynomial of a given ribbon graph, are presented and discussed. The first possible algorithm is based on the spanning quasi-trees expansion for generalized Tutte polynomials of generalized graphs and on a quantum version of the Binary Decision Diagram (BDD) for quasi-trees . The second possible algorithm is based on the relation between the Kauffman bracket and the Tutte polynomial; and with an application of the recently introduced Aharonov-Arad-Eban-Landau quantum algorithm. The third possible algorithm is based on the relation between the HOMFLY polynomial and the Tutte polynomial; and with an application of the Wocjan-Yard quantum algorithm. It is claimed that these possible algorithms may be more efficient that the best known classical algorithms. These three algorithms may have interesting applications in computer science at general or in computational biology and bio-informatics in particular. A line for future research based on the categorification project is mentioned.

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Mar 5, 2008•2 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

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

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
Recently a quantum algorithm for the Jones polynomial of virtual links was proposed by Kauffman and Dye via the implementation of the virtual braid group in anyonic topological quantum computation when the virtual crossings are considered as generalized swap gates. Also recently, a mathematical method for the computation of the Jones polynomial of a given virtual link in terms of the relative Tuttle polynomial of its face (Tait) graph with some suitable variable substitutions was proposed by Diao and Hetyei. The method of Diao and Hetyei is offered as an alternative to the ribbon graph approach according to which the Tutte polynomial of a given virtual link is computed in terms of the Bollobás- Riordan polynomial of the corresponding ribbon graph. The method of Diao and Hetyei can be considered as an extension of the celebrated Thistlethwaite theorem according to which invariant polynomials for knots and links are derived from invariant polynomials for graphs. Starting from these ideas we propose a quantum algorithm for the Jones polynomial of a given virtual link in terms of the generalized Tutte polynomials by exploiting the Thistlethwaite theorem and the Kauffman algorithm . Our method is claimed as the quantum version of the Diao-Hetyei method. Possible supersymmetric implementations of our algortihm are discussed jointly with its formulations using topological quantum lambda calculus.
Possible quantum algorithms for generalized Khovanov homology and the Rasmussen's invariant are proposed. Such algorithms are resulting from adaptations of the recently proposed Kauffman's algorithm for the standard Khovanov homology. The method that was applied consists in to write the relevant quantum invariant as the trace of a certain unitary operator and then to compute the trace using the Hadamard test. We apply such method to the quantum computation of the Jones polynomial, HOMFLY polynomial, Chromatic polynomial, Tutte polynomial and Bollobàs- Riordan polynomial. These polynomials are quantum topological invariants for knots, links, graphs and ribbon graphs respectively. The Jones polynomial is categorified by the standard Khovanov homology and the others polynomials are categorified by generalized Khovanov homologies, such as the Khovanov-Rozansky homology and the graph homologies. The algorithm for the Rasmussen's invariant is obtained using the gauge theory; and the recently introduced program of homotopyfication is linked with the super-symmetric quantum mechanics. It is claimed that a new program of analytification could be development from the homotopyfication using the celebrated Atiyah-Singer theorem and its super-symmetric interpretations. It is hoped that the super-symmetric quantum mechanics provides the hardware for the implementation of the proposed quantum algorithms.
Three possible quantum algorithms, for the computation of the Bollobás-Riordan-Tutte polynomial of a given ribbon graph, are presented and discussed. The first possible algorithm is based on the spanning quasi-trees expansion for generalized Tutte polynomials of generalized graphs and on a quantum version of the Binary Decision Diagram (BDD) for quasi-trees . The second possible algorithm is based on the relation between the Kauffman bracket and the Tutte polynomial; and with an application of the recently introduced Aharonov-Arad-Eban-Landau quantum algorithm. The third possible algorithm is based on the relation between the HOMFLY polynomial and the Tutte polynomial; and with an application of the Wocjan-Yard quantum algorithm. It is claimed that these possible algorithms may be more efficient that the best known classical algorithms. These three algorithms may have interesting applications in computer science at general or in computational biology and bio-informatics in particular. A line for future research based on the categorification project is mentioned.
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.
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.
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.