AI Tackles Complex Problems Previously Beyond Reach

Researchers are tackling the computationally intractable problem of finding ground states in p-spin models, disordered systems with complex many-body interactions that pose a significant challenge to both theoretical understanding and practical optimisation. Li Zeng, Mutian Shen from the Department of Physics at Washington University in St. Louis, and Tianle Pu, working with colleagues including Zohar Nussinov from the Rudolf Peierls Centre for Theoretical Physics, University of Oxford, and Qing Feng, Chao Chen, Zhong Liu, and Changjun Fan from the Laboratory for Big Data and Decision, College of Systems Engineering, National University of Defense Technology, present a novel approach to this longstanding issue. Their work introduces PLANCK, a deep reinforcement learning framework inspired by physics, which demonstrates remarkable zero-shot generalisation to significantly larger systems and outperforms existing methods across diverse problem structures. This advance not only expands the scope of tractable high-order disordered systems but also offers a promising new paradigm for machine learning to address previously insurmountable combinatorial optimisation problems.

Can complex problems with many interacting parts always be solved efficiently. A new technique demonstrates a way to find good solutions to these problems much faster than existing methods. By combining insights from physics with artificial intelligence, it tackles challenges previously considered too difficult for computers. Scientists are tackling a longstanding challenge in computational physics: efficiently solving for the lowest energy state of complex disordered systems known as p-spin glasses.

These systems, defined by interactions extending beyond simple pairs of particles (where ‘p’ represents the number of interacting spins and is greater than two), present a computational hurdle because finding their ground state is an NP-hard problem. This means the time required to find a solution increases exponentially with the size of the system, quickly becoming intractable for even moderately sized instances.

Solving this problem has implications not only for understanding the fundamental physics of disordered materials, structural glasses, and exotic quantum phases, but also for a broad range of practical optimisation tasks. Yet, despite decades of research, a general and scalable method for tackling large-scale p-spin models has remained elusive. Now, researchers have developed PLANCK, a novel framework combining deep reinforcement learning with hypergraph neural networks.

Unlike previous approaches, PLANCK directly addresses the complex, many-body interactions inherent in p-spin glasses, rather than simplifying them into pairwise approximations. Trained on relatively small examples, the system demonstrates an unexpected ability to generalise to problems many orders of magnitude larger, consistently exceeding the performance of established thermal annealing techniques across various system configurations.

Once trained, PLANCK not only excels at finding low-energy states in p-spin glasses but also delivers near-optimal solutions for other notoriously difficult combinatorial problems. These include random k-XORSAT, a problem involving Boolean logic, hypergraph max-cut, and the conventional max-cut problem, all of which fall into the category of NP-hard challenges.

This suggests a potential shift in how we approach optimisation, moving towards physics-inspired machine learning algorithms capable of handling problems previously considered beyond reach. At the core of PLANCK is a symmetry-aware design that exploits the underlying mathematical structure of p-spin models. By representing these interactions as hypergraphs, generalisations of graphs that allow for connections between multiple nodes, the framework can efficiently encode and process complex relationships. This approach not only expands the boundaries of tractable disordered systems but also suggests a promising path for developing machine learning solvers capable of addressing previously intractable combinatorial optimisation challenges.

PLANCK achieves superior performance and scalability via hypergraph networks and gauge symmetry

Once trained on small synthetic instances, PLANCK consistently outperforms state-of-the-art thermal annealing methods across all tested structural topologies and coupling distributions. Specifically, the research demonstrates that the system can solve problems orders of magnitude larger than those previously tractable with conventional approaches. PLANCK’s performance is particularly evident when considering its zero-shot generalisation ability; it requires training only on smaller instances to then effectively address substantially larger systems without any further adaptation.

At the core of PLANCK is a specially designed hypergraph neural network, which encodes spin states and many-body couplings into order-independent features. This design allows the framework to seamlessly scale to higher interaction orders, a key advancement over previous methods. Exploitation of gauge symmetry further enhances performance, drastically reducing the search space and accelerating training convergence.

