A Simple Algorithm for Best Separable State

Abstract

We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states. In classical terms, the goal is to maximize $\langle(x \otimes y), M (x \otimes y)\rangle$ over unit vectors $x,y$ where $0 \preceq M \preceq I$; we call this value $\mathrm{BSS}(M)$. We study $\mathrm{BSS}$ in the"perfect completeness"regime, where given $M$ such that $\mathrm{BSS}(M) = 1$ the goal is to find the best possible solution $x,y$ -- this generalizes the problem of finding a rank-one matrix as close as possible to a given subspace of $\mathbb{R}^{n \times n}$ guaranteed to contain a rank-one matrix. The strongest known algorithmic guarantees for this problem are: (1) an algorithm which finds a solution with value $1-\varepsilon$ in time $\exp(\sqrt{n} (\log n)^{O(1)} / \varepsilon^2)$, due to Barak, Kothari, and Steurer, and (2) an algorithm which finds a solution with value $q/n$ in time roughly $n^{O(q)}$, due to Bhattiprolu, Ghosh, Guruswami, Lee, and Tulsiani. We give a much simpler approach to rounding the SoS relaxation, generalizing the canonical"global correlation rounding"technique, and obtain a better running time. Given $M$ with $\mathrm{BSS}(M) = 1$, our algorithm finds a solution with value $1-\epsilon$ in time $n^{O(\sqrt{n/\varepsilon})}$, and a solution of value $q/n$ in time $n^{O(\sqrt q)}$. Using the same techniques, we prove a new variant of the"pinning lemma", a measure-decomposition theorem widely used in LP/SDP rounding, high-dimensional probability, and statistical physics, which we believe is of independent interest.