Combinatorial framework for topological quantum computing

We describe a combinatorial framework for topological quantum
computation, and illustrate a number of algorithmic questions in knot theory and
in the theory of finitely presented groups, focusing in particular on the braid group.
This list of problems gives us the chance of defining (classical) complexity classes
of algorithms by resorting to specific examples and not in a purely abstract way. In
particular the algorithmic questions concerning the Jones polynomial are discussed
and the basic definition of ‘colored’ Jones polynomials is given within an algebraic
context. We address efficient quantum algorithms for the (approximate) evaluation
of colored Jones polynomials and 3–manifold invariants, stressing the strong mutual
connections between quantum geometry and quantum computing.