Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parameters

• URL: http://arxiv.org/abs/2609.06633v1
• Date: Sun, 06 Sep 2026 14:30:31 GMT
• Title: Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parameters
• Abstract summary: Convex optimization on polytopes arises in many areas of science.<n>We develop a first-order framework called Hadamard mirror descent to optimize convex functions over moment polytopes.<n>Applying the framework to entanglement polytopes yields the first efficient first-order algorithms.
• Score: 1.3438189447065458
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Convex optimization on polytopes arises in many areas of science. When the polytope is given implicitly or has exponentially many vertices and facets, standard methods may not apply or be ineffective. This is the case for moment polytopes, such as the entanglement polytopes, which play a foundational role in quantum information and algebraic complexity. They give rise to important entanglement measures and tensor parameters such as the quantum functionals, yet general effective methods for computing these quantities have been elusive. In this paper we address this challenge. We develop a first-order framework called Hadamard mirror descent to optimize suitable convex functions over moment polytopes and, more generally, the gradient sets of geodesically convex functions. It operates locally and does not rely on any explicit description of the polytope. Our framework extends mirror descent, an effective and widely used framework for convex optimization, from the Euclidean setting to Hadamard manifolds, and is motivated by a recent work by Hirai, which we interpret as a Hadamard version of mirror flow. Applying the framework to entanglement polytopes yields the first efficient first-order algorithms to compute the quantum functionals, the symmetric quantum functional, and the G-stable ranks, as well as a new direct algorithm for the non-commutative rank.

Related papers

• Sandwiching Polynomials for Geometric Concepts with Low Intrinsic Dimension [23.43080600040766]
  We give a new method for constructing low-degree sandwichings that yield greatly improved degree bounds for several fundamental function classes and marginal distributions.<n>Our proof is relatively simple and directly uses the smoothness of the target function's boundary to construct sandwiching Lipschitz functions.
  arXiv  Detail & Related papers  (2026-02-27T16:59:18Z)
• Strassen's support functionals coincide with the quantum functionals [1.3438189447065458]
  Strassen's spectrum offers a framework for analyzing the complexity of tensors.<n>Long-standing open problem asks whether Strassen's support functionals are universal spectral points.<n>We prove that support functionals coincide with the quantum functionals.
  arXiv  Detail & Related papers  (2026-01-29T11:13:44Z)
• Neural Network Approximation: A View from Polytope Decomposition [36.24385738607139]
  We develop an explicit kernel method to derive an universal approximation of continuous functions.<n>A ReLU network is constructed to approximate the kernel in each subdomain separately.<n>We extend our approach to analytic functions to reach a higher approximation rate.
  arXiv  Detail & Related papers  (2026-01-26T08:39:11Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Flows on convex polytopes [0.0]
  We show that any full-dimensional polytope is homeomorphic to a unit ball, and our approach harnesses flows defined on the ball, mapping them back to the original polytope.<n>Our experiments take inspiration from applications in metabolic flux analysis and demonstrate that our methods achieve competitive density estimation, sampling accuracy, as well as fast training and inference times.
  arXiv  Detail & Related papers  (2025-03-13T10:15:40Z)
• Quantum Algorithm For Testing Convexity of Function [0.0]
  An important property of a real-valued function is its convexity, which plays a very crucial role in many areas, such as thermodynamics and geometry. Motivated by recent advances in quantum computation as well as the quest for quantum advantage, we give a quantum algorithm for testing convexity of functions. We show that quantum computers can reveal the convexity property superpolynomially faster than classical computers with respect to number of variables.
  arXiv  Detail & Related papers  (2024-09-05T07:38:38Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching [41.05165517541873]
  We introduce a novel global optimization method for align partially overlapping point sets.<n>Our method exhibits superior robustness to non-rigid deformations, positional noise and outliers.<n> Experiments on 2D and 3D synthetic and real-world data demonstrate that our method, compared to state-of-the-art approaches, exhibits superior robustness to outliers.
  arXiv  Detail & Related papers  (2024-05-14T13:28:57Z)
• GloptiNets: Scalable Non-Convex Optimization with Certificates [61.50835040805378]
  We present a novel approach to non-cube optimization with certificates, which handles smooth functions on the hypercube or on the torus. By exploiting the regularity of the target function intrinsic in the decay of its spectrum, we allow at the same time to obtain precise certificates and leverage the advanced and powerful neural networks.
  arXiv  Detail & Related papers  (2023-06-26T09:42:59Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Flow Matching on General Geometries [43.252817099263744]
  We propose a simple yet powerful framework for training continuous normalizing flows on manifold geometries. We show that it is simulation-free on simple geometries, does not require divergence, and computes its target vector field in closed-form. Our method achieves state-of-the-art performance on many real-world non-Euclidean datasets.
  arXiv  Detail & Related papers  (2023-02-07T18:21:24Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  This work considers a large family of bandit problems where the unknown underlying reward function is non-concave. Our algorithms are based on a unified zeroth-order optimization paradigm that applies in great generality. We show that the standard optimistic algorithms are sub-optimal by dimension factors.
  arXiv  Detail & Related papers  (2021-07-09T16:04:24Z)
• 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)
• Weighted slice rank and a minimax correspondence to Strassen's spectra [5.348876409230947]
  Strassen's spectra program characterizes optimal matrix algorithms through monotone functionals. Weighted slice rank encapsulates different notions of bipartiteness of quantum entanglement. New characterization can be extended to all fields.
  arXiv  Detail & Related papers  (2020-12-28T18:49:23Z)

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.