A Complexity Dichotomy for Quantum Invariants of 3-Manifolds

Abstract

We determine the complexity of exact evaluation of the Reshetikhin--Turaev and Turaev--Viro invariants of closed connected oriented 3-manifolds, with the underlying tensor category fixed. If $\mathcal{C}$ is a modular category, then the Reshetikhin--Turaev invariant $Z_{\mathcal{C}}(M)$ can be computed in polynomial time from a framed-link surgery presentation of $M$ precisely when $\mathcal{C}$ is pointed; otherwise the problem is $\#\mathrm{P}$-hard. If $\mathcal{A}$ is a spherical fusion category, then the Turaev--Viro invariant $|M{|}_{\mathcal{A}}$ can be computed in polynomial time from a triangulation of $M$ precisely when the Drinfeld center $\mathcal{Z}(\mathcal{A})$ is pointed, equivalently when $\mathcal{A}$ is trivializable pointed; otherwise the problem is $\#\mathrm{P}$-hard. This proves the dichotomy conjectured by Bridges and Samperton and identifies the categorical obstruction to polynomial-time evaluation.

36 pages. Revised version. Simplifies the ordering convention in the graph-manifold construction, expands the polynomial-time cases, and clarifies the surgery-diagram presentations used in the reductions