A Continuous Energy Ising Machine Leveraging Difference-of-Convex Programming
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_ | 1866918241584021504 |
|---|---|
| author | Banerjee, Debraj Mahapatra, Santanu Chaudhury, Kunal Narayan |
| author_facet | Banerjee, Debraj Mahapatra, Santanu Chaudhury, Kunal Narayan |
| contents | Many combinatorial optimization problems can be reformulated as finding the ground state of the Ising model. Existing Ising solvers are mostly inspired by simulated annealing. Although annealing techniques offer scalability, they lack convergence guarantees and are sensitive to the cooling schedule. We propose solving the Ising problem by relaxing the binary spins to continuous variables and introducing an attraction potential that steers the solution toward binary spin configurations. A key property of this potential is that its combination with the Ising energy produces a Hamiltonian that can be written as a difference of convex polynomials. This enables us to design efficient iterative algorithms that require a single matrix-vector multiplication per iteration and provide convergence guarantees. We implement our Ising solver on a wide range of GPU platforms, from edge devices to high-performance computing clusters, and demonstrate that it consistently outperforms existing solvers across problem sizes ranging from small ($10^3$ spins) to ultra-large ($10^8$ spins). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_01928 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Continuous Energy Ising Machine Leveraging Difference-of-Convex Programming Banerjee, Debraj Mahapatra, Santanu Chaudhury, Kunal Narayan Distributed, Parallel, and Cluster Computing Mathematical Physics Optimization and Control Quantum Physics 90C26, 90C59, 82B20, 68W40, 65K10, 82C32 Many combinatorial optimization problems can be reformulated as finding the ground state of the Ising model. Existing Ising solvers are mostly inspired by simulated annealing. Although annealing techniques offer scalability, they lack convergence guarantees and are sensitive to the cooling schedule. We propose solving the Ising problem by relaxing the binary spins to continuous variables and introducing an attraction potential that steers the solution toward binary spin configurations. A key property of this potential is that its combination with the Ising energy produces a Hamiltonian that can be written as a difference of convex polynomials. This enables us to design efficient iterative algorithms that require a single matrix-vector multiplication per iteration and provide convergence guarantees. We implement our Ising solver on a wide range of GPU platforms, from edge devices to high-performance computing clusters, and demonstrate that it consistently outperforms existing solvers across problem sizes ranging from small ($10^3$ spins) to ultra-large ($10^8$ spins). |
| title | A Continuous Energy Ising Machine Leveraging Difference-of-Convex Programming |
| topic | Distributed, Parallel, and Cluster Computing Mathematical Physics Optimization and Control Quantum Physics 90C26, 90C59, 82B20, 68W40, 65K10, 82C32 |
| url | https://arxiv.org/abs/2509.01928 |