Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1502.02842 · Electronic Journal of Linear Algebra

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

Sabine Burgdorf, Monique Laurent, Teresa Piovesan

Published Feb 6, 2017• 19 citations
arXivHTMLPDF

Abstract

We investigate structural properties of the completely positive semidefinite cone $\mathcal{CS}_+$, consisting of all the $n \times 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 $\mathcal 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 covering the interior of $\mathcal{CS}_+$, 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.

DOI
10.13001/1081-3810.3201

Related papers

Conic Approach to Quantum Graph Parameters Using Linear Optimization Over the Completely Positive Semidefinite Cone

Monique Laurent, Teresa Piovesan

We investigate the completely positive semidefinite cone ${\mathcal{CS}_{+}^n}$, a new matrix cone consisting of all $n\times 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 noncommutative polynomials. 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 can formulate these quantum parameters as conic linear programs over the cone ${\mathcal{CS}_{+}^n}$. 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.

SIAM Journal on Optimization•Jan 1, 2015•47 citations

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

Monique Laurent, Teresa Piovesan

We investigate the completely positive semidefinite cone $\mathcal{CS}_+^n$, a new matrix cone consisting of all $n\times 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 doubly nonnegative cones, 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 $\mathcal{CS}_+^n$. 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.

arXiv:1312.6643•Dec 23, 2013•0 citations

Semidefinite hierarchies for diagonal unitary invariant bipartite quantum states

Britz, Jonas, Monique Laurent

We investigate questions about the cone $\mathrm{SEP}_n$ of separable bipartite states, consisting of the Hermitian matrices acting on $\mathbb{C}^n\otimes\mathbb{C}^n$ that can be written as conic combinations of rank one matrices of the form $xx^*\otimes yy^*$ with $x,y\in\mathbb{C}^n$. Bipartite states that are not separable are said to be entangled. Detecting quantum entanglement is a fundamental task in quantum information and a hard computational problem. We explore the Doherty-Parrilo-Spedalieri (DPS) hierarchy of semidefinite conic approximations for $\mathrm{SEP}_n$ when the bipartite states have some additional structural properties: first, (i) for states with diagonal unitary invariance, and second (ii) for states with Bose symmetry. In case (i) we show that the DPS hierarchy can be block diagonalized, which, combining with its moment reformulation, leads to a substantially more efficient implementation. In case (ii), we give a characterization of the dual hierarchy, in terms of sums of squares of Hermitian complex polynomials, extending a known result in the generic case. It turns out that the completely positive cone $\mathrm{CP}_n$, its dual cone $\mathrm{COP}_n$, and their sums-of-squares based conic approximations $\mathcal{K}^{(t)}_n$, play a central role in these two settings (i),(ii). We clarify these connections and test the block diagonal relaxations on classes of examples.

arXiv:2512.06551•Dec 6, 2025•0 citations

Quantum entanglement: insights via graph parameters and conic optimization

Teresa Piovesan

In this PhD thesis we study the effects of quantum entanglement, one of quantum mechanics most peculiar features, in nonlocal games and communication problems in zero-error information theory. A nonlocal game is a thought experiment in which two cooperating players, who are forbidden to communicate, want to perform a certain task. Zero-error information theory is the mathematical field that studies communication problems where no error is tolerated. The unifying link among the various scenarios we consider is their combinatorial nature and in particular their reformulations as graph theoretical problems, mainly concerning the chromatic and stability numbers and some quantum generalizations thereof. In this thesis we propose a novel approach to the study of these quantum graph parameters using the paradigm of conic optimization. For that, we introduce and study the completely positive semidefinite cone, a new matrix cone consisting of all symmetric matrices that admit a Gram representation by positive semidefinite matrices. Furthermore, we investigate whether entanglement allows for better-than-classical communication schemes in some well-known problems from zero-error information theory. For example we study the channel coding problem, which asks a sender to transmit data reliably to a receiver in the presence of noise, as well as some of its generalizations.

•Oct 27, 2016•2 citations

Correlation matrices, Clifford algebras, and completely positive semidefinite rank

Anupam Prakash, Antonios Varvitsiotis

A symmetric n×n matrix X is completely positive semidefinite (cpsd) if there exist d×d positive semidefinite matrices {Pi}i=1n (for some d∈N) such that Xij=Tr(PiPj), for all i,j∈{1,…,n}. The cpsd−rank of a cpsd matrix is the smallest d∈N for which such a representation is possible. It was shown independently in Prakash A, Sikora J, Varvitsiotis A, et al. [Completely positive semidefinite rank. 2016 Apr. arXiv:1604.07199] and Gribling S, de Laat D, Laurent M. [Matrices with high completely positive semidefinite rank. Linear Algebra Appl. 2017 May;513:122–148] that there exist completely positive semidefinite matrices with sub-exponential cpsd-rank. Both proofs were obtained using fundamental results from the quantum information literature as a black-box. In this work we give a self-contained and succinct proof of the existence of completely positive semidefinite matrices with sub-exponential cpsd-rank. For this, we introduce matrix valued Gram decompositions for correlation matrices and show that for extremal correlations, the matrices in such a factorization generate a Clifford algebra. Lastly, we show that this fact underlies and generalizes Tsirelson's results concerning the structure of quantum representations for extremal quantum correlation matrices.

arXiv:1702.06305•Linear and Multilinear Algebra•Oct 8, 2018•4 citations

