University of Cambridge > Talks.cam > CQIF Seminar > Hierarchies and nets for separable states

Hierarchies and nets for separable states

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

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity