Estimating Turaev-Viro three-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)-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.
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.Attached Files
Published - Alagic2010p11630Phys_Rev_A.pdf
Files
Name | Size | Download all |
---|---|---|
md5:8ff801b051fb4f7cb5c0b0b25ecc0f93
|
250.1 kB | Preview Download |
Additional details
- Eprint ID
- 20493
- Resolver ID
- CaltechAUTHORS:20101025-093008743
- Sherman Fairchild Foundation
- PHY-0803371
- NSF
- PHY05-51164
- NSF
- PA00P2-126220
- Swiss National Science Foundation (SNF)
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- Army Research Office (ARO)
- Created
-
2010-11-24Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field