Certifying RBMs Cut NPA Hierarchy Optimization Costs by 100×

Researchers at ICFO, The Barcelona Institute of Science and Technology and collaborating institutions have outperformed a key technique used in quantum physics by reframing a complex problem as one of efficient selection. The team tackled the Navascués-Pironio-Acín (NPA) hierarchy, a method for bounding solutions to problems in quantum physics, which suffers from computational overhead as its complexity increases. By reframing the problem of choosing moments within the NPA hierarchy as one of combinatorial subset selection, they developed optimization methods, including one leveraging a Restricted Boltzmann Machine, that achieve costs reduced by nearly two orders of magnitude compared to brute force approaches. The work demonstrates that strong higher-order synergistic interactions among moments govern the effectiveness of NPA relaxations, quantifying these interactions through a marginal synergy diagnostic adapted from the study of complex systems and establishing a scalable framework for quantum optimization.

Navascués-Pironio-Acín Hierarchy for Noncommutative Optimization

The computational demands of the Navascués, Pironio, Acín (NPA) hierarchy, a framework for bounding solutions to quantum physics problems, are increasingly constrained by the number of operator moments required at each level of refinement. Researchers at ICFO, Institut de Ciencies Fotoniques, Eurecat, and affiliated institutions have now reframed the problem of choosing moments in NPA relaxations as one of combinatorial subset selection. Given a computational budget, they show how to select moments from a candidate pool to achieve the tightest possible bound. This reframing allows for the application of optimization techniques beyond those traditionally used in quantum computation. They quantify strong higher-order synergistic interactions among moments through a marginal synergy diagnostic adapted from the study of complex systems, highlighting a connection between fields.

They demonstrate this synergy is critical, as the best pair of moments does not generally contain the best single moment. To address this complexity, the researchers developed and compared three optimization methods: Parallel Tempering, deep reinforcement learning with a Restricted Boltzmann Machine, and Bayesian Optimization. These methods substantially outperform greedy optimisation approaches using the Bell inequality as a benchmark, achieving costs around two orders of magnitude below brute force and suggesting a scalable path toward more efficient quantum optimization.

Researchers confronted a significant hurdle within the Navascués-Pironio-Acín (NPA) hierarchy: its computational demands escalate rapidly with each level, limiting practical application despite its theoretical convergence. Reframing the problem of choosing moments in NPA relaxations as one of combinatorial subset selection revealed that identifying optimal moment sets isn’t about individual contributions, but rather the complex interplay between them. The researchers then developed and compared 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), quantifying these interactions through a marginal synergy diagnostic adapted from the study of complex systems.

Recognizing the combinatorial complexity of selecting impactful moments within the hierarchy, the team sought methods beyond traditional approaches, ultimately reframing the problem as a combinatorial subset selection. The RBM approach, detailed in the study, offered a deep policy-based solution capable of navigating the rugged energy landscapes revealed by their analysis of moment interactions. Using the Bell inequality as a benchmark, they demonstrated 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.

The NPA hierarchy, used to bound solutions in quantum problems, suffers from computational demands as its level increases, hindering practical application. The team focused on Bell inequalities, a standard benchmark with 174 bipartite variations involving measurements of two outcomes, to dissect the complex interplay between moments. A brute-force exploration of a configuration space of approximately two million subsets revealed that not all moments have the same impact on the quality of the bounds obtained through NPA. They discovered “strong higher-order synergistic interactions among moments,” which they quantify through a marginal synergy diagnostic adapted from the study of complex systems.

Beyond Bell inequality certification, the researchers extended their moment selection framework to tackle a significantly more complex problem: certifying ground-state properties of the one-dimensional Heisenberg spin chain. This system presents a substantial computational challenge when attempting to determine its lowest energy state with high precision. The team demonstrated that physically motivated monomial bases, traditionally used to represent the spin chain’s behavior, are internally compressible and are not globally optimal in general. This led to a budget-aware search across a broader pool of monomials, revealing a substantial improvement in the certified bound on long-range correlations, an increase of nearly two orders of magnitude. The ability to refine these bounds is critical for validating results from quantum simulation experiments and for developing more accurate models of material behavior. The study illustrates the power of their framework in scenarios where exhaustive searches are impractical, highlighting its scalability for tackling complex quantum many-body systems. The researchers emphasize that their approach establishes “a general, scalable framework for moment selection in noncommutative polynomial optimization,” with broad applications extending beyond the specific examples explored.