Xiaodi Wu, Massachusetts Institute of Technology
In this talk, I will present a stronger version of the Doherty-Parrilo-Spedalieri (DPS) hierarchy of approximations for the set of separable states. Unlike DPS, our hierarchy converges exactly at a finite number of rounds for any fixed input dimension. This yields an algorithm for separability testing which is singly exponential in dimension and poly-logarithmic in accuracy.
Our analysis makes use of tools from algebraic geometry, but our algorithm is elementary and differs from DPS only by one simple additional collection of constraints. The fact that algebraic geometry comes into play is due to the intimate connection between the DPS hierarchy and the sum-of-squares relaxation hierarchy (i.e, Lasserre/Parrilo hierarchy) for optimization over separable states. No algebraic geometry background is assumed for the talk.
Joint work with Aram Harrow and Anand Natarajan.