For every constant 0"> 0 , we give an exp ( O ( n )) -time algorithm for the 1 vs 1 − Best Separable State (BSS) problem of distinguishing, given an n 2 n 2 matrix M corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state that M accepts with probability 1 , and the case that every separable state is accepted with probability at most 1 − . Equivalently, our algorithm takes the description of a subspace W F n 2 (where F can be either the real or 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 far (in 2 distance) from W .

To the best of our knowledge, this is the first improvement over the brute-force exp ( n ) -time algorithm for this problem. Our algorithm is based on the *sum-of-squares* hierarchy and its analysis is inspired by Lovett's proof (STOC '14, JACM '16) that the communication complexity of every rank- n Boolean matrix is bounded by O ( n ) .