Supporting Higher-Order Interactions in Practical Ising Machines
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910919090503680 |
|---|---|
| author | Prova, Nafisa Sadaf Cılasun, Hüsrev Kumar, Abhimanyu Efe, Ahmet Sapatnekar, Sachin S. Karpuzcu, Ulya R. |
| author_facet | Prova, Nafisa Sadaf Cılasun, Hüsrev Kumar, Abhimanyu Efe, Ahmet Sapatnekar, Sachin S. Karpuzcu, Ulya R. |
| contents | Ising machines as hardware solvers of combinatorial optimization problems (COPs) can efficiently explore large solution spaces due to their inherent parallelism and physics-based dynamics. Many important COP classes such as satisfiability (SAT) assume arbitrary interactions between problem variables, while most Ising machines only support pairwise (second-order) interactions. This necessitates translation of higher-order interactions to pair-wise, which typically results in extra variables not corresponding to problem variables, and a larger problem for the Ising machine to solve than the original problem. This in turn can significantly increase time-to-solution and/or degrade solution accuracy. In this paper, considering a representative CMOS-compatible class of Ising machines, we propose a practical design to enable direct hardware support for higher order interactions. By minimizing the overhead of problem translation and mapping, our design leads to up to 4x lower time-to-solution without compromising solution accuracy. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_18486 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Supporting Higher-Order Interactions in Practical Ising Machines Prova, Nafisa Sadaf Cılasun, Hüsrev Kumar, Abhimanyu Efe, Ahmet Sapatnekar, Sachin S. Karpuzcu, Ulya R. Computational Physics Ising machines as hardware solvers of combinatorial optimization problems (COPs) can efficiently explore large solution spaces due to their inherent parallelism and physics-based dynamics. Many important COP classes such as satisfiability (SAT) assume arbitrary interactions between problem variables, while most Ising machines only support pairwise (second-order) interactions. This necessitates translation of higher-order interactions to pair-wise, which typically results in extra variables not corresponding to problem variables, and a larger problem for the Ising machine to solve than the original problem. This in turn can significantly increase time-to-solution and/or degrade solution accuracy. In this paper, considering a representative CMOS-compatible class of Ising machines, we propose a practical design to enable direct hardware support for higher order interactions. By minimizing the overhead of problem translation and mapping, our design leads to up to 4x lower time-to-solution without compromising solution accuracy. |
| title | Supporting Higher-Order Interactions in Practical Ising Machines |
| topic | Computational Physics |
| url | https://arxiv.org/abs/2504.18486 |