Colloquium: Pravesh Kothari
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.