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:2408.02572 · Quantum

Non-commutative optimization problems with differential constraints

Mateus Araújo, Andrew J. P. Garner, Miguel Navascués

Published Jul 22, 2026• 0 citations
arXivHTMLPDF

Abstract

Non-commutative polynomial optimization (NPO) problems seek to minimize the state average of a polynomial of some operator variables, subject to polynomial constraints, over all states and operators, as well as the Hilbert spaces where those might be defined. Many of these problems are known to admit a complete hierarchy of semidefinite programming (SDP) relaxations. In this work, we consider a variant of NPO problems where a subset of the operator variables satisfies a system of ordinary differential equations. We prove that, under mild conditions of operator boundedness, for every such problem one can construct a standard NPO problem with the same solution. This allows us to define a complete hierarchy of SDPs to tackle the original differential problem. We apply this method to bound averages of local observables in quantum spin systems subject to a Hamiltonian evolution (i.e., a quench). We find that, even in the thermodynamic limit of infinitely many sites, low levels of the hierarchy provide very good approximations for reasonably long evolution times.

DOI
10.22331/q-2026-07-22-2169

Related papers

Partially-Commutative Polynomial Optimization

Abhishek Mishra, Moisés Bermejo Morán, Stefano Pironio

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.

quant-pharXiv:2607.08841•Jul 13, 2026•0 citations

First-Order Optimality Conditions for Non-Commutative Optimization Problems

Mateus Araújo, Igor Klep, Andrew J. P. Garner +2 more

Abstract We consider the problem of optimizing the state average of a polynomial of non-commuting variables, over all states and operators satisfying a number of polynomial constraints, and over all Hilbert spaces where such states and operators are defined. Such non-commutative polynomial optimization (NPO) problems are routinely solved through hierarchies of semidefinite programming (SDP) relaxations. By formulating the general NPO problem in Lagrangian terms, we heuristically derive first-order optimality conditions via small variations in the problem variables. Although the derivation is not rigorous, it gives rise to two types of optimality conditions—state and operator—which are rigorously analyzed in the paper. Both types of conditions can be enforced through additional positive semidefinite constraints in the SDP hierarchies. State optimality conditions are shown to be satisfied by all NPO problems. For NPO problems with optimal solutions (such as, e.g., Archimedean ones) they allow enforcing a new type of constraints: namely, restricting the optimization over states to the set of common ground states of an arbitrary number of operators. Operator optimality conditions are the non-commutative analogs of the Karush–Kuhn–Tucker (KKT) conditions, which are known to hold in many classical optimization problems. In this regard, we prove that a weak form of operator optimality holds for all NPO problems; stronger versions require the problem constraints to satisfy some qualification criterion, just like in the classical case (e.g.: Mangasarian–Fromovitz constraint qualification). We test the power of the new optimality conditions by computing local properties of ground states of many-body spin systems and the maximum quantum violation of Bell inequalities.

arXiv:2311.18707•Foundations of Computational Mathematics•Jul 7, 2026•2 citations

Quantitative semidefinite certificates for ground-state energies of Pauli Hamiltonians

Igor Klep, Nando Leijenhorst, Victor Magron

The $k$-local Hamiltonian problem is a central model for quantum many-body systems and Hamiltonian complexity. Semidefinite programming and noncommutative sum-of-squares hierarchies provide systematic certificates for ground-state energies, but existing finite-convergence results give no quantitative guarantee on the accuracy of the low hierarchy levels accessible in computation. We prove explicit finite-level convergence rates for these hierarchies in the Pauli setting. For $k$-local Hamiltonians whose Pauli expansion contains only even-weight terms, we show that both the NPA-type lower-bound hierarchy and the upper-bound hierarchy on the spectral minimum have error at most $C(k)ξ^{n,4}_{d+1}/n$, where $ξ^{n,4}_{d+1}$ is the smallest root of a Krawtchouk polynomial and $C(k)$ is independent of the number of qubits $n$ and the hierarchy level $d$. General $k$-local Hamiltonians reduce to this even-weight case by adding one ancilla qubit while preserving the spectrum. The proof constructs almost-reproducing kernels for the Pauli algebra and relates their spectra to Krawtchouk polynomials, giving a noncommutative analogue of recent kernel-based convergence analyses for commutative polynomial optimization. These results provide the first quantitative finite-level accuracy guarantees for noncommutative semidefinite relaxations of Pauli Hamiltonians.

