Energy landscapes of combinatorial optimization in Ising machines
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912076375523328 |
|---|---|
| author | Dobrynin, Dmitrii Renaudineau, Adrien Hizzani, Mohammad Strukov, Dmitri Mohseni, Masoud Strachan, John Paul |
| author_facet | Dobrynin, Dmitrii Renaudineau, Adrien Hizzani, Mohammad Strukov, Dmitri Mohseni, Masoud Strachan, John Paul |
| contents | Physics-based Ising machines (IM) have been developed as dedicated processors for solving hard combinatorial optimization problems with higher speed and better energy efficiency. Generally, such systems employ local search heuristics to traverse energy landscapes in searching for optimal solutions. Here, we quantify and address some of the major challenges met by IMs by extending energy-landscape geometry visualization tools known as disconnectivity graphs. Using efficient sampling methods, we visually capture landscapes of problems having diverse structure and hardness manifesting as energetic and entropic barriers for IMs. We investigate energy barriers, local minima, and configuration space clustering effects caused by locality reduction methods when embedding combinatorial problems to the Ising hardware. To this end, we sample disconnectivity graphs of PUBO energy landscapes and their different QUBO mappings accounting for both local minima and saddle regions. We demonstrate that QUBO energy landscape properties lead to the subpar performance for quadratic IMs and suggest directions for their improvement. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_01320 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Energy landscapes of combinatorial optimization in Ising machines Dobrynin, Dmitrii Renaudineau, Adrien Hizzani, Mohammad Strukov, Dmitri Mohseni, Masoud Strachan, John Paul Disordered Systems and Neural Networks Physics-based Ising machines (IM) have been developed as dedicated processors for solving hard combinatorial optimization problems with higher speed and better energy efficiency. Generally, such systems employ local search heuristics to traverse energy landscapes in searching for optimal solutions. Here, we quantify and address some of the major challenges met by IMs by extending energy-landscape geometry visualization tools known as disconnectivity graphs. Using efficient sampling methods, we visually capture landscapes of problems having diverse structure and hardness manifesting as energetic and entropic barriers for IMs. We investigate energy barriers, local minima, and configuration space clustering effects caused by locality reduction methods when embedding combinatorial problems to the Ising hardware. To this end, we sample disconnectivity graphs of PUBO energy landscapes and their different QUBO mappings accounting for both local minima and saddle regions. We demonstrate that QUBO energy landscape properties lead to the subpar performance for quadratic IMs and suggest directions for their improvement. |
| title | Energy landscapes of combinatorial optimization in Ising machines |
| topic | Disordered Systems and Neural Networks |
| url | https://arxiv.org/abs/2403.01320 |