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

with , . STOC 2017. pdf
(to appear).

## abstract

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

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 $$\tilde{O}(\sqrt{n})$$.

## keywords

sum-of-squares method, tensor computations, quantum information, semidefinite programming, small-set expansion.