Dr. Sergey Bravyi

IBM T.J. Watson Research Centre
10598 YORKTOWN HEIGHTS NY

Ground state problems for spin Hamiltonians with non-positive matrix elements

Ground state problems for interacting quantum spins are analyzed using techniques from complexity theory. I focus on the problem of evaluating the smallest eigenvalue of a spin Hamiltonian with non-positive matrix elements. This problem is shown to be contained in the complexity class AM and be hard for the class MA (probabilistic analogues of NP with one (MA) and two (AM) rounds of communication between the prover and the verifier). I also consider the smallest eigenvalue problem for frustration free Hamiltonians (quantum analogue of k-SAT) and prove that it is MA-complete. If no restrictions on the matrix elements are imposed, both problems are complete for QMA --- quantum analogue of NP. These results can be viewed as a strict version of folklore knowledge: Hamiltonians avoiding the "sign problem" are easy to simulate.