Estimating Turaev-Viro three-manifold invariants is universal for quantum computation

The Turaev-Viro invariants are scalar topological invariants of compact, orientable $3$-manifolds. We give a quantum algorithm for additively approximating Turaev-Viro invariants of a manifold presented by a Heegaard splitting. The algorithm is motivated by the relationship between topological quantum computers and $(2+1)$-dimensional topological quantum field theories. Its accuracy is shown to be nontrivial, as the same algorithm, after efficient classical preprocessing, can solve any problem efficiently decidable by a quantum computer. Thus approximating certain Turaev-Viro invariants of manifolds presented by Heegaard splittings is a universal problem for quantum computation. This establishes a relation between the task of distinguishing nonhomeomorphic $3$-manifolds and the power of a general quantum computer.

Figure 1

A Dehn twist is a $2\pi$ rotation about a closed curve. The Dehn twists about the $3g-1$ curves shown above generate the full mapping class group of the genus-$g$ surface [10].

Figure 2

Three examples of decompositions of the genus-2 surface ${\Sigma }_2$ into three-punctured spheres. Trivalent adjacency graphs of the punctured spheres are shown in red.

Figure 3

(a) A $g$-qubit state $|z\rangle$, $z\in \{0,1\}{}^g$, can be encoded into ${\mathcal{H}}_{k,g}$ for the genus-$g$ handlebody. (b) Any two-qubit gate can be approximated within the codespace using the Dehn twists involving the two corresponding handles.