Limitations of semidefinite programs for separable states and entangled games
From MaRDI portal
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.
Recommendations
- An improved semidefinite programming hierarchy for testing entanglement
- A quasipolynomial-time algorithm for the quantum separability problem
- The set of separable states has no finite semidefinite representation except in dimension \(3\times 2\)
- A semidefinite program for distillable entanglement
- Bounding the separable rank via polynomial optimization
Cites work
- scientific article; zbMATH DE number 1489808 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- A de Finetti representation for finite symmetric quantum states
- A most compendious and facile quantum de Finetti theorem
- A positivstellensatz for non-commutative polynomials
- A semidefinite program for distillable entanglement
- All bipartite entangled states are useful for information processing
- An approach to obtaining global extremums in polynomial mathematical programming problems
- An improved semidefinite programming hierarchy for testing entanglement
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- Approximating the set of separable states using the positive partial transpose test
- CSP gaps and reductions in the lasserre hierarchy
- Classical deterministic complexity of Edmonds' Problem and quantum entanglement
- Complementarity and Cirel'son's inequality
- Computational Complexity
- ConnectingN-representability to Weyl's problem: the one-particle density matrix forN= 3 andR= 6
- Convergent relaxations of polynomial optimization problems with noncommuting variables
- Dvoretzky's theorem and the complexity of entanglement detection
- Entangled games are hard to approximate
- Entanglement of the antisymmetric state
- Faithful squashed entanglement
- Finite Blocklength Converse Bounds for Quantum Channels
- Finite exchangeable sequences
- Global optimization with polynomials and the problem of moments
- Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
- Hypercontractivity, sum-of-squares proofs, and their applications
- Inapproximability of combinatorial problems via small LPs and SDPs
- Limit on nonlocality in any world in which communication complexity is not trivial
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Lower bounds on the size of semidefinite programming relaxations
- NP vs QMA\(_{\log}(2)\)
- On Khot’s unique games conjecture
- On QMA protocols with two short quantum proofs
- On the Power of the PPT Constraint in the Symmetric Extensions Test for Separability
- On the complexity of \(k\)-SAT
- On the power of unique 2-prover 1-round games
- One-and-a-half quantum de Finetti theorems
- Optimization, approximation, and complexity classes
- Positive polynomials in scalar and matrix variables, the spectral theorem, and optimization
- Product-state approximations to quantum ground states
- Quantum bilinear optimization
- Quantum data hiding
- Quantum de finetti theorems under local measurements with applications
- Random constructions in Bell inequalities: a survey
- Remarks on additivity of the Holevo channel capacity and of the entanglement of formation
- Rounding sum-of-squares relaxations
- Separability Criterion for Density Matrices
- Separability of mixed states: necessary and sufficient conditions.
- Strong NP-hardness of the quantum separability problem
- Sum-of-squares certificates for maxima of random tensors on the sphere
- Sum-of-squares proofs and the quest toward optimal algorithms
- Sums of squares, moment matrices and optimization over polynomials
- Testing product states, quantum Merlin-Arthur games and tensor optimization
- The Pauli principle revisited
- The power of unentanglement
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Unknown quantum states: The quantum de Finetti representation
- \(k\)-extendibility of high-dimensional bipartite quantum states
Cited in
(11)- Product Theorems Via Semidefinite Programming
- Semi-definite programming and quantum information
- Quantum bilinear optimization
- Hardness amplification for entangled games via anchoring
- A family of norms with applications in quantum information theory. II
- Product Rules in Semidefinite Programming
- Semidefinite programming hierarchies for constrained bilinear optimization
- Dvoretzky's theorem and the complexity of entanglement detection
- An improved semidefinite programming hierarchy for testing entanglement
- scientific article; zbMATH DE number 7559121 (Why is no real title available?)
- A semidefinite program for distillable entanglement
This page was built for publication: Limitations of semidefinite programs for separable states and entangled games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1731116)