Convex semidefinite tensor optimization and quantum entanglement

Liding Xu, Ye-Chao Liu, Sebastian Pokutta

The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods.

math.OCCross-listedarXiv:2511.05258•Nov 10, 2025•0 citations
We investigate structural properties of the completely positive semidefinite cone CS+\mathcal{CS}_+CS+​, consisting of all the n×nn \times nn×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\mathcal QQ 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 covering the interior of CS+\mathcal{CS}_+CS+​, 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.
We investigate the completely positive semidefinite cone CS+n{\mathcal{CS}_{+}^n}CS+n​, a new matrix cone consisting of all n×nn\times nn×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 noncommutative polynomials. We use this new cone to model quantum analogues of the classical independence and chromatic graph parameters α(G)\alpha(G)α(G) and χ(G)\chi(G)χ(G), which are roughly obtained by allowing variables to be positive semidefinite matrices instead of 0/10/10/1 scalars in the programs defining the classical parameters. We can formulate these quantum parameters as conic linear programs over the cone CS+n{\mathcal{CS}_{+}^n}CS+n​. 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.
We investigate the completely positive semidefinite cone CS+n\mathcal{CS}_+^nCS+n​, a new matrix cone consisting of all n×nn\times nn×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 doubly nonnegative cones, 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)α(G)α(G) and χ(G)χ(G)χ(G), which are roughly obtained by allowing variables to be positive semidefinite matrices instead of 0/10/10/1 scalars in the programs defining the classical parameters. We can formulate these quantum parameters as conic linear programs over the cone CS+n\mathcal{CS}_+^nCS+n​. 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.
We investigate questions about the cone SEPn\mathrm{SEP}_nSEPn​ of separable bipartite states, consisting of the Hermitian matrices acting on Cn⊗Cn\mathbb{C}^n\otimes\mathbb{C}^nCn⊗Cn that can be written as conic combinations of rank one matrices of the form xx∗⊗yy∗xx^*\otimes yy^*xx∗⊗yy∗ with x,y∈Cnx,y\in\mathbb{C}^nx,y∈Cn. Bipartite states that are not separable are said to be entangled. Detecting quantum entanglement is a fundamental task in quantum information and a hard computational problem. We explore the Doherty-Parrilo-Spedalieri (DPS) hierarchy of semidefinite conic approximations for SEPn\mathrm{SEP}_nSEPn​ when the bipartite states have some additional structural properties: first, (i) for states with diagonal unitary invariance, and second (ii) for states with Bose symmetry. In case (i) we show that the DPS hierarchy can be block diagonalized, which, combining with its moment reformulation, leads to a substantially more efficient implementation. In case (ii), we give a characterization of the dual hierarchy, in terms of sums of squares of Hermitian complex polynomials, extending a known result in the generic case. It turns out that the completely positive cone CPn\mathrm{CP}_nCPn​, its dual cone COPn\mathrm{COP}_nCOPn​, and their sums-of-squares based conic approximations Kn(t)\mathcal{K}^{(t)}_nKn(t)​, play a central role in these two settings (i),(ii). We clarify these connections and test the block diagonal relaxations on classes of examples.
In this PhD thesis we study the effects of quantum entanglement, one of quantum mechanics most peculiar features, in nonlocal games and communication problems in zero-error information theory. A nonlocal game is a thought experiment in which two cooperating players, who are forbidden to communicate, want to perform a certain task. Zero-error information theory is the mathematical field that studies communication problems where no error is tolerated. The unifying link among the various scenarios we consider is their combinatorial nature and in particular their reformulations as graph theoretical problems, mainly concerning the chromatic and stability numbers and some quantum generalizations thereof. In this thesis we propose a novel approach to the study of these quantum graph parameters using the paradigm of conic optimization. For that, we introduce and study the completely positive semidefinite cone, a new matrix cone consisting of all symmetric matrices that admit a Gram representation by positive semidefinite matrices. Furthermore, we investigate whether entanglement allows for better-than-classical communication schemes in some well-known problems from zero-error information theory. For example we study the channel coding problem, which asks a sender to transmit data reliably to a receiver in the presence of noise, as well as some of its generalizations.
A symmetric n×n matrix X is completely positive semidefinite (cpsd) if there exist d×d positive semidefinite matrices {Pi}i=1n (for some d∈N) such that Xij=Tr(PiPj), for all i,j∈{1,…,n}. The cpsd−rank of a cpsd matrix is the smallest d∈N for which such a representation is possible. It was shown independently in Prakash A, Sikora J, Varvitsiotis A, et al. [Completely positive semidefinite rank. 2016 Apr. arXiv:1604.07199] and Gribling S, de Laat D, Laurent M. [Matrices with high completely positive semidefinite rank. Linear Algebra Appl. 2017 May;513:122–148] that there exist completely positive semidefinite matrices with sub-exponential cpsd-rank. Both proofs were obtained using fundamental results from the quantum information literature as a black-box. In this work we give a self-contained and succinct proof of the existence of completely positive semidefinite matrices with sub-exponential cpsd-rank. For this, we introduce matrix valued Gram decompositions for correlation matrices and show that for extremal correlations, the matrices in such a factorization generate a Clifford algebra. Lastly, we show that this fact underlies and generalizes Tsirelson's results concerning the structure of quantum representations for extremal quantum correlation matrices.
The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods.