Moment Optimization in the Navascu'es-Pironio-Ac'in Hierarchy

The Navascués–Pironio–Acín (NPA) hierarchy provides a convergent sequence of semidefinite programming (SDP) relaxations for bounding the solution to noncommutative polynomial optimisation problems, ubiquitous in quantum physics.

The gist The Navascués–Pironio–Acín (NPA) hierarchy provides a convergent sequence of semidefinite programming (SDP) relaxations for bounding the solution to noncommutative polynomial optimisation problems, ubiquitous in quantum physics

The Problem and Framework

The Navascués–Pironio–Acín (NPA) hierarchy addresses problems like optimizing the expectation value of a noncommutative polynomial over quantum states and operators by constructing a sequence of SDP relaxations parameterized by operator moments These relaxations form progressively tighter outer approximations to the set of feasible points in the optimization problem, with convergence to the exact quantum value guaranteed in the limit The computational bottleneck arises because the number of required moments scales combinatorially with the hierarchy level, making higher-level relaxations computationally prohibitive The work reframes moment selection as a combinatorial subset selection problem given a computational budget, seeking the choice of moments to achieve the tightest possible bound

Synergy and Landscape Structure

The problem is characterized by strong higher-order synergistic interactions among moments, which are quantified through a marginal synergy diagnostic adapted from the study of complex systems The marginal synergy is defined as ∆(Sk):= 1/k X k i=1 fγ(Sk-i) − fγ(Sk), which measures how much the relaxation bound degrades on average when any single moment is removed from the best known k-subset This diagnostic distinguishes between regimes where moments operate collectively and those where they contribute independently The landscape is highly heterogeneous, with the typical value across random subsets far from the best achievable value, indicating that greedy strategies fail because the optimal subset cannot be built by extending the optimal subset of size k-1

Optimization Methods

Three complementary optimization methods are developed for moment selection:

1. Parallel Tempering (PT): This method runs multiple replicas at different temperatures and uses exchange moves to cross energy barriers It is particularly well-suited as it combines efficient barrier crossing with parallel execution while preserving the fixed Hamming-weight constraint x ∈ S k N in all local updates

2. Restricted Boltzmann Machine (RBM): This method uses deep policy-based reinforcement learning with an RBM architecture to optimize a parametric policy πθ(x) that concentrates probability on low-loss subsets The RBM is effective because its gradient-based updates allow it to learn and exploit the collective landscape structure in a way that memoryless Metropolis and the random forest surrogate cannot

3. Bayesian Optimization (BO): This method maintains a probabilistic surrogate model of fγ that is cheap to query and uses an acquisition function, such as the Upper Confidence Bound (UCB) criterion, to determine which configuration to evaluate next BO trades accuracy in the transition regime for a factor of twenty fewer SDP evaluations relative to PT, making it preferable when evaluations are the dominant cost

Results and Applications

The methods substantially outperform greedy optimisation approaches at computational costs around two orders of magnitude below brute force The RBM achieves the closest approach to optimal bounds throughout the hard transition regime In two paradigmatic problems, the framework was applied to all 174 bipartite Bell inequalities involving four measurements of two outcomes A second application involved the certification of ground-state properties of the one-dimensional Heisenberg spin chain This budget-aware search over a broader monomial pool improved the certified bound on long-range correlations by nearly two orders of magnitude

Conclusion

The moment-selection framework establishes a general, scalable framework for moment selection in noncommutative polynomial optimization, with applications in many scenarios in quantum physics and quantum information theory The synergy diagnostic provides a useful convergence diagnostic at no additional SDP cost The method that performs best—RBM—is precisely the one whose design facilitates collective exploration, consistent with the synergistic character of the landscape This provides a principled and practical recipe for extending high-quality ground-state certification to system sizes and observables where rigid NPA level truncations are provably suboptimal

--- Page 1 ---

MOMENT OPTIMIZATION IN THE NAVASCUÉS-PIRONIO-ACÍN

HIERARCHY Francesco Flora1,2 Losel Matos1,4 Tim Heightman1 Tamás Kriváchy1,5 Adan Garriga2 Antonio Acín1,3 July 17, 2026

ABSTRACT The Navascués–Pironio–Acín (NPA) hierarchy provides a convergent sequence of semidefinite programming (SDP) relaxations for bounding the solution to noncommutative polynomial optimisation problems, ubiquitous in quantum physics. Its practical applicability is however limited by the computational overhead when increasing the hierarchy level, due to the combinatorial growth in the number of operator moments that must be included at each level Nevertheless, it is known that not all the moments have the same impact on the quality of the bounds obtained through NPA and it is a relevant problem to understand how to select moments to get tighter bounds for a fixed computational effort In this work, we first reframe the problem of choosing moments in NPA relaxations as one of combinatorial subset selection Given a computational budget, we show how to select moments from a candidate pool to achieve the tightest possible bound We show that this selection problem is governed by strong higher-order synergistic interactions among moments, which we quantify through a marginal synergy diagnostic adapted from the study of complex systems We then develop and compare three complementary optimization methods for moment selection: Parallel Tempering (PT), deep policy-based reinforcement learning with a Restricted Boltzmann Machine (RBM) architecture, and Bayesian Optimization (BO) Using the I3322 Bell inequality as a benchmark, we demonstrate that all three methods substantially outperform greedy optimisation approaches at computational costs around two orders of magnitude below brute force, with the RBM achieving the closest approach to optimal bounds throughout the hard transition regime We illustrate the power of our framework in two paradigmatic problems.

1. Bold header: Moment Selection as Combinatorial Subset Optimization

The improved AI system can solve a black-box combinatorial optimization problem by reframing moment selection as a search over binary vectors in the space SN, aiming to find the choice of these k moments that produce the tightest bound.

2. Bold header: Synergy-First Diagnostic for Landscape Navigation

The system can identify collectively important subsets by quantifying strong higher-order synergistic interactions among moments using the marginal synergy diagnostic, which measures how much the relaxation bound degrades on average when any single moment is removed from the best known k-subset.

3. Bold header: Parallel Tempering for Robust Global Search

The AI can navigate high-energy barriers in the synergistic landscape by employing Parallel Tempering (PT), which allows replicas to cross energy barriers at different temperatures, effectively combining efficient barrier crossing with parallel execution.

4. Bold header: Deep Policy-Based Reinforcement Learning for Collective Exploration

The system can learn optimal moment selections through a policy-based RL approach, where the objective is to minimize the expected loss J(θ) using a Restricted Boltzmann Machine (RBM) as the parametric distribution over binary vectors x.

5. Bold header: Bayesian Optimization for Budget-Aware Evaluation

The AI can efficiently locate near-optimal solutions by using Bayesian Optimization with a random forest surrogate, which selects the next configuration based on the Upper Confidence Bound (UCB) criterion to minimize the total number of expensive SDP calls needed.

6. Bold header: Certified Long-Range Correlation Improvement in Many-Body Physics

The system can improve certified bounds on observables by using a budget-aware search over a broader monomial pool, demonstrating that this approach can improve the bound on long-range correlations by nearly two orders of magnitude when moving from a physically motivated local basis to an enlarged candidate pool.