  


Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
Monique Laurent (moniquecwi.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 noncommutative 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/2013 Modify/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  