



02093nas a2200145   4500008004100000245008200041210006900123260001500192490000800207520163800215100002101853700002101874700001501895856003701910       2019                        eng d00aLimitations of semidefinite programs for separable states and entangled games0 aLimitations of semidefinite programs for separable states and en  c03/04/20190 v3663 a<p>Semidefinite programs (SDPs) are a framework for exact or approximate optimization that have widespread application in quantum information theory. We introduce a new method for using reductions to construct integrality gaps for SDPs. These are based on new limitations on the sum-of-squares (SoS) hierarchy in approximating two particularly important sets in quantum information theory, where previously no ω(1)-round integrality gaps were known: the set of separable (i.e. unentangled) states, or equivalently, the 2&rarr;4 norm of a matrix, and 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). In some cases we can make use of the framework of Lee-Raghavendra-Steurer (LRS) to establish integrality gaps for any SDP, not only the SoS hierarchy. Our hardness result on separable states also yields a dimension lower bound of approximate disentanglers, answering a question of Watrous and Aaronson et al. These results can be viewed as limitations on the monogamy principle, the PPT test, the ability of Tsirelson-type bounds to restrict quantum correlations, as well as the SDP hierarchies of Doherty-Parrilo-Spedalieri, Navascues-Pironio-Acin and Berta-Fawzi-Scholz.</p>1 aHarrow, Aram, W.1 aNatarajan, Anand1 aWu, Xiaodi  uhttps://arxiv.org/abs/1612.09306