A Caltech Library Service

Quantum-Merlin-Arthur–complete problems for stoquastic Hamiltonians and Markov matrices

Jordan, Stephen P. and Gosset, David and Love, Peter J. (2010) Quantum-Merlin-Arthur–complete problems for stoquastic Hamiltonians and Markov matrices. Physical Review A, 81 (3). Art. No. 032331 . ISSN 1050-2947.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription DOIArticle
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.
Funding AgencyGrant Number
Massachusetts Institute of Technology (MIT)UNSPECIFIED
Institute for Quantum InformationUNSPECIFIED
Army Research Office (ARO)UNSPECIFIED
Department of Energy (DOE)UNSPECIFIED
Sherman Fairchild FoundationUNSPECIFIED
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Issue or Number:3
Classification Code:PACS: 03.67.Ac, 75.10.Jm, 89.70.Eg
Record Number:CaltechAUTHORS:20100513-130915681
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:18294
Deposited By: Tony Diaz
Deposited On:19 May 2010 16:43
Last Modified:03 Oct 2019 01:40

Repository Staff Only: item control page