A Simple Algorithm for Best Separable State

The Best Separable State (BSS) problem asks for the maximum probability that a quantum measurement accepts given unentangled (separable) states. In classical terms, this is equivalent to maximizing a degree-4 polynomial over the product of two unit spheres. While this problem is generally hard, the authors focus on the perfect completeness regime—where the maximum value is 1—and seek efficient algorithms to find a near-optimal solution.

The authors introduce a simplified rounding strategy for the Sum-of-Squares (SoS) hierarchy, a powerful framework for convex optimization. Their approach generalizes the "global correlation rounding" technique, which iteratively conditions (or "pins") variables to reduce the covariance of the pseudodistribution. By carefully analyzing the growth of a potential function—defined by the norms of the expected values of the vectors—they show that after pinning a relatively small number of coordinates, the resulting conditional pseudodistribution satisfies a "small covariance" condition. This condition guarantees that the rounded solution is close to the optimal value.

The paper provides two primary algorithmic results for the BSS problem with perfect completeness:

1. For any epsilon, the algorithm finds a solution with value 1-epsilon in time n^O(sqrt(n/epsilon)).
2. For any q, the algorithm finds a solution with value q/n in time n^O(sqrt(q)).

These results improve upon existing algorithms, specifically beating the previous subexponential time bounds for a wider range of parameters. Additionally, the authors prove a new variant of the "pinning lemma," a fundamental tool in high-dimensional probability and optimization, which they expect to be useful for other problems in the field.

BSS is a central problem in quantum complexity theory, linked to the complexity class QMA(2). Finding efficient algorithms for BSS has significant implications for understanding the power of quantum provers and the relationship between quantum and classical complexity classes. By simplifying the rounding analysis and improving the runtime, this work makes the SoS approach more accessible and provides a more efficient tool for tackling hard polynomial optimization problems.