Published March 2010
| Version Published
Journal Article
Open
Quantum-Merlin-Arthur–complete problems for stoquastic Hamiltonians and Markov matrices
-
1.
California Institute of Technology
-
2.
Massachusetts Institute of Technology
-
3.
Haverford College
Abstract
We show that finding the lowest eigenvalue of a 3-local symmetric stochastic matrix is Quantum-Merlin-Arthur-complete (QMA-complete). We also show that finding the highest energy of a stoquastic Hamiltonian is QMA-complete and that adiabatic quantum computation using certain excited states of a stoquastic Hamiltonian is universal. We also show that adiabatic evolution in the ground state of a stochastic frustration-free Hamiltonian is universal. Our results give a QMA-complete problem arising in the classical setting of Markov chains and adiabatically universal Hamiltonians that arise in many physical systems.
Additional Information
© 2010 The American Physical Society. Received 1 June 2009; revised 6 January 2010; published 29 March 2010. We thank Sergey Bravyi for a helpful discussion. S.J. thanks MIT's Center for Theoretical Physics, RIKEN's Digital Materials Laboratory, and Caltech's Institute for Quantum Information, Franco Nori, Sahel Ashhab, ARO/DTO's QuaCGR program, the US Department of Energy, the Sherman Fairchild Foundation, and the NSF for Grant No. PHY-0803371. D.G. thanks Eddie Farhi, the W. M. Keck Foundation Center for Extreme Quantum Information Theory, and the Natural Sciences and Engineering Research Council of Canada. P.J.L. thanks John Preskill and the Institute of Quantum Information at Caltech for hosting an extended visit, during which part of this work was completed. This research was supported in part by the National Science Foundation under Grant No. PHY05-51164.Attached Files
Published - Jordan2010p9885Phys_Rev_A.pdf
Files
Jordan2010p9885Phys_Rev_A.pdf
Additional details
Identifiers
- Eprint ID
- 18294
- Resolver ID
- CaltechAUTHORS:20100513-130915681
Funding
- Massachusetts Institute of Technology (MIT)
- RIKEN
- Institute for Quantum Information
- Franco Nori
- Sahel Ashhab
- Army Research Office (ARO)
- Department of Energy (DOE)
- Sherman Fairchild Foundation
- NSF
- PHY-0803371
- NSF
- PHY-0551164
- Natural Sciences and Engineering Research Council of Canada (NSERC)
Dates
- Created
-
2010-05-19Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field