# Improved Sparse Ising Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 27 references that are in the map.
- First posted on arXiv 15 Nov 2023.

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

- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [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)
- [Analog Iterative Machine (AIM): using light to solve quadratic optimization problems with mixed variables](https://mlsanity.com/paper/2304.12594/) (2023)
- [Monte Carlo Policy Gradient Method for Binary Optimization](https://mlsanity.com/paper/2307.00783/) (2023)
- [Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups](https://mlsanity.com/paper/2307.09442/) (2023)

## Abstract (arXiv)

Sparse Ising problems can be found in application areas such as logistics, condensed matter physics and training of deep Boltzmann networks, but can be very difficult to tackle with high efficiency and accuracy. This report presents new data demonstrating significantly higher performance on some longstanding benchmark problems with up to 20,000 variables. The data come from a new heuristic algorithm tested on the large sparse instances from the Gset benchmark suite. Relative to leading reported combinations of speed and accuracy (e.g., from Toshiba's Simulated Bifurcation Machine and Breakout Local Search), a proof-of-concept implementation reached targets 2-4 orders of magnitude faster. For two instances (G72 and G77) the new algorithm discovered a better solution than all previously reported values. Solution bitstrings confirming these two best solutions are provided. The data suggest exciting possibilities for pushing the sparse Ising performance frontier to potentially strengthen algorithm portfolios, AI toolkits and decision-making systems.