Finding the Ground State of Spin Hamiltonians with Reinforcement Learning

By Kyle Mills, Pooya Ronagh, & Isaac Tamblyn
Reinforcement learning (RL) has become a proven method for optimizing a procedure for which success has been defined, but the specific actions needed to achieve it have not. Using a method we call “controlled online optimization learning” (COOL), we apply the so-called “black box” method of RL to simulated annealing (SA), demonstrating that an RL agent based on proximal policy optimization can, through experience alone, arrive at a temperature schedule that surpasses the performance of standard heuristic temperature schedules for two classes of Hamiltonians. When the system is initialized at a cool temperature, the RL agent learns to heat the system to “melt” it and then slowly cool it in an effort to anneal to the ground state; if the system is initialized at a high temperature, the algorithm immediately cools the system. We investigate the performance of our RL-driven SA agent in generalizing to all Hamiltonians of a specific class. When trained on random Hamiltonians of nearest-neighbour spin glasses, the RL agent is able to control the SA process for other Hamiltonians, reaching the ground state with a higher probability than a simple linear annealing schedule. Furthermore, the scaling performance (with respect to system size) of the RL approach is far more favourable, achieving a performance improvement of almost two orders of magnitude on L = 14² systems. We demonstrate the robustness of the RL approach when the system operates in a “destructive observation” mode, an allusion to a quantum system where measurements destroy the state of the system. The success of the RL agent could have far-reaching impacts, from classical optimization, to quantum annealing and to the simulation of physical systems.

Journal reference:  Mills, K., Ronagh, P., & Tamblyn, I. Finding the ground state of spin Hamiltonians with reinforcement learning. Nat Mach Intell 2, 509–517 (2020).

Most Recent Papers

Scaling Overhead of Locality Reduction in Binary Optimization Problems

By Elisabetta Valiante, Maritza Hernandez, Amin Barzegar, & Helmut G. Katzgraber Recently, there has been considerable interest in solving optimization problems by mapping these onto a binary representation, sparked mostly by the use of quantum annealing machines....

Quantum Multiple Kernel Learning

By Seyed Shakib Vedaie, Moslem Noori, Jaspreet S. Oberoi, Barry C. Sanders, & Ehsan Zahedinejad Kernel methods play an important role in machine learning applications due to their conceptual simplicity and superior performance on numerous machine learning tasks....

Quantum Algorithms for Solving Dynamic Programming Problems

By Pooya RonaghWe present a general quantum algorithm for solving finite-horizon dynamic programming problems. Up to polylogarithmic factors, our algorithm provides a quadratic quantum advantage in terms of the number of states of a given dynamic programming problem....