Quantum Lunch Location:
T-Division Conference Room, TA-3,
Building 123, Room 121
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
IBM Watson Research Center
Computational Complexity of Spin Hamiltonian Problems
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.