⚛️ quantum physics

A hierarchy of eigencomputations for polynomial optimization on the sphere

This paper introduces a convergent hierarchy of lower bounds for polynomial optimization on the sphere that relies on efficient minimum eigenvalue computations rather than full semidefinite programs, thereby enabling the solution of significantly larger problems than existing methods by leveraging a reduction to Hermitian optimization.

Original authors: Benjamin Lovitz, Nathaniel Johnston

Published 2026-09-14

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Benjamin Lovitz, Nathaniel Johnston

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a world where you must find the lowest point in a vast, rugged landscape, but you are only allowed to walk on the surface of a perfect sphere. This is the essence of a fundamental problem in mathematics and engineering: finding the minimum value of a complex polynomial equation when its variables are constrained to lie on a unit sphere. These equations, which can involve dozens of variables raised to high powers, appear everywhere from analyzing the stability of networks to understanding the behavior of quantum particles. For simple cases, like those involving just squares of numbers, the answer is easy to find. But as the equations grow more complicated, the problem becomes incredibly difficult, belonging to a class of challenges that are notoriously hard for computers to solve efficiently. For decades, mathematicians have relied on a powerful but computationally heavy method called the sum-of-squares hierarchy to get closer and closer to the true answer. This method works by solving increasingly large systems of equations, but the sheer size of these systems quickly overwhelms even the most powerful supercomputers, limiting how far researchers can push the solution.

A team of researchers has now developed a new approach that bypasses this computational bottleneck, allowing them to tackle much larger and more complex problems than was previously possible. Instead of solving massive, complex systems of equations, their method reduces the problem to finding the smallest value in a specific list of numbers, known as an eigenvalue. This shift is akin to swapping a heavy, slow-moving freight train for a nimble, high-speed bicycle; while the destination remains the same, the journey becomes vastly more efficient. The researchers proved that their new method, which they call a hierarchy of eigencomputations, reliably converges to the correct answer. They demonstrated that as they increased the level of detail in their calculations, the results consistently improved, eventually reaching the true minimum value of the polynomial.

The secret to this efficiency lies in a clever mathematical trick that transforms the original real-world problem into a slightly different version involving complex numbers. By translating the problem into this complex domain, the researchers could apply a known technique called the Hermitian sum-of-squares hierarchy. This technique is naturally suited to finding the smallest eigenvalue, a task that is far less demanding than the full-scale equation solving required by the older methods. The researchers showed that this translation does not lose any essential information; the minimum value found in the complex version is tightly linked to the minimum value in the original real version. This connection allowed them to build a ladder of approximations that climbs steadily toward the truth, with each rung of the ladder requiring only a single, manageable calculation rather than a massive, time-consuming optimization.

In practice, this new method opens the door to solving problems that were previously out of reach. The researchers tested their approach on several difficult examples, including a famous polynomial known as the Motzkin polynomial, which is known for being non-negative but not easily expressible as a sum of squares. On this and other randomly generated problems, their method produced better estimates in significantly less time than existing alternatives. While the older, more powerful methods could still solve very small problems faster, the new approach excelled as the problems grew larger. For instance, while other methods failed to produce any results for polynomials with more than ten variables due to memory limits, the new method successfully handled polynomials with over ninety variables. This capability is crucial for applications involving large data sets, such as analyzing the structure of massive networks or processing signals in advanced sensing technologies.

The researchers also extended their technique to a broader class of problems involving tensors, which are multi-dimensional arrays of numbers used to represent complex data structures. They showed that their method could be used to compute the spectral norm of a real tensor, a measure of its maximum stretching power, which is a key quantity in fields ranging from machine learning to quantum information theory. By proving that their hierarchy converges to the correct answer at a predictable rate, they provided a reliable tool for scientists and engineers who need to optimize complex systems. The work does not claim to have solved the entire field of polynomial optimization, nor does it suggest that the older methods are obsolete for small-scale problems. Instead, it offers a practical, scalable alternative for the specific class of large-scale problems where current tools fail, providing a clear path forward for tackling some of the most demanding computational challenges in modern science.

Technical Summary: A Hierarchy of Eigencomputations for Polynomial Optimization on the Sphere

Problem Statement

The paper addresses the fundamental problem of minimizing a real homogeneous polynomial (form) $p(x)$ of degree $D$ over the unit sphere in $\mathbb{R}^n$ :
$p_{\min} = \min_{x \in \mathbb{R}^n, \|x\|=1} p(x).$
This problem is NP-hard for degrees $D \geq 3$ and encompasses significant applications in graph theory (e.g., maximum stable sets), computational complexity, and quantum information (e.g., computing $2 \to 4$ norms).

The standard approach to this problem is the Real Sum-of-Squares (RSOS) hierarchy, which provides a sequence of lower bounds converging to $p_{\min}$ . However, each level of the RSOS hierarchy requires solving a full Semidefinite Program (SDP). As the problem size (number of variables $n$ and degree $D$ ) increases, the size of the SDP grows rapidly, rendering the method computationally infeasible for large-scale instances.

Methodology

The authors propose a new hierarchy, termed HRSOS (Hermitian Real Sum-of-Squares), which approximates $p_{\min}$ through a sequence of minimum eigenvalue computations rather than full SDPs. The methodology relies on three core components:

