A Complexity Dichotomy for Quantum Invariants of 3-Manifolds

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{\#}\mathrm{P}$-hard. If $\mathcal{A}$ is a spherical fusion category, then the Turaev–Viro invariant $\mathrm{\mid }M{\mathrm{\mid }}_{\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{\#}\mathrm{P}$-hard. This proves the dichotomy conjectured by Bridges and Samperton and identifies the categorical obstruction to polynomial-time evaluation.