- Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone Monique Laurent (moniquecwi.nl) Teresa Piovesan (piovesancwi.nl) Abstract: We investigate the completely positive semidefinite matrix cone $\mathcal{CS}_+^n$, consisting of all $n\times n$ matrices that admit a Gram representation by positive semidefinite matrices (of any size). We use this new cone to model quantum analogues of the classical independence and chromatic graph parameters $\alpha(G)$ and $\chi(G)$, which are roughly obtained by allowing variables to be positive semidefinite matrices instead of $0/1$ scalars in the programs defining the classical parameters. We study relationships between the cone $\mathcal{CS}_+^n$ and the completely positive and doubly nonnegative cones, and between its dual cone and trace positive non-commutative polynomials. By using the truncated tracial quadratic module as sufficient condition for trace positivity, we can define hierarchies of cones aiming to approximate the dual cone of $\mathcal{CS}_+^n$, which we then use to construct hierarchies of semidefinite programming bounds approximating the quantum graph parameters. Finally we relate their convergence properties to Connes' embedding conjecture in operator theory. Keywords: Quantum graph parameters, Semidefinite programming, Trace positive polynomials, Copositive cone, Chromatic number, Quantum Entanglement, Quantum information, Nonlocal games. Category 1: Linear, Cone and Semidefinite Programming Category 2: Combinatorial Optimization Citation: Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands and Tilburg University. December 2013. Download: [PDF]Entry Submitted: 12/23/2013Entry Accepted: 12/23/2013Entry Last Modified: 12/23/2013Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.