BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Hierarchies and nets for separable states - Aram Harrow (MIT)
DTSTART:20150420T150000Z
DTEND:20150420T160000Z
UID:TALK59126@talks.cam.ac.uk
CONTACT:William Matthews
DESCRIPTION:Given a mixed quantum state\, is it entangled or separable?  T
 his basic question turns out to be closely related to a wide range of prob
 lems in quantum information and classical optimization.  These include QMA
  with multiple provers\, mean-field theory\, estimating minimum output ent
 ropies of quantum channels and the unique games conjecture.  The leading a
 lgorithm known for this problem is the semidefinite programming (SDP) hier
 archy due to Doherty\, Parrilo and Spedalieri (DPS).  In this talk I will 
 describe recent progress on finding algorithms for optimizing over separab
 le states.\n\n1. The DPS hierarchy is known to never converge at any finit
 e level in any dimension where entangled states with positive partial tran
 spose exist.  I will describe an improved version which always does at lea
 st as well as DPS and converges exactly at a finite level.  This yields an
  exponential time algorithm 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 separability testing. These limitations match the 
 previously known bounds (Omega(log(n)) levels are required for constant er
 ror\, or n^{Omega(1)} levels are needed for 1/poly(n) error) but now are p
 roved unconditionally.  Previously these were only known to hold based on 
 the assumption that 3-SAT required exponential time.\n\n3. Some of the str
 ongest known results about the DPS hierarchy are due to Brandao\, Christan
 dl and Yard\, and show that after O(log(n)) levels it already gives nontri
 vial approximations in the norm induced by 1-LOCC measurements.  I will de
 scribe an alternate algorithm achieving similar performance based instead 
 on brute-force enumeration over epsilon nets.  This algorithm admits some 
 natural generalizations and also gives some geometric intuition for why 1-
 LOCC measurements are especially easy to handle.\n\n1 & 2 are joint work w
 ith Anand Natarajan and Xiaodi Wu.  3 is joint work with Fernando Brandao.
LOCATION:MR15\,  Centre for Mathematical Sciences\, Wilberforce Road\, Cam
 bridge
END:VEVENT
END:VCALENDAR