# Exact Spin Elimination for Quadratic and k-Local Ising Optimization

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 45 references that are in the map.
- First posted on arXiv 12 May 2025.

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

- [Traffic flow optimization using a quantum annealer](https://mlsanity.com/paper/1708.01625/) (2017)
- [Low Autocorrelation Binary Sequences](https://mlsanity.com/paper/1512.02475/) (2015)
- [Quantum-Informed Recursive Optimization Algorithms](https://mlsanity.com/paper/2308.13607/) (2023)
- [Computing High-Degree Polynomial Gradients in Memory](https://mlsanity.com/paper/2401.16204/) (2024)
- [Reducing Binary Quadratic Forms for More Scalable Quantum Annealing](https://mlsanity.com/paper/1801.08652/) (2018)
- [Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines](https://mlsanity.com/paper/2311.01171/) (2023)

## Built on by (most cited first, 1 of 1)

- [Programmable k-local Ising interactions and shallow optical Kolmogorov--Arnold networks through repeated data encounters](https://mlsanity.com/paper/2508.17440/) (2025)

## Abstract (arXiv)

Ising solvers have a finite spin budget. Quadratization uses auxiliary spins to replace higher-order interactions by pairwise ones. We show that removing spins while allowing more complex interactions can fit larger problems within the same spin budget and improve optimization. Walsh elimination minimizes over one spin at a time, writes the resulting interaction as a sum of spin products in the Walsh basis, and stores a rule for recovering the removed spin. Explicit resource limits control which eliminations are accepted. In a held-out test with the protocol frozen before instance generation and one annealing schedule shared by both formulations, mean observed success rises from 10.4% to 97.5% on sparse quadratic spin glasses and from 16.9% to 87.5% on three-body problems. Observed success increases on every instance with a verified reference minimum, and pooled time-to-solution estimates decrease by factors of about 34 and 11, respectively, with preprocessing included. For zero-field pairwise models on connected simple cubic graphs with more than four vertices, we prove that a fixed spin budget accommodates 50% larger inputs while retaining pairwise interactions, zero fields, residual degree at most six, and no increase in coupling count. These results establish exact spin elimination as a controlled trade between active-spin capacity and interaction complexity.