Limitations of semidefinite programs for separable states and entangled games

Aram W. Harrow, Anand Natarajan, Xiaodi WuarXiv 2016 · DOI · OpenReview

TL;DR

This paper introduces a new technique to prove fundamental limitations on the power of semidefinite programming (SDP) relaxations, a crucial tool in quantum information theory. The authors demonstrate that these relaxations, specifically the sum-of-squares (SoS) hierarchy, cannot efficiently solve problems related to distinguishing entangled from separable quantum states and characterizing quantum correlations, even without relying on strong computational complexity assumptions.

What Problem Does This Paper Address?

Semidefinite programs (SDPs) are powerful optimization tools widely used in quantum information theory to tackle problems like identifying separable (unentangled) quantum states and understanding quantum correlations. While SDPs can provide exact solutions or good approximations, their efficiency and accuracy are often limited. Specifically, the "sum-of-squares" (SoS) hierarchy, a common SDP relaxation technique, has known limitations. Previously, proving these limitations for certain quantum information problems required assuming strong computational complexity conjectures like the Exponential Time Hypothesis (ETH). This paper addresses the challenge of establishing these limitations unconditionally, meaning without relying on such assumptions, and for a broader class of SDP relaxations.

Methods

The core of the paper's contribution lies in a novel reduction-based framework. The authors leverage a known hardness result for the 3XOR problem and "reduce" it to the quantum problems of interest. This involves constructing a series of transformations (reductions) that map instances of the hard classical problem to instances of the quantum problems. Crucially, these reductions are designed to preserve certain properties, ensuring that if the classical problem is hard for SoS, then the quantum problem will also be hard for SoS.

Key techniques include:

  • Low-degree reductions: These are carefully constructed transformations that preserve the "pseudo-solution" property, which is essential for proving integrality gaps.
  • Leveraging the Lee-Raghavendra-Steurer (LRS) framework: The authors extend the LRS technique, originally developed for boolean constraint satisfaction problems, to non-boolean domains relevant to quantum information. This allows them to establish lower bounds not just for SoS hierarchies but for a broader class of SDP "extended formulations."
  • Quantum interactive proof protocols: These protocols are used as a bridge to connect classical hardness results to quantum problems, particularly for the separability problem.

Datasets

Not discussed in the paper. The paper focuses on theoretical constructions and proofs rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unconditional hardness for quantum information problems: The most significant insight is the demonstration of fundamental limitations for SDP relaxations in quantum information theory without relying on ETH. This strengthens our understanding of what is computationally feasible in quantum information processing.
  • A unified framework for deriving SDP lower bounds: The paper presents a general methodology for establishing integrality gaps for SDPs through reductions, which can be applied to various optimization problems beyond those discussed.
  • Connecting classical and quantum complexity: The work highlights the deep connections between classical computational hardness (like 3XOR) and the limitations of quantum information processing tools.
  • Implications for approximate disentanglers: The hardness results for separability directly lead to a proof of a version of the "no approximate disentangler" conjecture, answering a long-standing question.

Key Results

  • Integrality gaps for the $2 \rightarrow 4$ norm and separable states: The paper establishes that the SoS hierarchy requires at least $\omega(1)$ levels (specifically, $\Omega(\log d / \text{poly}\log\log d)$ levels for the $2 \rightarrow 4$ norm and $\Omega(n)$ levels for separability) to approximate these problems within a constant factor. This is a significant improvement over previous results that relied on ETH.
  • Integrality gaps for quantum correlations: Similar unconditional limitations are shown for characterizing quantum correlations.
  • Lower bounds for SDP extended formulations: Using the LRS framework, the authors extend their SoS hardness results to a more general class of SDP relaxations, providing unconditional lower bounds on their size.
  • Dimension lower bounds for approximate disentanglers: The results imply that distinguishing between separable and entangled states requires a significant dimension for approximate disentanglers, answering a question by Watrous and Aaronson et al.

Limitations and Future Work

  • Gap between SoS and general SDP bounds: While the paper extends LRS to non-boolean domains, it acknowledges that the resulting SDP lower bounds are often weaker than the SoS lower bounds due to limitations in the LRS technique itself. The authors consider it a major open problem to improve these SDP lower bounds.
  • Matching ETH-based bounds: The unconditional results achieve parameters that are close to, but not always matching, the best known ETH-based hardness results. Further work is needed to bridge this gap.
  • Exploring other relaxations: The paper suggests investigating convex but non-SDP-based relaxations, such as entropic bounds.
  • Understanding upper-bound methods for games: The authors pose questions about whether existing upper-bound methods for entangled games can be understood more generally within the SoS hierarchy framework.
  • Strengthening bounds for quantum correlations: The paper calls for strengthening the results to match ETH-based bounds for quantum correlations.
  • Investigating generic states for DPS hierarchy: The authors suggest exploring whether their constructed states are "generic" in the sense of Lancien, which would have further implications for the DPS hierarchy.

Summary updated

Abstract

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 $\omega(1)$-round integrality gaps were known: the set of separable (i.e. unentangled) states, or equivalently, the $2 \rightarrow 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.
BibTeX
@misc{harrow2016limitations,
  author = {Aram W. Harrow and Anand Natarajan and Xiaodi Wu},
  title = {{Limitations of semidefinite programs for separable states and entangled games}},
  year = {2016},
  eprint = {1612.09306},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1612.09306},
}
Figure