Efficient optimization with higher-order Ising machines
Abstract A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization prob...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2023-09-01
|
| Series: | Nature Communications |
| Online Access: | https://doi.org/10.1038/s41467-023-41214-9 |
| _version_ | 1797276490953392128 |
|---|---|
| author | Connor Bybee Denis Kleyko Dmitri E. Nikonov Amir Khosrowshahi Bruno A. Olshausen Friedrich T. Sommer |
| author_facet | Connor Bybee Denis Kleyko Dmitri E. Nikonov Amir Khosrowshahi Bruno A. Olshausen Friedrich T. Sommer |
| author_sort | Connor Bybee |
| collection | DOAJ |
| description | Abstract A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Boolean k-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines. |
| first_indexed | 2024-03-07T15:28:57Z |
| format | Article |
| id | doaj.art-9ec908aeb3da4fd8a8b5da279e69aaab |
| institution | Directory Open Access Journal |
| issn | 2041-1723 |
| language | English |
| last_indexed | 2024-03-07T15:28:57Z |
| publishDate | 2023-09-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Nature Communications |
| spelling | doaj.art-9ec908aeb3da4fd8a8b5da279e69aaab2024-03-05T16:33:58ZengNature PortfolioNature Communications2041-17232023-09-0114111010.1038/s41467-023-41214-9Efficient optimization with higher-order Ising machinesConnor Bybee0Denis Kleyko1Dmitri E. Nikonov2Amir Khosrowshahi3Bruno A. Olshausen4Friedrich T. Sommer5Redwood Center for Theoretical Neuroscience, University of CaliforniaRedwood Center for Theoretical Neuroscience, University of CaliforniaComponents Research, IntelRedwood Center for Theoretical Neuroscience, University of CaliforniaRedwood Center for Theoretical Neuroscience, University of CaliforniaRedwood Center for Theoretical Neuroscience, University of CaliforniaAbstract A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Boolean k-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines.https://doi.org/10.1038/s41467-023-41214-9 |
| spellingShingle | Connor Bybee Denis Kleyko Dmitri E. Nikonov Amir Khosrowshahi Bruno A. Olshausen Friedrich T. Sommer Efficient optimization with higher-order Ising machines Nature Communications |
| title | Efficient optimization with higher-order Ising machines |
| title_full | Efficient optimization with higher-order Ising machines |
| title_fullStr | Efficient optimization with higher-order Ising machines |
| title_full_unstemmed | Efficient optimization with higher-order Ising machines |
| title_short | Efficient optimization with higher-order Ising machines |
| title_sort | efficient optimization with higher order ising machines |
| url | https://doi.org/10.1038/s41467-023-41214-9 |
| work_keys_str_mv | AT connorbybee efficientoptimizationwithhigherorderisingmachines AT deniskleyko efficientoptimizationwithhigherorderisingmachines AT dmitrienikonov efficientoptimizationwithhigherorderisingmachines AT amirkhosrowshahi efficientoptimizationwithhigherorderisingmachines AT brunoaolshausen efficientoptimizationwithhigherorderisingmachines AT friedrichtsommer efficientoptimizationwithhigherorderisingmachines |