Partially-Commutative Polynomial Optimization

• URL: http://arxiv.org/abs/2607.08841v1
• Date: Thu, 09 Jul 2026 18:01:42 GMT
• Title: Partially-Commutative Polynomial Optimization
• Abstract summary: We show how a partially-commutative monoid can be used to build SDP relaxations for partially-commutative optimization problems.<n>We show how they can be used to build SDP relaxations for partially-commutative optimization problems in which the partial commutations are implemented in the monomial structure.
• Score: 1.236218755528715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• (MPO)$^2$: Multivariate Polynomial Optimization based on Matrix Product Operators [6.420068890493834]
  We introduce Multi Polynomial based on Matrix Product Operators (MPO)$2$, a framework that combines learned MPO feature embeddings with compact weight tensors.<n>Across regression and classification benchmarks, (MPO)$2$ improves over existing tensor decomposition based models and provides a flexible alternative for efficient function approximation.
  arXiv  Detail & Related papers  (2026-07-17T12:44:48Z)
• PCPOP.jl: A Julia package for partially commutative polynomial optimization [1.389385993711899]
  PCPOP is a Julia package for optimization that supports non-commutative optimization, t-racial optimization, trace optimization and state optimization.<n>PCPOP implements a specialized framework for computations in partially commutative variables that provides significant computational advantages for problems appearing in algebra information.
  arXiv  Detail & Related papers  (2026-07-10T12:20:16Z)
• Efficient generation and explicit dimensionality of Lie group-equivariant and permutation-invariant bases [1.6789611055085498]
  We propose a practical construction of Lie group-equivariant and permutation-invariant functions of $N$ variables.<n>The construction is generic for any linear Lie group and relies on building a matrix constructed from the Lie algebra.<n>We show that for large values of $N$, the number of rotation-equivariant and permutation-invariant basis functions is of a comparable order.
  arXiv  Detail & Related papers  (2026-04-02T12:33:33Z)
• Variational Entropic Optimal Transport [67.76725267984578]
  We propose Variational Entropic Optimal Transport (VarEOT) for domain translation problems.<n>VarEOT is based on an exact variational reformulation of the log-partition $log mathbbE[exp(cdot)$ as a tractable generalization over an auxiliary positive normalizer.<n> Experiments on synthetic data and unpaired image-to-image translation demonstrate competitive or improved translation quality.
  arXiv  Detail & Related papers  (2026-02-02T15:48:44Z)
• A Galois theorem for machine learning: Functions on symmetric matrices and point clouds via lightweight invariant features [26.619014249559942]
  We present a mathematical formulation for machine learning of functions on symmetric matrices and point clouds.<n>We provide a general construction of generically separating invariant features using ideas inspired by Galois theory.<n>We prove that the number of invariant features can be reduced, generically without losing expressivity, to $O(n)$, where $n$ is the number of points.
  arXiv  Detail & Related papers  (2024-05-13T18:24:03Z)
• Upper bound hierarchies for noncommutative polynomial optimization [1.2249546377051437]
  This work focuses on minimizing the eigenvalue of a noncommutative to a finite number of noncommutative constraints.<n>We derive converging hierarchies of upper bounds due to Lasserre problem for minimizing compact sets.
  arXiv  Detail & Related papers  (2024-02-03T11:53:57Z)
• Learning Polynomial Problems with $SL(2,\mathbb{R})$ Equivariance [6.5783892500847205]
  We show that neural networks can effectively solve problems in a data-driven fashion, achieving tenfold speedups while retaining high accuracy. We observe that these learning problems are equivariant to the non-compact group $SL(2,mathbbR)$, which consists of area-preserving linear transformations.
  arXiv  Detail & Related papers  (2023-12-04T18:59:19Z)
• Convolutional Filtering and Neural Networks with Non Commutative Algebras [153.20329791008095]
  We study the generalization of non commutative convolutional neural networks. We show that non commutative convolutional architectures can be stable to deformations on the space of operators.
  arXiv  Detail & Related papers  (2021-08-23T04:22:58Z)
• Optimization on manifolds: A symplectic approach [127.54402681305629]
  We propose a dissipative extension of Dirac's theory of constrained Hamiltonian systems as a general framework for solving optimization problems. Our class of (accelerated) algorithms are not only simple and efficient but also applicable to a broad range of contexts.
  arXiv  Detail & Related papers  (2021-07-23T13:43:34Z)
• A Reinforcement Learning Environment for Polyhedral Optimizations [68.8204255655161]
  We propose a shape-agnostic formulation for the space of legal transformations in the polyhedral model as a Markov Decision Process (MDP) Instead of using transformations, the formulation is based on an abstract space of possible schedules. Our generic MDP formulation enables using reinforcement learning to learn optimization policies over a wide range of loops.
  arXiv  Detail & Related papers  (2021-04-28T12:41:52Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classes is a new structural framework which permits generalization in reinforcement learning. The framework incorporates nearly all existing models in which a sample complexity is achievable. Our main result provides an RL algorithm which has sample complexity for Bilinear Classes.
  arXiv  Detail & Related papers  (2021-03-19T16:34:20Z)
• Invariant Feature Coding using Tensor Product Representation [75.62232699377877]
  We prove that the group-invariant feature vector contains sufficient discriminative information when learning a linear classifier. A novel feature model that explicitly consider group action is proposed for principal component analysis and k-means clustering.
  arXiv  Detail & Related papers  (2019-06-05T07:15:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.