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.
Additional Metadata
Keywords Quantum graph parameters, Semidefinite program- ming, Trace positive polynomials, Copositive cone, Chromatic number, Quantum Entanglement, Quantum information, Nonlocal games
THEME Logistics (theme 3), Information (theme 2)
Publisher S.I.A.M.
Persistent URL dx.doi.org/10.1137/14097865X
Journal SIAM Journal on Optimization
Citation
Laurent, M, & Piovesan, T. (2015). Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone. SIAM Journal on Optimization, 25(4), 2461–2493. doi:10.1137/14097865X