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:1312.6643 · SIAM Journal on Optimization

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

Monique Laurent, Teresa Piovesan

Published Jan 1, 2015• 49 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1137/14097865x

Related papers

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

Sabine Burgdorf, Monique Laurent, Teresa Piovesan

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.

arXiv:1502.02842•Electronic Journal of Linear Algebra•Feb 6, 2017•22 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

Quantum Bilinear Optimization

Mario Berta, Omar Fawzi, Volkher B. Scholz

We study optimization programs given by a bilinear form over noncommutative variables subject to linear inequalities. Problems of this form include the entangled value of two-prover games, entanglement-assisted coding for classical channels, and quantum-proof randomness extractors. We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization. This allows us to give upper bounds on the quantum advantage for all of these problems. Compared to previous work of Pironio, Navascués, and Acín [SIAM J. Optim., 20 (2010), pp. 2157--2180], our hierarchy has additional constraints. By means of examples, we illustrate the importance of these new constraints both in practice and for analytical properties. Moreover, this allows us to give a hierarchy of SDP outer approximations for the completely positive semidefinite cone introduced by Laurent and Piovesan.

arXiv:1506.08810•SIAM Journal on Optimization•Jan 1, 2016•38 citations

Applications of optimization to factorization ranks and quantum information theory

Sander Gribling

Optimization is a fundamental area in mathematics and computer science, with many real-world applications. In this thesis we study the efficiency with which we can solve certain optimization problems from two different perspectives. Firstly, we study it from the perspective of matrix factorization ranks, which comes with connections to quantum information theory. Secondly, we study it from the perspective of quantum computing. This thesis is accordingly divided into two parts, where we take these perspectives. In the first part of this thesis we study several matrix factorization ranks and their connections to quantum information theory. In Chapter 5, we first give a unified approach to lower bounding matrix factorization ranks, using polynomial optimization techniques. In Chapter 6, we exploit the connection between one particular factorization rank, the completely positive semidefinite rank, and quantum correlations to provide an explicit family of matrices with a large completely positive semidefinite factorization rank. In Chapter 8, we use the same connection to study quantum versions of classical graph parameters from the perspective of polynomial optimization (albeit in noncommutative variables). In Chapter 7 we propose and study a new measure for the amount of entanglement needed to realize quantum correlations. We can approximate this new measure using our approach to matrix factorization ranks, i.e., through polynomial optimization in noncommutative variables. In the second part of this thesis we turn our attention to the question: Can we solve optimization problems faster on a quantum computer? First, in Chapter 10, we look at the problem of evaluating a Boolean function. We give a new semidefinite programming characterization of the minimum number of quantum queries to the input that are needed to determine the corresponding function value. In Chapter 11 we revisit the semidefinite programming problem that plays a crucial role in the rest of the thesis; we provide a quantum algorithm for solving semidefinite programs. Finally, in Chapter 12, we study the general problem of solving convex optimization problems in the oracle model. We provide both upper and lower bounds on the efficiency of various reductions in the quantum setting. In particular, we show that quantum computers are more efficient than classical computers for the task of answering separation queries when access to the convex problem is given through membership queries.

Other publications TiSEM•Aug 2, 2019•2 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•5 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•1 citation
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 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.
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.
We study optimization programs given by a bilinear form over noncommutative variables subject to linear inequalities. Problems of this form include the entangled value of two-prover games, entanglement-assisted coding for classical channels, and quantum-proof randomness extractors. We introduce an asymptotically converging hierarchy of efficiently computable semidefinite programming (SDP) relaxations for this quantum optimization. This allows us to give upper bounds on the quantum advantage for all of these problems. Compared to previous work of Pironio, Navascués, and Acín [SIAM J. Optim., 20 (2010), pp. 2157--2180], our hierarchy has additional constraints. By means of examples, we illustrate the importance of these new constraints both in practice and for analytical properties. Moreover, this allows us to give a hierarchy of SDP outer approximations for the completely positive semidefinite cone introduced by Laurent and Piovesan.
Optimization is a fundamental area in mathematics and computer science, with many real-world applications. In this thesis we study the efficiency with which we can solve certain optimization problems from two different perspectives. Firstly, we study it from the perspective of matrix factorization ranks, which comes with connections to quantum information theory. Secondly, we study it from the perspective of quantum computing. This thesis is accordingly divided into two parts, where we take these perspectives. In the first part of this thesis we study several matrix factorization ranks and their connections to quantum information theory. In Chapter 5, we first give a unified approach to lower bounding matrix factorization ranks, using polynomial optimization techniques. In Chapter 6, we exploit the connection between one particular factorization rank, the completely positive semidefinite rank, and quantum correlations to provide an explicit family of matrices with a large completely positive semidefinite factorization rank. In Chapter 8, we use the same connection to study quantum versions of classical graph parameters from the perspective of polynomial optimization (albeit in noncommutative variables). In Chapter 7 we propose and study a new measure for the amount of entanglement needed to realize quantum correlations. We can approximate this new measure using our approach to matrix factorization ranks, i.e., through polynomial optimization in noncommutative variables. In the second part of this thesis we turn our attention to the question: Can we solve optimization problems faster on a quantum computer? First, in Chapter 10, we look at the problem of evaluating a Boolean function. We give a new semidefinite programming characterization of the minimum number of quantum queries to the input that are needed to determine the corresponding function value. In Chapter 11 we revisit the semidefinite programming problem that plays a crucial role in the rest of the thesis; we provide a quantum algorithm for solving semidefinite programs. Finally, in Chapter 12, we study the general problem of solving convex optimization problems in the oracle model. We provide both upper and lower bounds on the efficiency of various reductions in the quantum setting. In particular, we show that quantum computers are more efficient than classical computers for the task of answering separation queries when access to the convex problem is given through membership queries.
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.
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.