Page 93 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 93
COMPUTATIONAL ASPECTS OF COMMUTATIVE AND NONCOMMUTATIVE
POSITIVE POLYNOMIALS (MS-77)
converging hierarchy of SDP relaxation of a non-commutative polynomial optimisation prob-
lem involving variables of unbounded dimension. This hierarchy converges, it is one of QIT
main technical tool.
Importantly, some QIT problems concern operators of bounded dimension d. The NPA
hierarchy was extended into the NV hierarchy [Phys. Rev. Lett.115, 020501(2015)] to tackle
this case. In this method, one first sample at random many dimension d operators satisfying
the constraint, and compute the associated moment matrix. This first step discovers the moment
matrix vector space, over which the relaxed SDP problem is solved in a second step. In this talk,
we will first review this method. Then, based on [Phys. Rev. Lett. 122, 070501], we will show
how one can reduce the computational requirements by several orders of magnitude, exploiting
the eventual symmetries present in the optimization problem.
Hilbert’s 17th problem for noncommutative rational functions
Jurij Volcˇicˇ, volcic@tamu.edu
Texas A&M University, United States
One of the problems on Hilbert’s 1900 list asked whether every positive rational function can
be written as a sum of squares of rational functions. Its affirmative resolution by Artin in 1927
was a breakthrough for real algebraic geometry. This talk addresses the analog of this problem
for noncommutative rational functions. More generally, a rational Positivstellensatz on ma-
tricial sets given by linear matrix inequalities is presented. The crucial intermediate step is an
extension theorem on invertible evaluations of linear matrix pencils. A consequence of the Posi-
tivstellensatz is an algorithm for eigenvalue optimization of noncommutative rational functions.
Lastly, the talk discusses some contrast between polynomial and rational Positivstellensätze.
Efficient noncommutative polynomial optimization by exploiting sparsity
Jie Wang, jwang@laas.fr
LAAS-CNRS, France
Coauthor: Victor Magron
Many problems arising from quantum information can be modelled as noncommutative poly-
nomial optimization problems. The moment-SOHS hierarchy approximates the optimum of
noncommutative polynomial optimization problems by solving a sequence of semidefinite pro-
gramming relaxations with increasing sizes. In this talk, I will show how to exploit various
sparsity patterns encoded in the problem data to improve scalability of the moment-SOHS hier-
archy for eigenvalue and trace optimization problems.
91
POSITIVE POLYNOMIALS (MS-77)
converging hierarchy of SDP relaxation of a non-commutative polynomial optimisation prob-
lem involving variables of unbounded dimension. This hierarchy converges, it is one of QIT
main technical tool.
Importantly, some QIT problems concern operators of bounded dimension d. The NPA
hierarchy was extended into the NV hierarchy [Phys. Rev. Lett.115, 020501(2015)] to tackle
this case. In this method, one first sample at random many dimension d operators satisfying
the constraint, and compute the associated moment matrix. This first step discovers the moment
matrix vector space, over which the relaxed SDP problem is solved in a second step. In this talk,
we will first review this method. Then, based on [Phys. Rev. Lett. 122, 070501], we will show
how one can reduce the computational requirements by several orders of magnitude, exploiting
the eventual symmetries present in the optimization problem.
Hilbert’s 17th problem for noncommutative rational functions
Jurij Volcˇicˇ, volcic@tamu.edu
Texas A&M University, United States
One of the problems on Hilbert’s 1900 list asked whether every positive rational function can
be written as a sum of squares of rational functions. Its affirmative resolution by Artin in 1927
was a breakthrough for real algebraic geometry. This talk addresses the analog of this problem
for noncommutative rational functions. More generally, a rational Positivstellensatz on ma-
tricial sets given by linear matrix inequalities is presented. The crucial intermediate step is an
extension theorem on invertible evaluations of linear matrix pencils. A consequence of the Posi-
tivstellensatz is an algorithm for eigenvalue optimization of noncommutative rational functions.
Lastly, the talk discusses some contrast between polynomial and rational Positivstellensätze.
Efficient noncommutative polynomial optimization by exploiting sparsity
Jie Wang, jwang@laas.fr
LAAS-CNRS, France
Coauthor: Victor Magron
Many problems arising from quantum information can be modelled as noncommutative poly-
nomial optimization problems. The moment-SOHS hierarchy approximates the optimum of
noncommutative polynomial optimization problems by solving a sequence of semidefinite pro-
gramming relaxations with increasing sizes. In this talk, I will show how to exploit various
sparsity patterns encoded in the problem data to improve scalability of the moment-SOHS hier-
archy for eigenvalue and trace optimization problems.
91
