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

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

Mahmut Levent Doğan, Keiya Sakabe, Michael Walter

cs.CCmath-phmath.OCquant-phSubmitted Sep 6, 2026• Announced Sep 8, 2026• 0 citations
arXivHTMLPDF

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.

Comments
81 pages

Related papers

Efficient Algorithms for Tensor Scaling, Quantum Marginals, and Moment Polytopes

Peter Bürgisser, Cole Franks, Ankit Garg +3 more

We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensor-train decompositions, widely used in computational physics and numerical mathematics. Beyond these applications, the algorithm enriches the arsenal of "numerical" methods for classical problems in invariant theory that are significantly faster than "symbolic" methods which explicitly compute invariants or covariants of the relevant action. We stress that (like almost all past algorithms) our convergence rate is polynomial in the approximation parameter; it is an intriguing question to achieve exponential convergence rate, beating symbolic algorithms exponentially, and providing strong membership and separation oracles for the problems above. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomial-time convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.

arXiv:1804.04739•Annual Symposium on Foundations of Computer Science•Oct 1, 2018•35 citations

Minimizing Quantum Renyi Divergences via Mirror Descent with Polyak Step Size

Jun-Kai You, Hao–Chung Cheng, Yen-Huan Li

Quantum information quantities play a substantial role in characterizing operational quantities in various quantum information-theoretic problems. We consider numerical computation of four quantum information quantities: Petz-Augustin information, sandwiched Augustin information, conditional sandwiched Renyi entropy and sandwiched Renyi information. To compute these quantities requires minimizing some order-$α$ quantum Renyi divergences over the set of quantum states. Whereas the optimization problems are obviously convex, they violate standard bounded gradient/Hessian conditions in literature, so existing convex optimization methods and their convergence guarantees do not directly apply. In this paper, we propose a new class of convex optimization methods called mirror descent with the Polyak step size. We prove their convergence under a weak condition, showing that they provably converge for minimizing quantum Renyi divergences. Numerical experiment results show that entropic mirror descent with the Polyak step size converges fast in minimizing quantum Renyi divergences.

arXiv:2109.06054•Sep 13, 2021•1 citation

Strassen's support functionals coincide with the quantum functionals

Keiya Sakabe, Mahmut Levent Doğan, Michael Walter

Strassen's asymptotic spectrum offers a framework for analyzing the complexity of tensors. It has found applications in diverse areas, from computer science to additive combinatorics and quantum information. A long-standing open problem, dating back to 1991, asks whether Strassen's support functionals are universal spectral points, that is, points in the asymptotic spectrum of tensors. In this paper, we answer this question in the affirmative for tensors over complex numbers by proving that the support functionals coincide with the quantum functionals - universal spectral points that are defined via entropy optimization on entanglement polytopes. We obtain this result as a special case of a general minimax formula for convex optimization on entanglement polytopes (and more general moment polytopes). Our formula can be interpreted as a very general "classical-quantum correspondence" analogous to the well-known relation between the Shannon entropy and the von Neumann entropy. Its proof is based on a recent Fenchel-type duality theorem on Hadamard manifolds due to Hirai. In addition to settling Strassen's question, our results yield a unified and simpler approach to several other tensor invariants, including the asymptotic slice rank, the symmetric quantum functional, the $G$-stable rank, and the non-commutative rank.

cs.CCCross-listedarXiv:2601.21553•Jan 30, 2026•0 citations

Fast Convex Optimization with Quantum Gradient Methods

Brandon Augustino, Dylan Herman, Enrico Fontana +4 more

We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. Interestingly, only using noisy function evaluation oracles, we match the first-order query complexities of classical gradient descent, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent and its variants, including dual averaging and mirror prox. By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games. We identify a parameter regime in which our zero-sum games algorithm is faster than any existing classical or quantum approach.

arXiv:2503.17356•Mar 21, 2025•0 citations

Minimizing Quantum Rényi Divergences via Mirror Descent with Polyak Step Size

Jun-Kai You, Hao–Chung Cheng, Yen-Huan Li

Quantum information quantities play a substantial role in characterizing operational quantities in various quantum information-theoretic problems. We consider the numerical computation of four quantum information quantities: Petz-Augustin information, sandwiched Augustin information, conditional sandwiched Rényi entropy, and sandwiched Rényi information. To compute these quantities requires minimizing some order-α quantum Rényi divergences over the set of quantum states. Whereas the optimization problems are obviously convex, they violate standard bounded gradient/Hessian conditions in the literature, so existing convex optimization methods and their convergence guarantees do not directly apply. In this paper, we propose a new class of convex optimization methods called mirror descent with the Polyak step size. We prove their convergence under a weak condition, showing that they provably converge for minimizing quantum Rényi divergences. Numerical experiment results show that entropic mirror descent with the Polyak step size converges fast in minimizing quantum Rényi divergences.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•15 citations

Convex semidefinite tensor optimization and quantum entanglement

Liding Xu, Ye-Chao Liu, Sebastian Pokutta

The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods.

