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!
|
| _version_ | 1832542843233632256 |
|---|---|
| author | Dairong Chen Andrew D. Kent Dries Sels Flaviano Morone |
| author_facet | Dairong Chen Andrew D. Kent Dries Sels Flaviano Morone |
| author_sort | Dairong Chen |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-aa621fd29bee4097aaafbda23ef7a63b |
| institution | Kabale University |
| issn | 2643-1564 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj-art-aa621fd29bee4097aaafbda23ef7a63b2025-02-03T15:13:10ZengAmerican Physical SocietyPhysical Review Research2643-15642025-02-017101312910.1103/PhysRevResearch.7.013129Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systemsDairong ChenAndrew D. KentDries SelsFlaviano MoroneWe 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.http://doi.org/10.1103/PhysRevResearch.7.013129 |
| spellingShingle | Dairong Chen Andrew D. Kent Dries Sels Flaviano Morone Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systems Physical Review Research |
| title | Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systems |
| title_full | Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systems |
| title_fullStr | Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systems |
| title_full_unstemmed | Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systems |
| title_short | Solving combinatorial optimization problems through stochastic Landau-Lifshitz-Gilbert dynamical systems |
| title_sort | solving combinatorial optimization problems through stochastic landau lifshitz gilbert dynamical systems |
| url | http://doi.org/10.1103/PhysRevResearch.7.013129 |
| work_keys_str_mv | AT dairongchen solvingcombinatorialoptimizationproblemsthroughstochasticlandaulifshitzgilbertdynamicalsystems AT andrewdkent solvingcombinatorialoptimizationproblemsthroughstochasticlandaulifshitzgilbertdynamicalsystems AT driessels solvingcombinatorialoptimizationproblemsthroughstochasticlandaulifshitzgilbertdynamicalsystems AT flavianomorone solvingcombinatorialoptimizationproblemsthroughstochasticlandaulifshitzgilbertdynamicalsystems |