# Institute for Quantum Information Seminar

Tuesday
February 21, 2012
3:00 PM

**The complexity of the Local Separable Hamiltonian Problem lem **

**Speaker:**AndrĂ© Chailloux, University of California, Berkeley

**Location:**Annenberg 107

We study variants of the canonical Local-Hamiltonian problem where, in addition, the witness is promised to be separable. We define two variants of the Local-Hamiltonian problem. The input for the Separable-Local-Hamiltonian problem is the same as the Local-Hamiltonian problem, i.e. a local Hamiltonian and two energies a and b, but the question is somewhat different: the answer is YES if there is a separable quantum state with energy at most a, and the answer is NO if all separable quantum states have energy at least b.
The Separable-Sparse-Hamiltonian problem is defined similarly, but the Hamiltonian is not necessarily local, but rather sparse. We show that the Separable-Sparse-Hamiltonian problem is QMA(2)-Complete, while Separable-Local-Hamiltonian is in QMA. This should be compared to the Local-Hamiltonian problem, and the Sparse-Hamiltonian problem which are both QMA-Complete. To the best of our knowledge, Separable-SPARSE-Hamiltonian is the first non-trivial problem shown to be QMA(2)-Complete.
Joint work with Or Sattath.

**Series**Institute for Quantum Information Seminar

**Contact:** Ann Harvey at 4964 aharvey@caltech.edu