BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:New de Finetti theorems and the quantum PCP conjecture - Aram Harr
 ow (MIT)
DTSTART:20130326T140000Z
DTEND:20130326T150000Z
UID:TALK44225@talks.cam.ac.uk
CONTACT:Ashley Montanaro
DESCRIPTION:The quantum de Finetti theorem states that subsystems of symme
 tric quantum states are close to mixtures of i.i.d. states.  Depending on 
 exactly how "close" is quantified\, this theorem can have many application
 s to quantum information theory\, quantum complexity theory\, and even cla
 ssical optimization algorithms.  However\, previous bounds scaled badly wi
 th either dimension or the number of systems.  I'll give an overview of wh
 y de Finetti theorems are useful\, describe a way to use information theor
 y to improve existing bounds\, and discuss\napplications and open problems
 .  One application of particular interest is finding k-body Hamiltonians w
 hose ground-state energy can be approximately achieved by product states. 
  This can be used to show\nthat the problem of estimating the ground-state
  energy of a k-body Hamiltonian is in some cases contained in NP (thus pro
 viding evidence against the quantum PCP conjecture) and in other cases con
 tained in P.\n\nBased on joint work with Fernando Brandao\, some unpublish
 ed\, and some in 1210.6367.
LOCATION:MR14\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR