RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

Quantum Entanglement, Sum-of-Squares and the Log-Rank Conjecture

February 22, 2017 - 11:00am
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). 
CSS 3100A

Subscribe to A Quantum Bit 

Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...

Sign Up Now

Sign up to receive A Quantum Bit in your email!

 Have an idea for A Quantum Bit? Submit your suggestions to