BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Isaac Newton Institute Seminar Series
SUMMARY:Complexity classification of local Hamiltonian pro
blems - Montanaro\, A (University of Bristol)
DTSTART;TZID=Europe/London:20131127T160000
DTEND;TZID=Europe/London:20131127T170000
UID:TALK49058AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/49058
DESCRIPTION:Co-author: Toby Cubitt (University of Cambridge) \
n\nThe calculation of ground-state energies of phy
sical systems can be formalised as the k-local Ham
iltonian problem\, which is the natural quantum an
alogue of classical constraint satisfaction proble
ms. One way of making the problem more physically
meaningful is to restrict the Hamiltonian in quest
ion by picking its terms from a fixed set S. Examp
les of such special cases are the Heisenberg and I
sing models from condensed-matter physics.\n \nIn
this talk I will discuss work which characterises
the complexity of this problem for all 2-local qub
it Hamiltonians. Depending on the subset S\, the p
roblem falls into one of the following categories:
in P\; NP-complete\; polynomial-time equivalent t
o the Ising model with transverse magnetic fields\
; or QMA-complete. The third of these classes cont
ains NP and is contained within StoqMA. The charac
terisation holds even if S does not contain any 1-
local terms\; for example\, we prove for the first
time QMA-completeness of the Heisenberg and XY in
teractions in this setting. If S is assumed to con
tain all 1-local terms\, which is the setting cons
idered by previous work\, we have a characterisati
on that goes beyond 2-local interactions: for any
constant k\, all k-local qubit Hamiltonians whose
terms are picked from a fixed set S correspond to
problems either in P\; polynomial-time equivalent
to the Ising model with transverse magnetic fields
\; or QMA-complete.\n\nThese results are a quantum
analogue of Schaefer's dichotomy theorem for bool
ean constraint satisfaction problems.\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR