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

Creators: Jordan, Stephen P.; Gosset, David; Love, Peter J.

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

Files (192.6 kB)

Name	Size	Download all
Jordan2010p9885Phys_Rev_A.pdf md5:812ac3c79ccad6dd2bb9bff651239738	192.6 kB	Preview Download

Additional details

	All versions	This version
Views	0	0
Downloads	0	0
Data volume	0 Bytes	0 Bytes