Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systems
We 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 dynamics. Conventional techniques to solve discrete optimization problems that use simple continuous relaxa...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
American Physical Society
2025-02-01
|
| Series: | Physical Review Research |
| Online Access: | http://doi.org/10.1103/PhysRevResearch.7.013129 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | We 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 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. Our method considers the physical dynamics of macrospins capable of escaping from local minima, 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. Our 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. |
|---|---|
| ISSN: | 2643-1564 |