ON THE QUANTUM COMPLEXITY OF EVALUATING THE TUTTE POLYNOMIAL

DOI10.1142/S021821651000808XzbMath1194.81100MaRDI QIDQ3581162

Hamed Ahmadi, Paweł Wocjan

Publication date: 16 August 2010

Published in: Journal of Knot Theory and Its Ramifications (Search for Journal in Brave)

zbMATH Keywords

Tutte polynomialquantum algorithmlink invariantsquantum complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68) Relations of low-dimensional topology with graph theory (57M15) Quantum mechanics on special spaces: manifolds, fractals, graphs, lattices (81Q35)

Cites Work

• Inapproximability of the Tutte polynomial
• A spanning tree expansion of the Jones polynomial
• Hecke algebras of type \(A_ n\) and subfactors
• Simulation of topological field theories by quantum computers
• A modular functor which is universal for quantum computation
• q-DEFORMED SPIN NETWORKS, KNOT POLYNOMIALS AND ANYONIC TOPOLOGICAL QUANTUM COMPUTATION
• On the computational complexity of the Jones and Tutte polynomials
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Approximate Counting and Quantum Computation

This page was built for publication: ON THE QUANTUM COMPLEXITY OF EVALUATING THE TUTTE POLYNOMIAL