  For every $\epsilon>0$, we give an
$\exp(\tilde{O}(\sqrt{n}/\epsilon^2))$-time algorithm for the $1$ vs
$1-\epsilon$ \emph{Best Separable State (BSS)} problem of distinguishing, given
an $n^2\times n^2$ matrix $\mathcal{M}$ corresponding to a quantum measurement,
between the case that there is a separable (i.e., non-entangled) state $\rho$
that $\mathcal{M}$ 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 $\mathcal{W}
\subseteq \mathbb{F}^{n^2}$ (where $\mathbb{F}$ can be either the real or
complex field) and distinguishes between the case that $\mathcal{W}$ contains a
rank one matrix, and the case that every rank one matrix is at least $\epsilon$
far (in $\ell_2$ distance) from $\mathcal{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 \emph{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 $\tilde{O}(\sqrt{n})$.

Quantum Physics;Data Structures and Algorithms