Abstract
In this talk, I’ll describe a sub-exponential time algorithm for the Best Separable State (BSS) problem (see next paragraph for a classical algorithmic formulation). Aside from being a central question in quantum information theory arising in the study of entanglement, recent works have uncovered potentially useful connections between BSS and fundamental problems in classical algorithm design such as Small-Set-Expansion, Max-Cut and Unique Games. For every constant \epsilon>0, we give an \exp(\sqrt(n) \poly log(n))-time algorithm for the 1 vs 1-\epsilon-BSS problem of distinguishing, given an n^2 \times n^2 matrix M corresponding to a quantum measurement, between the cases that there is a separable (i.e., non-entangled) state \rho that accepts with probability 1, and the case that every separable state is accepted with probability at most 1-\epsilon.
Equivalently, our algorithm takes the description of a subspace W \subset F^{n^2} (where F is either the real or the complex field) and distinguishes between the case that W contains a rank one matrix, and the case that every rank one matrix is at least \epsilon far (in the Euclidean distance) from W.
The algorithm is based on a general rounding paradigm that uses polynomial reweightings to round the solution to the Sum-of-Squares (SoS) semidefinite programming relaxations. Somewhat surprisingly, a key technical step in analyzing this rounding scheme is inspired by the recent breakthrough on the log-rank conjecture by Lovett (STOC’14, JACM’16) who showed that the communication complexity of every rank-n Boolean matrix is bounded by \sqrt{n} poly log(n).
Based on joint work with Boaz Barak (Harvard) and David Steurer (Cornell, IAS).