# Efficient Optimization Accelerator Framework for Multistate Ising Problems

arXiv: https://arxiv.org/abs/2505.20250 · HTML: https://mlsanity.com/paper/2505.20250/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 62 references that are in the map.
- First posted on arXiv 26 May 2025.

## Builds on (most cited first, 12 of 12)

- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [Compute Trends Across Three Eras of Machine Learning](https://mlsanity.com/paper/2202.05924/) (2022)
- [Graph Coloring with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2202.01606/) (2022)
- [Massively Parallel Probabilistic Computing with Sparse Ising Machines](https://mlsanity.com/paper/2110.02481/) (2021)
- [Training Deep Boltzmann Networks with Sparse Ising Machines](https://mlsanity.com/paper/2303.10728/) (2023)
- [Rethinking Graph Neural Networks for the Graph Coloring Problem](https://mlsanity.com/paper/2208.06975/) (2022)
- [All-to-all reconfigurability with sparse and higher-order Ising machines](https://mlsanity.com/paper/2312.08748/) (2023)
- [ON-OFF Neuromorphic ISING Machines using Fowler-Nordheim Annealers](https://mlsanity.com/paper/2406.05224/) (2024)
- [CMOS-compatible Ising and Potts Annealing Using Single Photon Avalanche Diodes](https://mlsanity.com/paper/2211.12607/) (2022)
- [Logically Synthesized, Hardware-Accelerated, Restricted Boltzmann Machines for Combinatorial Optimization and Integer Factorization](https://mlsanity.com/paper/2007.13489/) (2020)
- [Ising Model Optimization Problems on a FPGA Accelerated Restricted Boltzmann Machine](https://mlsanity.com/paper/2008.04436/) (2020)
- [PASS: An Asynchronous Probabilistic Processor for Next Generation Intelligence](https://mlsanity.com/paper/2409.10325/) (2024)

## Abstract (arXiv)

Ising Machines are emerging hardware architectures that efficiently solve NP-Hard combinatorial optimization problems. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form, but this transformation often complicates the solution landscape, degrading performance, especially for multi-state problems. To address this challenge, we model spin interactions as generalized boolean logic function to significantly reduce the exploration space. We demonstrate the effectiveness of our approach on graph coloring problem using probabilistic Ising solvers, achieving similar accuracy compared to state-of-the-art heuristics and machine learning algorithms. It also shows significant improvement over state-of-the-art QUBO-based Ising solvers, including probabilistic Ising and simulated bifurcation machines. We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach that shows ~10000x performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5-4x over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.