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.
|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||Cornell University Library|
|Series||arXiv.org e-Print archive|
Laurent, M, & Piovesan, T. (2013). Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone. arXiv.org e-Print archive. Cornell University Library .