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.