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

Monique Laurent, Teresa Piovesan

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We investigate the completely positive semidefinite cone CSn+, a new matrix cone
consisting of all n×n matrices that admit a Gram representation by positive semidefinite matrices (of any size). In particular, we study relationships between this cone and the completely positive and the doubly nonnegative cone, and between its dual cone and trace positive non-commutative polynomials. We use this new cone to model quantum analogues of the classical independence and chromatic 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 can formulate these quantum parameters as conic linear programs over the cone CSn+. Using this conic approach we can recover the bounds in terms of the theta number and define further approximations by exploiting the link to trace positive polynomials.
Original languageEnglish
Pages (from-to)2461-2493
JournalSIAM Journal on Optimization
Volume25
Issue number4
DOIs
Publication statusPublished - 2015

Fingerprint

Quantum Graphs
Linear Optimization
Positive semidefinite
Parameter Optimization
Cones
Cone
Positive Semidefinite Matrix
Trace
Positive Polynomials
Dual Cone
Polynomials
Linear Program
Non-negative
Scalar
Analogue
Polynomial
Approximation
Graph in graph theory

Keywords

  • quantum graph parameters
  • trace positive polynomials
  • copositive cone
  • chromatic number
  • quantum entanglement
  • nonlocal games

Cite this

@article{10c7401540144889a391e65643740450,
title = "Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone",
abstract = "We investigate the completely positive semidefinite cone CSn+, a new matrix coneconsisting of all n×n matrices that admit a Gram representation by positive semidefinite matrices (of any size). In particular, we study relationships between this cone and the completely positive and the doubly nonnegative cone, and between its dual cone and trace positive non-commutative polynomials. We use this new cone to model quantum analogues of the classical independence and chromatic 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 can formulate these quantum parameters as conic linear programs over the cone CSn+. Using this conic approach we can recover the bounds in terms of the theta number and define further approximations by exploiting the link to trace positive polynomials.",
keywords = "quantum graph parameters, trace positive polynomials, copositive cone, chromatic number, quantum entanglement, nonlocal games",
author = "Monique Laurent and Teresa Piovesan",
year = "2015",
doi = "10.1137/14097865X",
language = "English",
volume = "25",
pages = "2461--2493",
journal = "SIAM Journal on Optimization",
issn = "1052-6234",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "4",

}

Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone. / Laurent, Monique; Piovesan, Teresa.

In: SIAM Journal on Optimization, Vol. 25, No. 4, 2015, p. 2461-2493.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

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

AU - Laurent, Monique

AU - Piovesan, Teresa

PY - 2015

Y1 - 2015

N2 - We investigate the completely positive semidefinite cone CSn+, a new matrix coneconsisting of all n×n matrices that admit a Gram representation by positive semidefinite matrices (of any size). In particular, we study relationships between this cone and the completely positive and the doubly nonnegative cone, and between its dual cone and trace positive non-commutative polynomials. We use this new cone to model quantum analogues of the classical independence and chromatic 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 can formulate these quantum parameters as conic linear programs over the cone CSn+. Using this conic approach we can recover the bounds in terms of the theta number and define further approximations by exploiting the link to trace positive polynomials.

AB - We investigate the completely positive semidefinite cone CSn+, a new matrix coneconsisting of all n×n matrices that admit a Gram representation by positive semidefinite matrices (of any size). In particular, we study relationships between this cone and the completely positive and the doubly nonnegative cone, and between its dual cone and trace positive non-commutative polynomials. We use this new cone to model quantum analogues of the classical independence and chromatic 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 can formulate these quantum parameters as conic linear programs over the cone CSn+. Using this conic approach we can recover the bounds in terms of the theta number and define further approximations by exploiting the link to trace positive polynomials.

KW - quantum graph parameters

KW - trace positive polynomials

KW - copositive cone

KW - chromatic number

KW - quantum entanglement

KW - nonlocal games

U2 - 10.1137/14097865X

DO - 10.1137/14097865X

M3 - Article

VL - 25

SP - 2461

EP - 2493

JO - SIAM Journal on Optimization

JF - SIAM Journal on Optimization

SN - 1052-6234

IS - 4

ER -