Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation

Abstract

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)-D 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 novel relation between the task of distinguishing non-homeomorphic 3-manifolds and the power of a general quantum computer.

4 pages, 3 figures

References in corpus (4)

• Simulation of topological field theories by quantum computers
• Quantum computation with Turaev-Viro codes
• The two-eigenvalue problem and density of Jones representation of braid groups
• Density of the SO(3) TQFT representation of mapping class groups

Cited by in corpus (8)

• The BQP-hardness of approximating the Jones Polynomial
• Quantum Discord and Quantum Computing - An Appraisal
• (3+1)-dimensional topological phases and self-dual quantum geometries encoded on Heegard surfaces
• Algorithms and complexity for Turaev-Viro invariants
• Quantum Fourier Transforms and the Complexity of Link Invariants for Quantum Doubles of Finite Groups
• Approximating the Turaev-Viro Invariant of Mapping Tori is Complete for One Clean Qubit
• Resource optimization for fault-tolerant quantum computing
• Sumcheck-based delegation of quantum computing to rational server