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:CQIF Seminar
SUMMARY:Hierarchies and nets for separable states - Aram H
arrow (MIT)
DTSTART;TZID=Europe/London:20150420T160000
DTEND;TZID=Europe/London:20150420T170000
UID:TALK59126AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/59126
DESCRIPTION:Given a mixed quantum state\, is it entangled or s
eparable? This basic question turns out to be clo
sely related to a wide range of problems in quantu
m information and classical optimization. These i
nclude QMA with multiple provers\, mean-field theo
ry\, estimating minimum output entropies of quantu
m channels and the unique games conjecture. The l
eading algorithm known for this problem is the sem
idefinite programming (SDP) hierarchy due to Doher
ty\, Parrilo and Spedalieri (DPS). In this talk I
will describe recent progress on finding algorith
ms for optimizing over separable states.\n\n1. The
DPS hierarchy is known to never converge at any f
inite level in any dimension where entangled state
s with positive partial transpose exist. I will d
escribe an improved version which always does at l
east as well as DPS and converges exactly at a fin
ite level. This yields an exponential time algori
thm for exact separability testing.\n\n2. On the n
egative side\, I will show limitations on both DPS
\, the improved version\, or indeed any SDP for se
parability testing. These limitations match the pr
eviously known bounds (Omega(log(n)) levels are re
quired for constant error\, or n^{Omega(1)} levels
are needed for 1/poly(n) error) but now are prove
d unconditionally. Previously these were only kno
wn to hold based on the assumption that 3-SAT requ
ired exponential time.\n\n3. Some of the strongest
known results about the DPS hierarchy are due to
Brandao\, Christandl and Yard\, and show that afte
r O(log(n)) levels it already gives nontrivial app
roximations in the norm induced by 1-LOCC measurem
ents. I will describe an alternate algorithm achi
eving similar performance based instead on brute-f
orce enumeration over epsilon nets. This algorith
m admits some natural generalizations and also giv
es some geometric intuition for why 1-LOCC measure
ments are especially easy to handle.\n\n1 & 2 are
joint work with Anand Natarajan and Xiaodi Wu. 3
is joint work with Fernando Brandao.
LOCATION:MR15\, Centre for Mathematical Sciences\, Wilberf
orce Road\, Cambridge
CONTACT:William Matthews
END:VEVENT
END:VCALENDAR