Limitations of semidefinite programs for separable states and entangled games
arXiv:1612.09306 · doi:10.1007/s00220-019-03382-y
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 -round integrality gaps were known: the set of separable (i.e. unentangled) states, or equivalently, the 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.
arXiv comment47 pages. v2. small changes, fixes and clarifications. published version
References in corpus (41)
- Separability Criterion for Density Matrices
- Separability of Mixed States: Necessary and Sufficient Conditions
- No Signalling and Quantum Key Distribution
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- Unknown Quantum States: The Quantum de Finetti Representation
- A complete family of separability criteria
- A limit on nonlocality in any world in which communication complexity is not trivial
- Quantum Data Hiding
- One-and-a-half quantum de Finetti theorems
- Faithful Squashed Entanglement
- Sum-of-squares decompositions for a family of CHSH-like inequalities and their application to self-testing
- Hypercontractivity, Sum-of-Squares Proofs, and their Applications
- The Pauli principle revisited
- Convergent relaxations of polynomial optimization problems with non-commuting variables
- All entangled states are useful for information processing
- A de Finetti representation for finite symmetric quantum states
- Finite blocklength converse bounds for quantum channels
- The power of symmetric extensions for entanglement detection
- Remarks on additivity of the Holevo channel capacity and of the entanglement of formation
- Limitations on Quantum Key Repeaters
- Markov entropy decomposition: a variational dual for quantum belief propagation
- Entanglement of the Antisymmetric State
- Positive polynomials in scalar and matrix variables, the spectral theorem and optimization
- Tsirelson's Problem
- Connecting N-representability to Weyl's problem: The one particle density matrix for N = 3 and R = 6
- Convergence of SDP hierarchies for polynomial optimization on the hypersphere
- An improved semidefinite programming hierarchy for testing entanglement
- Quantum Bilinear Optimization
- Three-player entangled XOR games are NP-hard to approximate
- Approximating the Set of Separable States Using the Positive Partial Transpose Test
- Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements
- The Complexity of the Consistency and N-representability Problems for Quantum States
- Classical command of quantum systems via rigidity of CHSH games
- Sum-of-Squares Certificates for Maxima of Random Tensors on the Sphere
- Multi-Prover Quantum Merlin-Arthur Proof Systems with Small Gap
- Detecting Consistency of Overlapping Quantum Marginals by Separability
- A quantum characterization of NP
- -extendibility of high-dimensional bipartite quantum states
- The Pauli principle and magnetism
- Dvoretzky's Theorem and the Complexity of Entanglement Detection
- A most compendious and facile quantum de Finetti theorem
Cited by in corpus (6)
- Semidefinite programming hierarchies for constrained bilinear optimization
- Naturally restricted subsets of nonsignaling correlations: typicality and convergence
- Dvoretzky's Theorem and the Complexity of Entanglement Detection
- Probabilistic state synthesis based on optimal convex approximation
- Five Starter Pieces: Quantum Information Science via Semi-definite Programs
- Inapproximability of Matrix Norms