Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone

We investigate the completely positive semidefinite matrix cone CSn+, consisting of all n×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 chro- matic graph parameters α(G) and χ(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 CSn+ 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 CSn+, 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.