TY - JOUR
T1 - Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation
JF - Physical Review A
Y1 - 2010
A1 - Gorjan Alagic
A1 - Stephen P. Jordan
A1 - Robert Koenig
A1 - Ben W. Reichardt
AB - 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.
VL - 82
UR - http://arxiv.org/abs/1003.0923v1
CP - 4
J1 - Phys. Rev. A
U5 - 10.1103/PhysRevA.82.040302
ER -