Special IQI Seminar

We introduce a method for using reductions to prove limitations on the ability of semidefinite programs (SDPs) to approximately solve optimization problems. We use this to show specifically that SDPs have limited ability to approximate two particularly important sets in quantum information theory:   * The set of separable (i.e. unentangled) states. * The set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state.

 

In both cases no-go theorems were previously known based on computational assumptions such as the Exponential Time Hypothesis (ETH) which asserts that 3-SAT requires exponential time to solve. Our unconditional results achieve the same parameters as all of these previous results (for separable states) or as some of the previous results (for quantum correlations) and show that any SDPs which approximately solve either of these problems must have a number of variables which grows very quickly with problem size.

These results can be viewed as limitations on various ideas from quantum information (including the monogamy principle, the PPT test, Tsirelson-type inequalities) for understanding entanglement. Many of these ideas have been formalized into SDP hierarchies by Doherty-Parrilo-Spedalieri, Navascues-Pironio-Acin and Berta-Fawzi-Scholz, all of which we establish limits on the effectiveness of.   Joint work with Aram Harrow and Anand Natarajan