A Caltech Library Service

Limitations of Semidefinite Programs for Separable States and Entangled Games

Harrow, Aram W. and Natarajan, Anand and Wu, Xiaodi (2019) Limitations of Semidefinite Programs for Separable States and Entangled Games. Communications in Mathematical Physics, 366 (2). pp. 423-468. ISSN 0010-3616.

[img] PDF - Accepted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Semidefinite programs (SDPs) are a framework for exact or approximate optimization with widespread application in quantum information theory. We introduce a new method for using reductions to construct integrality gaps for SDPs, meaning instances where the SDP value is far from the true optimum. 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: 1. The set of separable (i.e. unentangled) states, or equivalently, the 2→4 norm of a matrix. 2. The set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state. Integrality gaps for the 2→4 norm had previously been sought due to its connection to Small-Set Expansion (SSE) and Unique Games (UG). 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 extended formulation, 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. Indeed a wide range of past work in quantum information can be described as using an SDP on one of the above two problems and our results put broad limits on these lines of argument.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access Paper
Harrow, Aram W.0000-0003-3220-7682
Natarajan, Anand0000-0003-3648-3844
Additional Information:© Springer-Verlag GmbH Germany, part of Springer Nature 2019. Received: 22 February 2017 / Accepted: 30 April 2018 / First Online: 04 March 2019. AWH and AN were funded by NSF Grant CCF-1629809 and AWH was funded by NSF grant CCF-1452616. XW was funded by the NSF Waterman Award of Scott Aaronson. All three authors (AWH, AN, and XW) were funded by ARO contract W911NF-12-1-0486. We are grateful to an anonymous STOC reviewer for pointing out a mistake in an earlier version.
Funding AgencyGrant Number
Army Research Office (ARO)W911NF-12-1-0486
Record Number:CaltechAUTHORS:20190304-095657663
Persistent URL:
Official Citation:Harrow, A.W., Natarajan, A. & Wu, X. Commun. Math. Phys. (2019) 366: 423.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93426
Deposited By: George Porter
Deposited On:04 Mar 2019 18:12
Last Modified:15 Mar 2019 15:11

Repository Staff Only: item control page