By leveraging this symmetry, PLANCK achieves improved solution quality and efficiency. Beyond p-spin glasses, PLANCK also tackles a broad class of NP-hard combinatorial problems. Without any task-specific customisation, the framework achieves near-optimal solutions for random k-XORSAT, hypergraph max-cut, and conventional max-cut problems. This versatility highlights the potential of PLANCK as a general-purpose optimisation tool.

The reinforcement learning formulation frames the p-spin ground-state search as a Markov decision process, utilising a reward function computed analytically from the current configuration and coupling tensor. The framework’s efficiency is notable; the reward calculation is both computationally efficient and statistically unbiased. By restricting each episode to start at the all-spins-up configuration and terminate at the all-spins-down configuration, while simultaneously exploiting gauge symmetry, PLANCK explores the configuration space efficiently.

Hypergraph networks and gauge symmetry for scalable p-spin optimisation

A hypergraph neural network underpins PLANCK, a deep reinforcement learning framework designed to address p-spin glass optimisation. This architecture was selected to directly handle the arbitrary high-order interactions characteristic of p-spin models, unlike many existing methods that reduce them to pairwise terms. The network receives as input the configuration of spins on a given graph and outputs an action that modifies these spins, aiming to lower the overall energy of the system.

Crucially, PLANCK exploits gauge symmetry during both its training and subsequent inference phases. This symmetry awareness reduces the search space and improves generalisation capability by ensuring that solutions related by symmetry transformations are treated equivalently. Once trained on relatively small, synthetically generated p-spin instances, PLANCK demonstrates a remarkable ability to generalise to systems many orders of magnitude larger.

Instead of relying on extensive retraining for each new problem size, the framework leverages learned patterns to efficiently explore the solution space of larger instances. At the core of the training process lies a reinforcement learning algorithm, where the agent (PLANCK) receives rewards based on the energy reduction achieved by its actions. By iteratively refining its strategy through trial and error, the agent learns to navigate the complex energy field of p-spin glasses.

The methodological design extends beyond learning to minimise energy. PLANCK’s architecture incorporates a specific mechanism for representing and manipulating hypergraphs, which are generalisations of graphs that allow for interactions between more than two nodes. By representing the p-spin interactions as hyperedges, the network can efficiently process the high-order correlations present in these systems.

Standard graph neural networks struggle with such interactions, often requiring approximations or simplifications. Also, the research team implemented a symmetry-aware design, ensuring that the learned policies are invariant to transformations that preserve the underlying structure of the problem. This is achieved through careful construction of the reward function and the network architecture, encouraging the agent to discover solutions that are strong to symmetry-related perturbations. Since the framework was tested on triangular, square, and hexagonal lattices, the versatility of the approach is apparent.

Reinforcement learning conquers intractable p-spin glass problems

When a problem defies conventional approaches, a new solution often emerges from unexpected quarters. This work presents a striking example, deploying deep reinforcement learning, a technique typically associated with game-playing and robotics, to tackle a class of mathematical problems long considered the exclusive domain of statistical physics. For decades, p-spin glasses, with their complex, high-order interactions, have presented a formidable challenge to computational methods.

The difficulty isn’t merely one of scale, but of fundamental structure; traditional algorithms struggle with the inherent frustration and vastness of the solution space. The significance extends beyond finding better solutions to existing problems. By framing the search for optimal states as a reinforcement learning task, researchers have created a bridge between two seemingly disparate fields.

This framework doesn’t just solve p-spin glasses; it demonstrates a capacity to address a wider range of NP-hard combinatorial optimisation challenges, including those found in logistics, finance, and materials science. The current system relies on training with relatively simple instances, raising questions about its adaptability to real-world complexities where data is noisy and incomplete.

Unlike many machine learning applications, this approach incorporates physical principles, specifically, an awareness of symmetry within the problem. This is a clever design choice, as it reduces the computational burden and improves generalisation. The reliance on synthetic data for training remains a limitation. Future work must explore methods for learning directly from real-world data, potentially through transfer learning or active learning strategies.

Beyond this specific implementation, the broader implications are considerable. We may witness a shift in how we approach intractable problems, moving away from bespoke algorithms towards more general-purpose, learning-based solvers. The success of this physics-inspired approach suggests that other areas of physics may hold untapped potential for advancing machine learning, offering a rich source of inspiration for the next generation of algorithms.