Quantum Institute: Visitor Schedule

The Quantum Lunch is regularly held on Thursdays in the Theoretical Division Conference Room, TA-3, Building 123, Room 121. For more information, contact Diego Dalvit.

May 23 , 2006
12:30 PM, Tuesday

Sergey Bravyi,
IBM Watson Research Center

Computational Complexity of Spin Hamiltonian Problems

Abstract

Evaluation of the smallest eigenvalue of a quantum spin Hamiltonian with interactions involving only a few spins is known as the "Local Hamiltonian Problem" (LHP). We study computational complexity of LHP in the special case when a Hamiltonian obeys conditions of the Perron-Frobenius theorem: all off-diagonal matrix elements in the standard basis are real and non-positive. Equivalently, a Hamiltonian must have non-negative Gibbs matrix (NGM) for any temperature. We prove that LHP with NGM Hamiltonian belongs to the complexity class AM—probabilistic version of NP with two rounds of communication between the prover and the verifier. Also we show that NGM LHP is hard for the class MA. With the additional promise of Hamiltonian having a polynomial spectral gap, we show that NGM LHP belongs to the class POSTBPP—a generalization of BPP in which a post selective readout is allowed.

This is a joint work with David DiVincenzo and Barbara Terhal.