Quantum entanglement, sum of squares, and the log rank conjecture
with Boaz Barak, Pravesh Kothari. STOC 2017.
For every constant , we give an -time algorithm for the vs Best Separable State (BSS) problem of distinguishing, given an matrix corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state that accepts with probability , and the case that every separable state is accepted with probability at most . Equivalently, our algorithm takes the description of a subspace (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 distance) from .
To the best of our knowledge, this is the first improvement over the brute-force -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- Boolean matrix is bounded by .
- sum-of-squares method
- tensor computations
- quantum information
- semidefinite programming
- small-set expansion