math.OCCross-listedarXiv:2511.05258•Nov 10, 2025•0 citations
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.
We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensor-train decompositions, widely used in computational physics and numerical mathematics. Beyond these applications, the algorithm enriches the arsenal of "numerical" methods for classical problems in invariant theory that are significantly faster than "symbolic" methods which explicitly compute invariants or covariants of the relevant action. We stress that (like almost all past algorithms) our convergence rate is polynomial in the approximation parameter; it is an intriguing question to achieve exponential convergence rate, beating symbolic algorithms exponentially, and providing strong membership and separation oracles for the problems above. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomial-time convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.
Quantum information quantities play a substantial role in characterizing operational quantities in various quantum information-theoretic problems. We consider numerical computation of four quantum information quantities: Petz-Augustin information, sandwiched Augustin information, conditional sandwiched Renyi entropy and sandwiched Renyi information. To compute these quantities requires minimizing some order-ααα quantum Renyi divergences over the set of quantum states. Whereas the optimization problems are obviously convex, they violate standard bounded gradient/Hessian conditions in literature, so existing convex optimization methods and their convergence guarantees do not directly apply. In this paper, we propose a new class of convex optimization methods called mirror descent with the Polyak step size. We prove their convergence under a weak condition, showing that they provably converge for minimizing quantum Renyi divergences. Numerical experiment results show that entropic mirror descent with the Polyak step size converges fast in minimizing quantum Renyi divergences.
Strassen's asymptotic spectrum offers a framework for analyzing the complexity of tensors. It has found applications in diverse areas, from computer science to additive combinatorics and quantum information. A long-standing open problem, dating back to 1991, asks whether Strassen's support functionals are universal spectral points, that is, points in the asymptotic spectrum of tensors. In this paper, we answer this question in the affirmative for tensors over complex numbers by proving that the support functionals coincide with the quantum functionals - universal spectral points that are defined via entropy optimization on entanglement polytopes. We obtain this result as a special case of a general minimax formula for convex optimization on entanglement polytopes (and more general moment polytopes). Our formula can be interpreted as a very general "classical-quantum correspondence" analogous to the well-known relation between the Shannon entropy and the von Neumann entropy. Its proof is based on a recent Fenchel-type duality theorem on Hadamard manifolds due to Hirai. In addition to settling Strassen's question, our results yield a unified and simpler approach to several other tensor invariants, including the asymptotic slice rank, the symmetric quantum functional, the GGG-stable rank, and the non-commutative rank.
We study quantum algorithms based on quantum (sub)gradient estimation using noisy function evaluation oracles, and demonstrate the first dimension-independent query complexities (up to poly-logarithmic factors) for zeroth-order convex optimization in both smooth and nonsmooth settings. Interestingly, only using noisy function evaluation oracles, we match the first-order query complexities of classical gradient descent, thereby exhibiting exponential separation between quantum and classical zeroth-order optimization. We then generalize these algorithms to work in non-Euclidean settings by using quantum (sub)gradient estimation to instantiate mirror descent and its variants, including dual averaging and mirror prox. By leveraging a connection between semidefinite programming and eigenvalue optimization, we use our quantum mirror descent method to give a new quantum algorithm for solving semidefinite programs, linear programs, and zero-sum games. We identify a parameter regime in which our zero-sum games algorithm is faster than any existing classical or quantum approach.
Quantum information quantities play a substantial role in characterizing operational quantities in various quantum information-theoretic problems. We consider the numerical computation of four quantum information quantities: Petz-Augustin information, sandwiched Augustin information, conditional sandwiched Rényi entropy, and sandwiched Rényi information. To compute these quantities requires minimizing some order-α quantum Rényi divergences over the set of quantum states. Whereas the optimization problems are obviously convex, they violate standard bounded gradient/Hessian conditions in the literature, so existing convex optimization methods and their convergence guarantees do not directly apply. In this paper, we propose a new class of convex optimization methods called mirror descent with the Polyak step size. We prove their convergence under a weak condition, showing that they provably converge for minimizing quantum Rényi divergences. Numerical experiment results show that entropic mirror descent with the Polyak step size converges fast in minimizing quantum Rényi divergences.
The cone of positive-semidefinite (PSD) matrices is fundamental in convex optimization, and we extend this notion to tensors, defining PSD tensors, which correspond to separable quantum states. We study the convex optimization problem over the PSD tensor cone. While this convex cone admits a smooth reparameterization through tensor factorizations (analogous to the matrix case), it is not self-dual. Moreover, there are currently no efficient algorithms for projecting onto or testing membership in this cone, and the semidefinite tensor optimization problem, although convex, is NP-hard. To address these challenges, we develop methods for computing lower and upper bounds on the optimal value of the problem. We propose a general-purpose iterative refinement algorithm that combines a lifted alternating direction method of multipliers with a cutting-plane approach. This algorithm exploits PSD tensor factorizations to produce heuristic solutions and refine the solutions using cutting planes. Since the method requires a linear minimization oracle over PSD tensors, we design a spatial branch-and-bound algorithm based on convex relaxations and valid inequalities. Our framework allows us to study the white-noise mixing threshold, which characterizes the entanglement properties of quantum states. Numerical experiments on benchmark instances demonstrate the effectiveness of the proposed methods.