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

with Boaz Barak, Pravesh Kothari. STOC 2017.



For every constant ϵ>0\epsilon>0, we give an exp(O~(n))\exp(\tilde{O}(\sqrt{n}))-time algorithm for the 11 vs 1ϵ1-\epsilon Best Separable State (BSS) problem of distinguishing, given an n2×n2n^2\times n^2 matrix M\mathcal M corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state ρ\rho that M\mathcal M accepts with probability 11, and the case that every separable state is accepted with probability at most 1ϵ1-\epsilon. Equivalently, our algorithm takes the description of a subspace WFn2\mathcal W\subseteq \mathbb F^{n^2} (where F\mathbb F can be either the real or complex field) and distinguishes between the case that W\mathcal W contains a rank one matrix, and the case that every rank one matrix is at least ϵ\epsilon far (in 2\ell_2 distance) from W\mathcal W.

To the best of our knowledge, this is the first improvement over the brute-force exp(n)\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-nn Boolean matrix is bounded by O~(n)\tilde{O}(\sqrt{n}).


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