Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systems.

A compelling idea linking physics and discrete mathematics is to leverage the intrinsic dynamics of real-world physical systems to solve mathematical optimization problems. The idea relies on correspondence between the variables of the mathematical problem and the degrees of freedom of an analogue physical system, where the role of the objective function to be optimized is played by the energy function of the interacting physical system. Once this correspondence has been successfully established, all one has to do is to cool the physical system down to zero temperature and wait for it to settle in its ground state, i.e., the state with minimal energy, which, in turn, represents the solution to the original optimization problem.

I will present a method to approximately solve general instances of combinatorial optimization problems using the physical dynamics of three-dimensional (3d) rotors obeying Landau-Lifshitz-Gilbert (LLG) dynamics. Conventional techniques to solve discrete optimization problems that use simple continuous relaxation of the objective function followed by gradient descent minimization are inherently unable to avoid local optima, thus producing poor-quality solutions. The LLG dynamical system considers the physical dynamics of 3d macrospins capable of avoiding local minima. It does so by slowly dissipating energy following trajectories that lie close to the level curves of the energy function, thus facilitating the discovery of high-quality, nearly optimal solutions, as supported by extensive numerical simulations on a prototypical quadratic unconstrained binary optimization (QUBO) problem. The method produces solutions that compare favorably with those obtained using state-of-the-art minimization algorithms (such as simulated annealing) while offering the advantage of being physically realizable by means of arrays of stochastic magnetic tunnel junction devices.

Finally, I will show that the same LLG dynamical system immediately suggests an interesting generalization of the Hopfield’s model of associative memory, where the states of the neurons are represented by 3d rotors instead of Ising binary spins, and the process of memory retrieval is carried out via LLG dynamics instead of the canonical spin-flip Glauber dynamics.