Quantum-Merlin-Arthur-complete problems for stoquastic Hamiltonians and Markov matrices
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 stoq...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
American Physical Society
2010
|
| Online Access: | http://hdl.handle.net/1721.1/58980 |