Linear conic formulations for two-party correlations and values of nonlocal games

DOI10.1007/S10107-016-1049-8MaRDI QIDQ517312zbMATH OpenOpenAlexFDO

Authors Jamie Sikora, A. Varvitsiotis

Publication date 23 March 2017

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.07297

zbMATH Keywords

completely positive conecompletely positive semidefinite conelinear conic programmingnonlocal gamesquantum correlationsquantum graph parameterssemidefinite programming relaxations

Mathematics Subject Classification ID

Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Semidefinite programming (90C22) Convex programming (90C25) Applications of mathematical programming (90C90)

Abstract: In this work we study the sets of two-party correlations generated from a Bell scenario involving two spatially separated systems with respect to various physical models. We show that the sets of classical, quantum, no-signaling and unrestricted correlations can be expressed as projections of affine sections of appropriate convex cones. As a by-product, we identify a spectrahedral outer approximation to the set of quantum correlations which is contained in the first level of the Navascu'es, Pironio and Ac'in (NPA) hierarchy and also a sufficient condition for the set of quantum correlations to be closed. Furthermore, by our conic formulations, the value of a nonlocal game over the sets of classical, quantum, no-signaling and unrestricted correlations can be cast as a linear conic program. This allows us to show that a semidefinite programming upper bound to the classical value of a nonlocal game introduced by Feige and Lov'asz is in fact an upper bound to the quantum value of the game and moreover, it is at least as strong as optimizing over the first level of the NPA hierarchy. Lastly, we show that deciding the existence of a perfect quantum (resp. classical) strategy is equivalent to deciding the feasibility of a linear conic program over the cone of completely positive semidefinite matrices (resp. completely positive matrices). By specializing the results to synchronous nonlocal games, we recover the conic formulations for various quantum and classical graph parameters that were recently derived in the literature.

Recommendations

• The set of quantum correlations is not closed
• Synchronicity for quantum non-local games
• On deciding the existence of perfect entangled strategies for nonlocal games
• Linear game non-contextuality and Bell inequalities -- a graph-theoretic approach
• A lower bound on the value of entangled binary games

Cites work

• A parallel repetition theorem for entangled projection games
• Analytical approach to parallel repetition
• Approximation of the stability number of a graph via copositive programming
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• Conic formulations of graph homomorphisms
• Estimating quantum chromatic numbers
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1933860 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 6744339 (Why is no real title available?)
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• New approximations for the cone of copositive matrices and its dual
• On deciding the existence of perfect entangled strategies for nonlocal games
• On the Matrix Equation X′X = A
• On the quantum chromatic number of a graph
• Perfect parallel repetition theorem for quantum XOR proof systems
• Polyhedral duality in Bell scenarios with two binary observables
• Proposed experiment to test local hidden-variable theories
• Quantum analogues of the Bell inequalities. The case of two spatially separated domains
• Quantum bilinear optimization
• Quantum cryptography based on Bell’s theorem
• Quantum homomorphisms
• Synchronous correlation matrices and Connes' embedding conjecture
• The theory of quantum information
• Tsirelson's problem and Kirchberg's conjecture
• Unique games with entangled provers are easy

Cited in

(12)

• Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization
• Completely positive semidefinite rank
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• Quantum bilinear optimization
• Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• The set of quantum correlations is not closed
• Approximate completely positive semidefinite factorizations and their ranks
• A synchronous NPA hierarchy with applications
• Graph isomorphism: physical resources, optimization models, and algebraic characterizations
• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Semidefinite games

This page was built for publication: Linear conic formulations for two-party correlations and values of nonlocal games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517312)