A permanent formula for the Jones polynomial

DOI10.1016/J.AAM.2011.03.003zbMATH Open1230.57014arXiv0705.4548OpenAlexW3105961863MaRDI QIDQ719783FDOQ719783

Martin Loebl, Iain Moffatt

Publication date: 11 October 2011

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

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.

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

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

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)

Cites Work

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

Cited In (3)

• TOWARDS A QUANTUM ALGORITHM FOR THE PERMANENT
• A matrix for computing the Jones polynomial of a knot
• Title not available (Why is that?)

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)