Scalable almost-linear dynamical Ising machines
arXiv:2205.14760 · doi:10.1007/s11047-024-09983-4
Abstract
The past decade has seen the emergence of Ising machines targeting hard combinatorial optimization problems by minimizing the Ising Hamiltonian with spins represented by continuous dynamical variables. However, capabilities of these machines at larger scales are yet to be fully explored. We investigate an Ising machine based on a network of almost-linearly coupled analog spins. We show that such networks leverage the computational resource similar to that of the semidefinite positive relaxation of the Ising model. We estimate the expected performance of the almost-linear machine and benchmark it on a set of {0,1}-weighted graphs. We show that the running time of the investigated machine scales polynomially (linearly with the number of edges in the connectivity graph). As an example of the physical realization of the machine, we present a CMOS-compatible implementation comprising an array of vertices efficiently storing the continuous spins on charged capacitors and communicating externally via analog current.
References in corpus (6)
- Ising formulations of many NP problems
- Network of Time-Multiplexed Optical Parametric Oscillators as a Coherent Ising Machine
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Vertex coloring of graphs via phase dynamics of coupled oscillatory networks
- Construction of Energy Functions for Lattice Heteropolymer Models: A Case Study in Constraint Satisfaction Programming and Adiabatic Quantum Optimization
- On computational capabilities of Ising machines based on nonlinear oscillators,