Limitations of semidefinite programs for separable states and entangled games
From MaRDI portal
Publication:1731116
DOI10.1007/s00220-019-03382-yzbMath1410.81012arXiv1612.09306OpenAlexW2569308491WikidataQ128302042 ScholiaQ128302042MaRDI QIDQ1731116
Xiaodi Wu, Anand Natarajan, Aram W. Harrow
Publication date: 20 March 2019
Published in: Communications in Mathematical Physics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1612.09306
Semidefinite programming (90C22) 2-person games (91A05) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)
Related Items
Semidefinite programming hierarchies for constrained bilinear optimization, Dvoretzky's theorem and the complexity of entanglement detection
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An improved semidefinite programming hierarchy for testing entanglement
- Remarks on additivity of the Holevo channel capacity and of the entanglement of formation
- Faithful squashed entanglement
- Finite exchangeable sequences
- Optimization, approximation, and complexity classes
- Random constructions in Bell inequalities: a survey
- Strong reductions for extended formulations
- Separability of mixed states: necessary and sufficient conditions.
- One-and-a-half quantum de Finetti theorems
- Entanglement of the antisymmetric state
- The Pauli principle revisited
- Global Optimization with Polynomials and the Problem of Moments
- k-Extendibility of high-dimensional bipartite quantum states
- Inapproximability of Combinatorial Problems via Small LPs and SDPs
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Finite Blocklength Converse Bounds for Quantum Channels
- Convergent Relaxations of Polynomial Optimization Problems with Noncommuting Variables
- Entangled Games Are Hard to Approximate
- Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial
- All Bipartite Entangled States Are Useful for Information Processing
- On Khot’s unique games conjecture
- Quantum Bilinear Optimization
- A de Finetti representation for finite symmetric quantum states
- On the power of unique 2-prover 1-round games
- Classical deterministic complexity of Edmonds' Problem and quantum entanglement
- A most compendious and facile quantum de Finetti theorem
- An approach to obtaining global extremums in polynomial mathematical programming problems
- Complementarity and Cirel'son's inequality
- Separability Criterion for Density Matrices
- A semidefinite program for distillable entanglement
- Quantum data hiding
- Sum-of-squares proofs and the quest toward optimal algorithms
- Dvoretzky's theorem and the complexity of entanglement detection
- A positivstellensatz for non-commutative polynomials
- Unknown quantum states: The quantum de Finetti representation
- Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs
- CSP gaps and reductions in the lasserre hierarchy
- On the Power of the PPT Constraint in the Symmetric Extensions Test for Separability
- Tsirelson’s problem and an embedding theorem for groups arising from non-local games
- Approximating the set of separable states using the positive partial transpose test
- Rounding sum-of-squares relaxations
- Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
- Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization
- Hypercontractivity, sum-of-squares proofs, and their applications
- ConnectingN-representability to Weyl's problem: the one-particle density matrix forN= 3 andR= 6
- Quantum de finetti theorems under local measurements with applications
- Product-state approximations to quantum ground states
- Computational Complexity
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- On the complexity of \(k\)-SAT