quant-pharXiv:2605.29959•May 29, 2026•0 citations

Certifying Optimality of Bell Inequality Violations: Noncommutative Polynomial Optimization through Semidefinite Programming and Local Optimization

Timotej Hrga, Igor Klep, Janez Povh

Abstract. Bell inequalities are pillars of quantum physics in that their violations imply that certain properties of quantum physics (e.g., entanglement) cannot be represented by any classical picture of physics. In this article Bell inequalities and their violations are considered through the lens of noncommutative polynomial optimization. Optimality of these violations is certified for a large majority of a set of standard Bell inequalities, denoted A2–A89 in the literature. The main techniques used in the paper include the NPA hierarchy, i.e., the noncommutative version of the Lasserre semidefinite programming (SDP) hierarchies based on the Helton–McCullough Positivstellensatz, the Gelfand–Naimark–Segal (GNS) construction with a novel use of the Artin–Wedderburn theory for rounding and projecting, and nonlinear programming (NLP). A new “Newton chip”-like technique for reducing sizes of SDPs arising in the constructed polynomial optimization problems is presented. This technique is based on conditional expectations. Finally, noncommutative Gröbner bases are exploited to certify when an optimizer (a solution yielding optimum violation) cannot be extracted from a dual SDP solution.

SIAM Journal on Optimization•Apr 9, 2024•1 citation

Quantum speed-ups for solving semidefinite relaxations of polynomial optimization

Daniel Stilck França, Ngoc Hoang Anh Mai

We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let $f,g_1,\ldots,g_m$ be real polynomials in $n$ variables and $f^\star$ the infimum of $f$ over the semialgebraic set $S(g)=\{x: g_i(x)\ge 0\}$. Let $λ_k$ be the value of the order-$k$ Lasserre relaxation. Assume either (i) $f^\star=λ_k$ and the optimum is attained in the $\ell_1$-ball of radius $1/2$, or (ii) $S(g)$ lies in the simplex $\{x\ge 0: \sum_j x_j\le 1/2\}$, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates $λ_k$ to accuracy $\varepsilon>0$ with runtime, for fixed $k$, \[ O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), \] where $s_g$ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as $O(n^{3k}\mathrm{poly}(1/\varepsilon))$ even in the unconstrained case. As an example, we obtain an $O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})$ quantum algorithm for portfolio optimization, improving over the classical $O(n^{ω+1}\log(1/\varepsilon))$ bound with $ω\approx2.373$. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.

quant-pharXiv:2511.14389•Nov 19, 2025•0 citations

An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut

Jun Takahashi, Sankara Sai Chaithanya Rayudu, Cunlu Zhou +3 more

Understanding and approximating extremal energy states of local Hamiltonians is a central problem in quantum physics and complexity theory. Recent work has focused on developing approximation algorithms for local Hamiltonians, and in particular the ``Quantum Max Cut'' (QMax-Cut) problem, which is closely related to the antiferromagnetic Heisenberg model. In this work, we introduce a family of semidefinite programming (SDP) relaxations based on the Navascues-Pironio-Acin (NPA) hierarchy which is tailored for QMaxCut by taking into account its SU(2) symmetry. We show that the hierarchy converges to the optimal QMaxCut value at a finite level, which is based on a new characterization of the algebra of SWAP operators. We give several analytic proofs and computational results showing exactness/inexactness of our hierarchy at the lowest level on several important families of graphs. We also discuss relationships between SDP approaches for QMaxCut and frustration-freeness in condensed matter physics and numerically demonstrate that the SDP-solvability practically becomes an efficiently-computable generalization of frustration-freeness. Furthermore, by numerical demonstration we show the potential of SDP algorithms to perform as an approximate method to compute physical quantities and capture physical features of some Heisenberg-type statistical mechanics models even away from the frustration-free regions.

