Quantum entanglement, sum of squares, and the log rank conjecture

Boaz Barak, Pravesh Kothari, David Steurer

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…