On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings

S. Burgdorf; Monique Laurent; Teresa Piovesan

doi:10.4230/LIPIcs.TQC.2015.127

On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings

S. Burgdorf, Monique Laurent, Teresa Piovesan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

4 Citations (Scopus)

Abstract

We investigate structural properties of the completely positive semidefinite cone CS^n_+, consisting of all the n x n symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size. This cone has been introduced to model quantum graph parameters as conic optimization problems. Recently it has also been used to characterize the set Q of bipartite quantum correlations, as projection of an affine section of it. We have two main results concerning the structure of the completely positive semidefinite cone, namely about its interior and about its closure. On the one hand we construct a hierarchy of polyhedral cones which covers the interior of CS^n_+, which we use for computing some variants of the quantum chromatic number by way of a linear program. On the other hand we give an explicit description of the closure of the completely positive semidefinite cone, by showing that it consists of all matrices admitting a Gram representation in the tracial ultraproduct of matrix algebras.

Original language	English
Title of host publication	Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)
Editors	S. Beigi, R. Koenig
Place of Publication	Leibniz
Publisher	Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Pages	127-146
Volume	44
ISBN (Print)	9783939897965
DOIs	https://doi.org/10.4230/LIPIcs.TQC.2015.127
Publication status	Published - Nov 2015
Event	10th Conference on the Theory of Quantum Computation, Communication and Cryptography - Brussels, Belgium Duration: 20 May 2015 → 22 May 2015

Publication series

Name	Leibniz International Proceedings in Informatics
Volume	44

Conference

Conference	10th Conference on the Theory of Quantum Computation, Communication and Cryptography
Country	Belgium
City	Brussels
Period	20/05/15 → 22/05/15

Keywords

quantum graph parameters
trace nonnegative polynomials
copositive cone
chromatic number
quantum entanglement
nonlocal games
Von Neumann algebra

Access to Document

10.4230/LIPIcs.TQC.2015.127

Fingerprint Dive into the research topics of 'On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings'. Together they form a unique fingerprint.

Cite this

Burgdorf, S., Laurent, M., & Piovesan, T. (2015). On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. In S. Beigi, & R. Koenig (Eds.), Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015) (Vol. 44, pp. 127-146). (Leibniz International Proceedings in Informatics; Vol. 44). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.TQC.2015.127

Burgdorf, S. ; Laurent, Monique ; Piovesan, Teresa. / On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). editor / S. Beigi ; R. Koenig. Vol. 44 Leibniz : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. pp. 127-146 (Leibniz International Proceedings in Informatics).

@inproceedings{7096e1f5c8f74fd1be71ed217b526870,

title = "On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings",

abstract = "We investigate structural properties of the completely positive semidefinite cone CS^n_+, consisting of all the n x n symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size. This cone has been introduced to model quantum graph parameters as conic optimization problems. Recently it has also been used to characterize the set Q of bipartite quantum correlations, as projection of an affine section of it. We have two main results concerning the structure of the completely positive semidefinite cone, namely about its interior and about its closure. On the one hand we construct a hierarchy of polyhedral cones which covers the interior of CS^n_+, which we use for computing some variants of the quantum chromatic number by way of a linear program. On the other hand we give an explicit description of the closure of the completely positive semidefinite cone, by showing that it consists of all matrices admitting a Gram representation in the tracial ultraproduct of matrix algebras.",

keywords = "quantum graph parameters, trace nonnegative polynomials, copositive cone, chromatic number, quantum entanglement, nonlocal games, Von Neumann algebra",

author = "S. Burgdorf and Monique Laurent and Teresa Piovesan",

year = "2015",

month = nov,

doi = "10.4230/LIPIcs.TQC.2015.127",

language = "English",

isbn = "9783939897965",

volume = "44",

series = "Leibniz International Proceedings in Informatics",

publisher = "Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik",

pages = "127--146",

editor = "S. Beigi and R. Koenig",

booktitle = "Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)",

note = "10th Conference on the Theory of Quantum Computation, Communication and Cryptography ; Conference date: 20-05-2015 Through 22-05-2015",

}

Burgdorf, S, Laurent, M & Piovesan, T 2015, On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. in S Beigi & R Koenig (eds), Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). vol. 44, Leibniz International Proceedings in Informatics, vol. 44, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Leibniz, pp. 127-146, 10th Conference on the Theory of Quantum Computation, Communication and Cryptography, Brussels, Belgium, 20/05/15. https://doi.org/10.4230/LIPIcs.TQC.2015.127

On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. / Burgdorf, S.; Laurent, Monique; Piovesan, Teresa.

Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). ed. / S. Beigi; R. Koenig. Vol. 44 Leibniz : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. p. 127-146 (Leibniz International Proceedings in Informatics; Vol. 44).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-review

TY - GEN

T1 - On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings

AU - Burgdorf, S.

AU - Laurent, Monique

AU - Piovesan, Teresa

PY - 2015/11

Y1 - 2015/11

N2 - We investigate structural properties of the completely positive semidefinite cone CS^n_+, consisting of all the n x n symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size. This cone has been introduced to model quantum graph parameters as conic optimization problems. Recently it has also been used to characterize the set Q of bipartite quantum correlations, as projection of an affine section of it. We have two main results concerning the structure of the completely positive semidefinite cone, namely about its interior and about its closure. On the one hand we construct a hierarchy of polyhedral cones which covers the interior of CS^n_+, which we use for computing some variants of the quantum chromatic number by way of a linear program. On the other hand we give an explicit description of the closure of the completely positive semidefinite cone, by showing that it consists of all matrices admitting a Gram representation in the tracial ultraproduct of matrix algebras.

AB - We investigate structural properties of the completely positive semidefinite cone CS^n_+, consisting of all the n x n symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size. This cone has been introduced to model quantum graph parameters as conic optimization problems. Recently it has also been used to characterize the set Q of bipartite quantum correlations, as projection of an affine section of it. We have two main results concerning the structure of the completely positive semidefinite cone, namely about its interior and about its closure. On the one hand we construct a hierarchy of polyhedral cones which covers the interior of CS^n_+, which we use for computing some variants of the quantum chromatic number by way of a linear program. On the other hand we give an explicit description of the closure of the completely positive semidefinite cone, by showing that it consists of all matrices admitting a Gram representation in the tracial ultraproduct of matrix algebras.

KW - quantum graph parameters

KW - trace nonnegative polynomials

KW - copositive cone

KW - chromatic number

KW - quantum entanglement

KW - nonlocal games

KW - Von Neumann algebra

U2 - 10.4230/LIPIcs.TQC.2015.127

DO - 10.4230/LIPIcs.TQC.2015.127

M3 - Conference contribution

SN - 9783939897965

VL - 44

T3 - Leibniz International Proceedings in Informatics

SP - 127

EP - 146

BT - Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015)

A2 - Beigi, S.

A2 - Koenig, R.

PB - Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik

CY - Leibniz

T2 - 10th Conference on the Theory of Quantum Computation, Communication and Cryptography

Y2 - 20 May 2015 through 22 May 2015

ER -

Burgdorf S, Laurent M, Piovesan T. On the closure of the completely positive semidefinite cone and linear approximations to quantum colorings. In Beigi S, Koenig R, editors, Proceedings of the 10th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2015). Vol. 44. Leibniz: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. 2015. p. 127-146. (Leibniz International Proceedings in Informatics). https://doi.org/10.4230/LIPIcs.TQC.2015.127