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

with Boaz Barak, Pravesh Kothari. STOC 2017.

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 $\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 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