Page 92 - 8th European Congress of Mathematics ∙ 20-26 June 2021 ∙ Portorož, Slovenia ∙ Book of Abstracts
P. 92
PUTATIONAL ASPECTS OF COMMUTATIVE AND NONCOMMUTATIVE
POSITIVE POLYNOMIALS (MS-77)
Semidefinite relaxations in non-convex spaces
Alejandro Pozas-Kerstjens, physics@alexpozas.com
Mathematical Analysis and Applied Mathematics Department,
Universidad Complutense de Madrid, Spain
In analogy with Lassere’s and Parillo’s hierarchies of semidefinite relaxations for polynomial
optimization problems, a semidefinite hierarchy exisits for non-commutative polynomial opti-
mization problems of the form
p∗ = min φ, p(X)φ
(H,φ,X ) ,
s.t.
qi(X) 0
where φ is a normalized vector in the Hilbert space H, X = (X1, . . . , Xn) are the non-
commuting variables in the problem, and p(X) and qi(X) are polynomials in the variables
X. This hierarchy, known as the Navascués-Pironio-Acín hierarchy, has encountered important
applications in physics, where it has become a central tool in quantum information theory and
in the certification of quantum phenomena.
Its success has motivated its application, within quantum information theory, in more com-
plex scenarios where the relevant search spaces are not convex, and thus the characterizing
constraints are in conflict with semidefinite formulations. The paradigmatic example is opti-
mizing over probability distributions obtained by parties performing measurements on quantum
systems where not all parties receive a share from every system available. The most illustrat-
ing consequence is that, in certain situations, marginalization over a selected number of parties
makes the resulting probability distribution to factorize.
In this talk we address the problem of non-commutative polynomial optimization in non-
convex search spaces and present two means of providing monotonically increasing lower
bounds on its solution, that retain the characteristic that the newly formulated problems re-
main being semidefinite programs. The first directly addresses factorization-type constraints
by adding auxiliary commuting variables that allow to encode (relaxations of) polynomial trace
constraints, while the second considers multiple copies of the problem variables and constrains
them by requiring the satisfaction of invariance under suitable permutations. In addition to pre-
senting the methods and exemplifying their applicability in simple situations, we highlight the
fundamental questions that remain open, mostly regarding to their convergence.
Quantum polynomial optimisation problems for dimension d variables,
with symmetries
Marc Olivier Renou, marc-olivier.renou@icfo.eu
ICFO - The Institute of Photonic Sciences, France
Quantum Information Theory (QIT) involves quantum states and measurements, mathemati-
cally represented as non-commutative positive operators. A typical problem in QIT is to find
the minimum of a polynomial expression in these operators. For instance, finding the maximum
violation of a Bell inequality, or the ground state energy of a Hamiltonian are polynomial opti-
misation problems in non-commuting variables. The NPA hierarchy [New J. Phys. 10, 073013
(2008)], which can be viewed as the “eigenvalue” version of Lasserre’s hierarchy, provides a
90
POSITIVE POLYNOMIALS (MS-77)
Semidefinite relaxations in non-convex spaces
Alejandro Pozas-Kerstjens, physics@alexpozas.com
Mathematical Analysis and Applied Mathematics Department,
Universidad Complutense de Madrid, Spain
In analogy with Lassere’s and Parillo’s hierarchies of semidefinite relaxations for polynomial
optimization problems, a semidefinite hierarchy exisits for non-commutative polynomial opti-
mization problems of the form
p∗ = min φ, p(X)φ
(H,φ,X ) ,
s.t.
qi(X) 0
where φ is a normalized vector in the Hilbert space H, X = (X1, . . . , Xn) are the non-
commuting variables in the problem, and p(X) and qi(X) are polynomials in the variables
X. This hierarchy, known as the Navascués-Pironio-Acín hierarchy, has encountered important
applications in physics, where it has become a central tool in quantum information theory and
in the certification of quantum phenomena.
Its success has motivated its application, within quantum information theory, in more com-
plex scenarios where the relevant search spaces are not convex, and thus the characterizing
constraints are in conflict with semidefinite formulations. The paradigmatic example is opti-
mizing over probability distributions obtained by parties performing measurements on quantum
systems where not all parties receive a share from every system available. The most illustrat-
ing consequence is that, in certain situations, marginalization over a selected number of parties
makes the resulting probability distribution to factorize.
In this talk we address the problem of non-commutative polynomial optimization in non-
convex search spaces and present two means of providing monotonically increasing lower
bounds on its solution, that retain the characteristic that the newly formulated problems re-
main being semidefinite programs. The first directly addresses factorization-type constraints
by adding auxiliary commuting variables that allow to encode (relaxations of) polynomial trace
constraints, while the second considers multiple copies of the problem variables and constrains
them by requiring the satisfaction of invariance under suitable permutations. In addition to pre-
senting the methods and exemplifying their applicability in simple situations, we highlight the
fundamental questions that remain open, mostly regarding to their convergence.
Quantum polynomial optimisation problems for dimension d variables,
with symmetries
Marc Olivier Renou, marc-olivier.renou@icfo.eu
ICFO - The Institute of Photonic Sciences, France
Quantum Information Theory (QIT) involves quantum states and measurements, mathemati-
cally represented as non-commutative positive operators. A typical problem in QIT is to find
the minimum of a polynomial expression in these operators. For instance, finding the maximum
violation of a Bell inequality, or the ground state energy of a Hamiltonian are polynomial opti-
misation problems in non-commuting variables. The NPA hierarchy [New J. Phys. 10, 073013
(2008)], which can be viewed as the “eigenvalue” version of Lasserre’s hierarchy, provides a
90
