Efficient Optimization with Higher-Order Ising Machines
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 \textit{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.
Code (0)
등록된 구현이 없습니다.
Tasks
Combinatorial OptimizationSimilar Papers 제목 키워드 기반
Higher-Order Neuromorphic Ising Machines -- Autoencoders and Fowler-Nordheim Annealers are all you need for Scalability
We report a higher-order neuromorphic Ising machine that exhibits superior scalability compared to architectures based on quadratization, while also achieving state-of-the-art quality and reliability in solutions with co…
AllCombinatorial OptimizationAnalysis of Higher-Order Ising Hamiltonians
It is challenging to scale Ising machines for industrial-level problems due to algorithm or hardware limitations. Although higher-order Ising models provide a more compact encoding, they are, however, hard to physically …
All-to-all reconfigurability with sparse and higher-order Ising machines
Domain-specific hardware to solve computationally hard optimization problems has generated tremendous excitement. Here, we evaluate probabilistic bit (p-bit) based Ising Machines (IM) on the 3-regular 3-Exclusive OR Sati…
AllCombinatorial OptimizationGPUMaximally Permissive Reward Machines
Reward machines allow the definition of rewards for temporally extended tasks and behaviors. Specifying "informative" reward machines can be challenging. One way to address this is to generate reward machines from a high…
Noise-injected analog Ising machines enable ultrafast statistical sampling and machine learning
Ising machines are a promising non-von-Neumann computational concept for neural network training and combinatorial optimization. However, while various neural networks can be implemented with Ising machines, their inabil…
BIG-bench Machine LearningCombinatorial Optimization