Hierarchies and nets for separable states

Add to your list(s) Download to your calendar using vCal

• Aram Harrow (MIT)
• Monday 20 April 2015, 16:00-17:00
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact William Matthews.

This talk has been canceled/deleted

Given a mixed quantum state, is it entangled or separable? This basic question turns out to be closely related to a wide range of problems in quantum information and classical optimization. These include QMA with multiple provers, mean-field theory, estimating minimum output entropies of quantum channels and the unique games conjecture. The leading algorithm known for this problem is the semidefinite programming (SDP) hierarchy due to Doherty, Parrilo and Spedalieri (DPS). In this talk I will describe recent progress on finding algorithms for optimizing over separable states.

1. The DPS hierarchy is known to never converge at any finite level in any dimension where entangled states with positive partial transpose exist. I will describe an improved version which always does at least as well as DPS and converges exactly at a finite level. This yields an exponential time algorithm for exact separability testing.

2. On the negative 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 error, or n^{Omega(1)} levels are needed for 1/poly(n) error) but now are proved unconditionally. Previously these were only known to hold based on the assumption that 3-SAT required exponential time.

3. Some of the strongest known results about the DPS hierarchy are due to Brandao, Christandl and Yard, and show that after O(log(n)) levels it already gives nontrivial approximations in the norm induced by 1-LOCC measurements. I will describe 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.

1 & 2 are joint work with Anand Natarajan and Xiaodi Wu. 3 is joint work with Fernando Brandao.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

This talk is not included in any other list

Note that ex-directory lists are not shown.