arXiv:2307.15688•Jul 28, 2023•3 citations
Non-commutative polynomial optimization (NPO) problems seek to minimize the state average of a polynomial of some operator variables, subject to polynomial constraints, over all states and operators, as well as the Hilbert spaces where those might be defined. Many of these problems are known to admit a complete hierarchy of semidefinite programming (SDP) relaxations. In this work, we consider a variant of NPO problems where a subset of the operator variables satisfies a system of ordinary differential equations. We prove that, under mild conditions of operator boundedness, for every such problem one can construct a standard NPO problem with the same solution. This allows us to define a complete hierarchy of SDPs to tackle the original differential problem. We apply this method to bound averages of local observables in quantum spin systems subject to a Hamiltonian evolution (i.e., a quench). We find that, even in the thermodynamic limit of infinitely many sites, low levels of the hierarchy provide very good approximations for reasonably long evolution times.
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.
Abstract We consider the problem of optimizing the state average of a polynomial of non-commuting variables, over all states and operators satisfying a number of polynomial constraints, and over all Hilbert spaces where such states and operators are defined. Such non-commutative polynomial optimization (NPO) problems are routinely solved through hierarchies of semidefinite programming (SDP) relaxations. By formulating the general NPO problem in Lagrangian terms, we heuristically derive first-order optimality conditions via small variations in the problem variables. Although the derivation is not rigorous, it gives rise to two types of optimality conditions—state and operator—which are rigorously analyzed in the paper. Both types of conditions can be enforced through additional positive semidefinite constraints in the SDP hierarchies. State optimality conditions are shown to be satisfied by all NPO problems. For NPO problems with optimal solutions (such as, e.g., Archimedean ones) they allow enforcing a new type of constraints: namely, restricting the optimization over states to the set of common ground states of an arbitrary number of operators. Operator optimality conditions are the non-commutative analogs of the Karush–Kuhn–Tucker (KKT) conditions, which are known to hold in many classical optimization problems. In this regard, we prove that a weak form of operator optimality holds for all NPO problems; stronger versions require the problem constraints to satisfy some qualification criterion, just like in the classical case (e.g.: Mangasarian–Fromovitz constraint qualification). We test the power of the new optimality conditions by computing local properties of ground states of many-body spin systems and the maximum quantum violation of Bell inequalities.
The kkk-local Hamiltonian problem is a central model for quantum many-body systems and Hamiltonian complexity. Semidefinite programming and noncommutative sum-of-squares hierarchies provide systematic certificates for ground-state energies, but existing finite-convergence results give no quantitative guarantee on the accuracy of the low hierarchy levels accessible in computation. We prove explicit finite-level convergence rates for these hierarchies in the Pauli setting. For kkk-local Hamiltonians whose Pauli expansion contains only even-weight terms, we show that both the NPA-type lower-bound hierarchy and the upper-bound hierarchy on the spectral minimum have error at most C(k)ξd+1n,4/nC(k)ξ^{n,4}_{d+1}/nC(k)ξd+1n,4​/n, where ξd+1n,4ξ^{n,4}_{d+1}ξd+1n,4​ is the smallest root of a Krawtchouk polynomial and C(k)C(k)C(k) is independent of the number of qubits nnn and the hierarchy level ddd. General kkk-local Hamiltonians reduce to this even-weight case by adding one ancilla qubit while preserving the spectrum. The proof constructs almost-reproducing kernels for the Pauli algebra and relates their spectra to Krawtchouk polynomials, giving a noncommutative analogue of recent kernel-based convergence analyses for commutative polynomial optimization. These results provide the first quantitative finite-level accuracy guarantees for noncommutative semidefinite relaxations of Pauli Hamiltonians.
Abstract. Bell inequalities are pillars of quantum physics in that their violations imply that certain properties of quantum physics (e.g., entanglement) cannot be represented by any classical picture of physics. In this article Bell inequalities and their violations are considered through the lens of noncommutative polynomial optimization. Optimality of these violations is certified for a large majority of a set of standard Bell inequalities, denoted A2–A89 in the literature. The main techniques used in the paper include the NPA hierarchy, i.e., the noncommutative version of the Lasserre semidefinite programming (SDP) hierarchies based on the Helton–McCullough Positivstellensatz, the Gelfand–Naimark–Segal (GNS) construction with a novel use of the Artin–Wedderburn theory for rounding and projecting, and nonlinear programming (NLP). A new “Newton chip”-like technique for reducing sizes of SDPs arising in the constructed polynomial optimization problems is presented. This technique is based on conditional expectations. Finally, noncommutative Gröbner bases are exploited to certify when an optimizer (a solution yielding optimum violation) cannot be extracted from a dual SDP solution.
We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let f,g1,…,gmf,g_1,\ldots,g_mf,g1​,…,gm​ be real polynomials in nnn variables and f⋆f^\starf⋆ the infimum of fff over the semialgebraic set S(g)={x:gi(x)≥0}S(g)=\{x: g_i(x)\ge 0\}S(g)={x:gi​(x)≥0}. Let λkλ_kλk​ be the value of the order-kkk Lasserre relaxation. Assume either (i) f⋆=λkf^\star=λ_kf⋆=λk​ and the optimum is attained in the ℓ1\ell_1ℓ1​-ball of radius 1/21/21/2, or (ii) S(g)S(g)S(g) lies in the simplex {x≥0:∑jxj≤1/2}\{x\ge 0: \sum_j x_j\le 1/2\}{x≥0:∑j​xj​≤1/2}, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates λkλ_kλk​ to accuracy ε>0\varepsilon>0ε>0 with runtime, for fixed kkk, O(nkε−4+nk/2ε−5),O ⁣(sg ⁣[nkε−4+ ⁣(nk+ ⁣∑i=1mnk−di)1/2 ⁣ε−5]), O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), O(nkε−4+nk/2ε−5),O(sg​[nkε−4+(nk+∑i=1m​nk−di​)1/2ε−5]), where sgs_gsg​ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as O(n3kpoly(1/ε))O(n^{3k}\mathrm{poly}(1/\varepsilon))O(n3kpoly(1/ε)) even in the unconstrained case. As an example, we obtain an O(nε−4+nε−5)O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})O(nε−4+n​ε−5) quantum algorithm for portfolio optimization, improving over the classical O(nω+1log⁡(1/ε))O(n^{ω+1}\log(1/\varepsilon))O(nω+1log(1/ε)) bound with ω≈2.373ω\approx2.373ω≈2.373. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.
Understanding and approximating extremal energy states of local Hamiltonians is a central problem in quantum physics and complexity theory. Recent work has focused on developing approximation algorithms for local Hamiltonians, and in particular the ``Quantum Max Cut'' (QMax-Cut) problem, which is closely related to the antiferromagnetic Heisenberg model. In this work, we introduce a family of semidefinite programming (SDP) relaxations based on the Navascues-Pironio-Acin (NPA) hierarchy which is tailored for QMaxCut by taking into account its SU(2) symmetry. We show that the hierarchy converges to the optimal QMaxCut value at a finite level, which is based on a new characterization of the algebra of SWAP operators. We give several analytic proofs and computational results showing exactness/inexactness of our hierarchy at the lowest level on several important families of graphs. We also discuss relationships between SDP approaches for QMaxCut and frustration-freeness in condensed matter physics and numerically demonstrate that the SDP-solvability practically becomes an efficiently-computable generalization of frustration-freeness. Furthermore, by numerical demonstration we show the potential of SDP algorithms to perform as an approximate method to compute physical quantities and capture physical features of some Heisenberg-type statistical mechanics models even away from the frustration-free regions.