Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
SIAM Journal on Optimization , Volume 25 - Issue 4 p. 2461- 2493
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)|
|Journal||SIAM Journal on Optimization|
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