Optimization Online


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

Monique Laurent (monique***at***cwi.nl)
Teresa Piovesan (piovesan***at***cwi.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 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 $\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
Entry Accepted: 12/23/2013
Entry Last Modified: 12/23/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society