A permanent formula for the Jones polynomial

DOI10.1016/J.AAM.2011.03.003MaRDI QIDQ719783zbMATH OpenOpenAlexFDO

Authors Martin Loebl, Iain Moffatt

Publication date 11 October 2011

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.4548

zbMATH Keywords

Jones polynomialApproximationQuantum computingPermanentState sums

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Relations of low-dimensional topology with graph theory (57M15)

Abstract: The permanent of a square matrix is defined in a way similar to the determinant, but without using signs. The exact computation of the permanent is hard, but there are Monte-Carlo algorithms that can estimate general permanents. Given a planar diagram of a link L with $n$ crossings, we define a 7n by 7n matrix whose permanent equals to the Jones polynomial of L. This result accompanied with recent work of Freedman, Kitaev, Larson and Wang provides a Monte-Carlo algorithm to any decision problem belonging to the class BQP, i.e. such that it can be computed with bounded error in polynomial time using quantum resources.

Recommendations

• On the computational complexity of the Jones and Tutte polynomials
• A polynomial quantum algorithm for approximating the Jones polynomial
• The BQP-hardness of approximating the Jones polynomial
• A polynomial quantum algorithm for approximating the Jones polynomial
• The Jones polynomial: quantum algorithms and applications in quantum complexity theory

Cites work

• scientific article; zbMATH DE number 3856167 (Why is no real title available?)
• scientific article; zbMATH DE number 793872 (Why is no real title available?)
• A Monte-Carlo Algorithm for Estimating the Permanent
• A polynomial quantum algorithm for approximating the Jones polynomial
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• Approximate Counting and Quantum Computation
• Hecke algebra representations of braid groups and link polynomials
• How hard is it to approximate the Jones polynomial?
• On knot invariants related to some statistical mechanical models
• On the Melvin-Morton-Rozansky conjecture
• On the computational complexity of the Jones and Tutte polynomials
• Polynomial Time Algorithms to Approximate Permanents and Mixed Discriminants Within a Simply Exponential Factor
• Random walks and the colored Jones function
• The BQP-hardness of approximating the Jones polynomial
• The Yang-Baxter equation and invariants of links
• The complexity of computing the permanent
• Topological quantum computation

Cited in

(3)

• TOWARDS A QUANTUM ALGORITHM FOR THE PERMANENT
• scientific article; zbMATH DE number 1383488 (Why is no real title available?)
• A matrix for computing the Jones polynomial of a knot

This page was built for publication: A permanent formula for the Jones polynomial

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q719783)