Reduction to Hermitian Optimization: The authors establish a reduction from real optimization on the sphere to Hermitian optimization on the complex sphere. For a real form $p$ , they define a maximally symmetric Gram operator $P = M(p)$ . They prove that the minimum value of the real form, $p_{\min}$ , is bounded by the minimum eigenvalue of the associated Hermitian form, $P_{\min}$ , up to a known constant factor $\delta(d)$ :
$P_{\min} \leq p_{\min} \leq \frac{P_{\min}}{\delta(d)}.$
Crucially, this reduction preserves the property that $p_{\min} > 0$ if and only if $P_{\min} > 0$ .
Utilization of the HSOS Hierarchy: The Hermitian optimization problem is solved using the Hermitian Sum-of-Squares (HSOS) hierarchy. Unlike the RSOS hierarchy, the HSOS hierarchy is a "spectral" hierarchy where the bound at level $k$ is simply the minimum eigenvalue of a specific Hermitian operator constructed from the input form. The convergence of the HSOS hierarchy is known to be $O(1/k)$ .
Construction of the HRSOS Hierarchy: By combining the reduction with the HSOS hierarchy, the authors construct a sequence of generalized eigenvalue problems. At level $k$ , the bound $\eta_k$ is computed as:
$\eta_k = \lambda_{\min}\left( (N^{(d)}_k)^{-1/2} P_k (N^{(d)}_k)^{-1/2} \right),$
where $P_k$ and $N^{(d)}_k$ are operators derived from $p$ and the norm form $\|x\|^{2d}$ , respectively. In practice, this is solved as a generalized eigenvalue problem $P_k \psi = \lambda N^{(d)}_k \psi$ , avoiding the explicit inversion of large matrices.

The authors extend this framework to multi-homogeneous forms (optimization over products of spheres) and tensor spectral norms, creating the m-HRSOS hierarchy.

Key Contributions

Spectral Hierarchy for Real Optimization: The paper introduces the first convergent hierarchy for real polynomial optimization on the sphere that relies solely on eigenvalue computations rather than full SDPs.
Convergence Guarantees: The authors prove that the HRSOS hierarchy converges additively to $p_{\min}$ with a rate of $O(1/k)$ . While this is slower than the best-known $O(1/k^2)$ rate for RSOS when $D \leq 2n$ , it matches the known $O(1/k)$ rate for RSOS when $D > 2n$ .
Tensor Spectral Norm Computation: The methodology is generalized to compute the real spectral norm of tensors and minimize biquadratic forms, providing a spectral alternative to existing tensor decomposition and optimization techniques.
Canonical Construction: Unlike other "cheaper" alternatives (such as the harmonic hierarchy), the proposed method is completely canonical, requiring no arbitrary choices of cubature rules or kernels.

Results and Numerical Performance

The authors implemented the HRSOS hierarchy in MATLAB and compared it against the RSOS, DSOS (Diagonally-Dominant SOS), and harmonic hierarchies.

Scalability: The primary advantage is scalability. While RSOS is limited to small problems (e.g., degree-4 polynomials with $\approx 25$ variables) due to memory constraints of SDP solvers, HRSOS can handle significantly larger instances (e.g., degree-4 polynomials with $>90$ variables) because it utilizes sparse generalized eigenvalue solvers.
Efficiency vs. RSOS: For small problems where RSOS is feasible, RSOS generally provides tighter bounds per unit of computation time. However, for larger problems where RSOS fails, HRSOS is the only viable spectral alternative.
Efficiency vs. Alternatives: Compared to the optimization-free harmonic hierarchy, HRSOS provides better bounds per unit of time. The harmonic hierarchy requires minimizing a polynomial over a cubature rule of size exponential in $n$ , which becomes prohibitively expensive for $n \geq 10$ . HRSOS avoids this discrete optimization bottleneck.
Convergence: In numerical experiments (including the Motzkin polynomial and random quartic forms), HRSOS consistently outperformed the DSOS and harmonic hierarchies in terms of the quality of bounds achieved within a fixed time budget.

Significance and Claims

The paper claims that the HRSOS hierarchy opens a new path for solving large-scale constrained real optimization problems by leveraging techniques from Hermitian optimization and quantum de Finetti theorems.

Practical Impact: The method enables the computation of bounds for polynomial optimization problems that are currently intractable for standard SDP-based methods.
Theoretical Bridge: It establishes a rigorous link between real and Hermitian optimization, suggesting that other Hermitian spectral techniques could be adapted for real problems.
Modesty: The authors acknowledge that while their convergence rate ( $O(1/k)$ ) is not as fast as the best RSOS rates for low degrees, the computational feasibility for high-dimensional problems makes it a superior practical tool in those regimes. They also note that for constrained optimization, the direct equivalence between real and Hermitian minima does not always hold, suggesting that further work is needed to adapt the hierarchy to general constraints without resorting to bisection or full SDPs.

The paper concludes that for large-scale polynomial optimization on the sphere and tensor spectral norm computation, the proposed eigencomputation hierarchy offers a compelling balance between computational tractability and bound quality, outperforming existing non-SDP alternatives.