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

For every constant ε>0, we give an exp(Õ(∞ n ))-time algorithm for the 1 vs 1 - ε Best Separable State (BSS) problem of distinguishing, given an n 2 x n 2 matrix ℳ corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state ρ that ℳ accepts with probability 1, and the case that every separable state is accepted with probability at most 1 - ε. Equivalently, our algorithm takes the description of a subspace 𝒲 ⊆ 𝔽 n 2 (where 𝔽 can be either the real or complex field) and distinguishes between the case that contains a rank one matrix, and the case that every rank one matrix is at least ε far (in 𝓁 2 distance) from 𝒲. 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 Õ(√ n ).

Authors

• Boaz Barak
• Pravesh K. Kothari
• David Steurer

Keywords

• Best Separable State Problem
• Polynomial Reweighting
• Sum-of-Squares Semidefinite Programming Hierarchy