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:1808.09598

SymDPoly: symmetry-adapted moment relaxations for noncommutative polynomial optimization

Denis Rosset

Published Aug 29, 2018• 8 citations
arXivHTMLPDF

Abstract

Semidefinite relaxations are widely used to compute upper bounds on the objective of optimization problems involving noncommutative polynomials. Such optimization problems are prevalent in quantum information. We present an algorithm able to discover automatically and exploit the symmetries present in the problem formulation. We also provide an open source software library written in Scala ( https://denisrosset.github.io/symdpoly ) that computes symmetry-adapted semidefinite relaxations with interfaces to a variety of open-source and commercial semidefinite solvers. We discuss the advantages of symmetrization, namely reductions in memory use, computation time, and increase in the solution precision.

DOI
10.48550/arxiv.1808.09598

Related papers

Certified bounds on optimization problems in quantum theory

Younes Naceur, Jie Wang, Victor Magron +1 more

Semidefinite relaxations of polynomial optimization have become a central tool for addressing the non-convex optimization problems over non-commutative operators that are ubiquitous in quantum information theory and, more in general, quantum physics. Yet, as these global relaxation methods are solved numerically, the bounds issued by the semidefinite solver can - and often do - exceed the global optimum, undermining their certifiability. To counter this issue, we introduce a framework for extracting rigorous certified bounds on non-commutative optimization problems from inexact numerical data, and apply it to several paradigmatic problems in quantum information theory. An extension to sparsity and symmetry-adapted semidefinite relaxations is also provided and compared to the general dense scheme. Our results establish rational post-processing as a practical route to reliable certification, pushing semidefinite optimization toward a certifiable standard for quantum information science.

quant-pharXiv:2512.17713•Quantum•Dec 22, 2025•0 citations

Noncommutative polynomial optimization under symmetry

Marie Ioannou, Denis Rosset

We present a general framework to exploit the symmetries present in the Navascu{é}s-Pironio-Ac{í}n semidefinite relaxations that approximate invariant noncommutative polynomial optimization problems. We put equal emphasis on the moment and sum-of-squares dual approaches, and provide a pedagogical and formal introduction to the Navascu{é}s-Pironio-Ac{í}n technique before working out the impact of symmetries present in the problem. Using our formalism, we compute analytical sum-of-square certificates for various Bell inequalities, and prove a long-standing conjecture about the exact maximal quantum violation of the CGLMP inequalities for dimension 3 and 4. We also apply our technique to the Sliwa inequalities in the Bell scenario with three parties with binary measurements settings/outcomes. Symmetry reduction is key to scale the applications of the NPA relaxation, and our formalism encompasses and generalizes the approaches found in the literature.

arXiv:2112.10803•Dec 20, 2021•1 citation

Optimization Techniques in Quantum Information

Benjamin Desef

This thesis focuses on the intersection of mathematical and computational optimization and quantum information. Main contributions are open-source software code: A hybrid approach mixing "traditional" nonconvex and convex methods can make difficult problems more accessible. A demonstration of how to efficiently implement such an algorithm, avoiding interfacial bottlenecks, is provided, finding optimal protocols to establish entanglement through a lossy channel. The central software package developed addresses polynomial optimization problems. Many problems naturally involve only a polynomial objective and constraint polynomials. Such problems can automatically be cast into semidefinite programs that provide a hierarchy of outer approximations. The resulting problems are often so large and scale so unfavorably with respect to the variable number and degree involved that the boundary of the doable is reached quickly. However, technical progress both in hardware and algorithms has pushed this boundary - but software frameworks for polynomial optimization have not followed in the same manner, often now making them the bottleneck that before was the solver. The package PolynomialOptimization.jl developed during this thesis aims to fill the gap and provide a very resource-efficient intermediate layer together with a wide number of algorithms to reduce the problem size, and naturally supporting complex numbers and semidefinite constraints ubiquitous in quantum information problems. Its application on an entanglement distribution problem is demonstrated, showing that even relaxations with semidefinite matrices of three- and four-digit size can be solved conveniently. Finally, a new way to calculate interior-point barriers for the cone of sums-of-squares matrices in a nearly time-optimal way is developed, whose efficient implementation has the potential of further reducing resource consumption.

quant-pharXiv:2512.15831•Dec 18, 2025•1 citation

Enabling Computation of Correlation Bounds for Finite-Dimensional Quantum Systems via Symmetrization

Armin Tavakoli, Denis Rosset, Marc-Olivier Renou

We present a technique for reducing the computational requirements by several orders of magnitude in the evaluation of semidefinite relaxations for bounding the set of quantum correlations arising from finite-dimensional Hilbert spaces. The technique, which we make publicly available through a user-friendly software package, relies on the exploitation of symmetries present in the optimization problem to reduce the number of variables and the block sizes in semidefinite relaxations. It is widely applicable in problems encountered in quantum information theory and enables computations that were previously too demanding. We demonstrate its advantages and general applicability in several physical problems. In particular, we use it to robustly certify the nonprojectiveness of high-dimensional measurements in a black-box scenario based on self-tests of d-dimensional symmetric informationally complete positive-operator-valued measurements.

arXiv:1808.02412•Physical Review Letters•Feb 20, 2019•58 citations

Convergent Relaxations of Polynomial Optimization Problems with Noncommuting Variables

S. Pironio, Miguel Navascués, A. Acín

We consider optimization problems with polynomial inequality constraints in noncommuting variables. These noncommuting variables are viewed as bounded operators on a Hilbert space whose dimension is not fixed and the associated polynomial inequalities as semidefinite positivity constraints. Such problems arise naturally in quantum theory and quantum information science. To solve them, we introduce a hierarchy of semidefinite programming relaxations which generates a monotone sequence of lower bounds that converges to the optimal solution. We also introduce a criterion to detect whether the global optimum is reached at a given relaxation step and show how to extract a global optimizer from the solution of the corresponding semidefinite programming problem.

arXiv:0903.4368•SIAM Journal on Optimization•Jan 1, 2010•194 citations

Partially-Commutative Polynomial Optimization

Abhishek Mishra, Moisés Bermejo Morán, Stefano Pironio

Semidefinite programming hierarchies for commutative and non-commutative polynomial optimization represent a powerful computational tool with many applications in quantum information. In such applications, a given variable is typically not either commuting or non-commuting with all other variables, but instead commutes with some variables and does not commute with others, i.e., the variables satisfy some partial commutation relations. While such partial commutation relations can always be incorporated in a fully non-commutative setting through suitable linear constraints in the semidefinite programming relaxations, exploiting their algebraic properties from the onset can result in more compact relaxations. This leads us to introduce partially-commutative polynomial optimization, a framework that encompasses commutative and non-commutative polynomial optimization, allowing for arbitrary commutation relations among the variables. We point out that the underlying algebraic structure is that of a partially-commutative monoid. We present and review several key aspects of such monoids and show how they can be used to build SDP relaxations for partially-commutative polynomial optimization problems in which the partial commutations are natively implemented in the monomial structure, without the need of additional linear constraints.

quant-pharXiv:2607.08841•Jul 13, 2026•0 citations
Semidefinite relaxations are widely used to compute upper bounds on the objective of optimization problems involving noncommutative polynomials. Such optimization problems are prevalent in quantum information. We present an algorithm able to discover automatically and exploit the symmetries present in the problem formulation. We also provide an open source software library written in Scala ( https://denisrosset.github.io/symdpoly ) that computes symmetry-adapted semidefinite relaxations with interfaces to a variety of open-source and commercial semidefinite solvers. We discuss the advantages of symmetrization, namely reductions in memory use, computation time, and increase in the solution precision.
Semidefinite relaxations of polynomial optimization have become a central tool for addressing the non-convex optimization problems over non-commutative operators that are ubiquitous in quantum information theory and, more in general, quantum physics. Yet, as these global relaxation methods are solved numerically, the bounds issued by the semidefinite solver can - and often do - exceed the global optimum, undermining their certifiability. To counter this issue, we introduce a framework for extracting rigorous certified bounds on non-commutative optimization problems from inexact numerical data, and apply it to several paradigmatic problems in quantum information theory. An extension to sparsity and symmetry-adapted semidefinite relaxations is also provided and compared to the general dense scheme. Our results establish rational post-processing as a practical route to reliable certification, pushing semidefinite optimization toward a certifiable standard for quantum information science.
We present a general framework to exploit the symmetries present in the Navascu{é}s-Pironio-Ac{í}n semidefinite relaxations that approximate invariant noncommutative polynomial optimization problems. We put equal emphasis on the moment and sum-of-squares dual approaches, and provide a pedagogical and formal introduction to the Navascu{é}s-Pironio-Ac{í}n technique before working out the impact of symmetries present in the problem. Using our formalism, we compute analytical sum-of-square certificates for various Bell inequalities, and prove a long-standing conjecture about the exact maximal quantum violation of the CGLMP inequalities for dimension 3 and 4. We also apply our technique to the Sliwa inequalities in the Bell scenario with three parties with binary measurements settings/outcomes. Symmetry reduction is key to scale the applications of the NPA relaxation, and our formalism encompasses and generalizes the approaches found in the literature.
This thesis focuses on the intersection of mathematical and computational optimization and quantum information. Main contributions are open-source software code: A hybrid approach mixing "traditional" nonconvex and convex methods can make difficult problems more accessible. A demonstration of how to efficiently implement such an algorithm, avoiding interfacial bottlenecks, is provided, finding optimal protocols to establish entanglement through a lossy channel. The central software package developed addresses polynomial optimization problems. Many problems naturally involve only a polynomial objective and constraint polynomials. Such problems can automatically be cast into semidefinite programs that provide a hierarchy of outer approximations. The resulting problems are often so large and scale so unfavorably with respect to the variable number and degree involved that the boundary of the doable is reached quickly. However, technical progress both in hardware and algorithms has pushed this boundary - but software frameworks for polynomial optimization have not followed in the same manner, often now making them the bottleneck that before was the solver. The package PolynomialOptimization.jl developed during this thesis aims to fill the gap and provide a very resource-efficient intermediate layer together with a wide number of algorithms to reduce the problem size, and naturally supporting complex numbers and semidefinite constraints ubiquitous in quantum information problems. Its application on an entanglement distribution problem is demonstrated, showing that even relaxations with semidefinite matrices of three- and four-digit size can be solved conveniently. Finally, a new way to calculate interior-point barriers for the cone of sums-of-squares matrices in a nearly time-optimal way is developed, whose efficient implementation has the potential of further reducing resource consumption.
We present a technique for reducing the computational requirements by several orders of magnitude in the evaluation of semidefinite relaxations for bounding the set of quantum correlations arising from finite-dimensional Hilbert spaces. The technique, which we make publicly available through a user-friendly software package, relies on the exploitation of symmetries present in the optimization problem to reduce the number of variables and the block sizes in semidefinite relaxations. It is widely applicable in problems encountered in quantum information theory and enables computations that were previously too demanding. We demonstrate its advantages and general applicability in several physical problems. In particular, we use it to robustly certify the nonprojectiveness of high-dimensional measurements in a black-box scenario based on self-tests of d-dimensional symmetric informationally complete positive-operator-valued measurements.
We consider optimization problems with polynomial inequality constraints in noncommuting variables. These noncommuting variables are viewed as bounded operators on a Hilbert space whose dimension is not fixed and the associated polynomial inequalities as semidefinite positivity constraints. Such problems arise naturally in quantum theory and quantum information science. To solve them, we introduce a hierarchy of semidefinite programming relaxations which generates a monotone sequence of lower bounds that converges to the optimal solution. We also introduce a criterion to detect whether the global optimum is reached at a given relaxation step and show how to extract a global optimizer from the solution of the corresponding semidefinite programming problem.
Semidefinite programming hierarchies for commutative and non-commutative polynomial optimization represent a powerful computational tool with many applications in quantum information. In such applications, a given variable is typically not either commuting or non-commuting with all other variables, but instead commutes with some variables and does not commute with others, i.e., the variables satisfy some partial commutation relations. While such partial commutation relations can always be incorporated in a fully non-commutative setting through suitable linear constraints in the semidefinite programming relaxations, exploiting their algebraic properties from the onset can result in more compact relaxations. This leads us to introduce partially-commutative polynomial optimization, a framework that encompasses commutative and non-commutative polynomial optimization, allowing for arbitrary commutation relations among the variables. We point out that the underlying algebraic structure is that of a partially-commutative monoid. We present and review several key aspects of such monoids and show how they can be used to build SDP relaxations for partially-commutative polynomial optimization problems in which the partial commutations are natively implemented in the monomial structure, without the need of additional linear constraints.