Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture
Pravesh Kothari, Princeton University
This talk will be about a sub-exponential time algorithm for the Best Separable State (BSS) problem. For every constant \eps>0, we give an exp(\sqrt(n) \poly log(n))-time algorithm for the 1 vs 1-\eps BSS problem of distinguishing, given an n^2 x n^2 matrix M corresponding to a quantum measurement, between the case that there is a separable (i.e., non-entangled) state \rho that M accepts with probability 1, and the case that every separable state is accepted with probability at most 1-\eps.
Equivalently, our algorithm takes the description of a subspace W \subset F^{n^2} (where F can be either the real or complex field) and distinguishes between the case that W contains a rank one matrix, and the case that every rank one matrix is at least \eps far (in Euclidean distance) from W.
The algorithm is based on the sum-of-squares semidefinite programming hierarchy - a powerful hierarchy of semidefinite programming relaxations that has recently been used to design fast approximation algorithms for problems in combinatorial optimization, machine learning and quantum information.
In this talk, I'll use the BSS problem as an example to illustrate a general rounding paradigm for the sum-of-squares algorithm. Somewhat surprisingly, a key technical step in the instantiation of this paradigm to analyze a rounding scheme for the BSS problem will be inspired by the recent breakthrough on the log-rank conjecture of Lovett (STOC'14, JACM'16) who showed that the communication complexity of every rank-n Boolean matrix is bounded by \sqrt{n} poly log(n).
The talk will assume no specialized background.
Based on joint work with Boaz Barak (Harvard) and David Steurer (Cornell, IAS).