BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Complexity classification of local Hamiltonian problems - Montanar
 o\, A (University of Bristol)
DTSTART:20131127T160000Z
DTEND:20131127T170000Z
UID:TALK49058@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:Co-author: Toby Cubitt (University of Cambridge) \n\nThe calcu
 lation of ground-state energies of physical systems can be formalised as t
 he k-local Hamiltonian problem\, which is the natural quantum analogue of 
 classical constraint satisfaction problems. One way of making the problem 
 more physically meaningful is to restrict the Hamiltonian in question by p
 icking its terms from a fixed set S. Examples of such special cases are th
 e Heisenberg and Ising models from condensed-matter physics.\n \nIn this t
 alk I will discuss work which characterises the complexity of this problem
  for all 2-local qubit Hamiltonians. Depending on the subset S\, the probl
 em falls into one of the following categories: in P\; NP-complete\; polyno
 mial-time equivalent to the Ising model with transverse magnetic fields\; 
 or QMA-complete. The third of these classes contains NP and is contained w
 ithin StoqMA. The characterisation holds even if S does not contain any 1-
 local terms\; for example\, we prove for the first time QMA-completeness o
 f the Heisenberg and XY interactions in this setting. If S is assumed to c
 ontain all 1-local terms\, which is the setting considered by previous wor
 k\, we have a characterisation that goes beyond 2-local interactions: for 
 any constant k\, all k-local qubit Hamiltonians whose terms are picked fro
 m a fixed set S correspond to problems either in P\; polynomial-time equiv
 alent to the Ising model with transverse magnetic fields\; or QMA-complete
 .\n\nThese results are a quantum analogue of Schaefer's dichotomy theorem 
 for boolean constraint satisfaction problems.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR