CaltechAUTHORS
  A Caltech Library Service

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

Alagic, Gorjan and Jordan, Stephen P. and König, Robert and Reichardt, Ben W. (2010) Estimating Turaev-Viro three-manifold invariants is universal for quantum computation. Physical Review A, 82 (4). Art. No. 040302. ISSN 1050-2947. http://resolver.caltech.edu/CaltechAUTHORS:20101025-093008743

[img]
Preview
PDF - Published Version
See Usage Policy.

244Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20101025-093008743

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)-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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1103/PhysRevA.82.040302 DOIUNSPECIFIED
http://pra.aps.org/abstract/PRA/v82/i4/e040302PublisherUNSPECIFIED
Additional Information:© 2010 The American Physical Society. Received 5 March 2010; revised manuscript received 10 August 2010; published 8 October 2010. S.J. acknowledges support from the Sherman Fairchild Foundation and NSF Grant No. PHY-0803371. R.K. acknowledges support by the Swiss National Science Foundation (SNF) under Grant No. PA00P2-126220. B.R. and G.A. acknowledge support from NSERC and ARO. Some of this research was conducted at the Kavli Institute for Theoretical Physics, supported by NSF Grant No. PHY05-51164.
Funders:
Funding AgencyGrant Number
Sherman Fairchild Foundation UNSPECIFIED
NSFPHY-0803371
NSFPHY05-51164
Swiss National Science Foundation (SNF) PA00P2-126220
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Army Research Office (ARO)UNSPECIFIED
Classification Code:PACS: 03.67.Ac, 02.40.Sf, 03.65.Vf, 05.30.Pr
Record Number:CaltechAUTHORS:20101025-093008743
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20101025-093008743
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:20493
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:24 Nov 2010 22:30
Last Modified:26 Dec 2012 12:33

Repository Staff Only: item control page