[QIP-Sem] QIP seminar, Monday, 4pm, 26-216: Sergey Bravyi

[Daniel Nagaj]

Seminar announcement:
--

Mon 9/18, 4pm in 26-214 (Quantum Information Processing seminar)

Sergey Bravyi (IBM)

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.