Exact Spin Elimination in Ising Hamiltonians and Energy-Based Machine Learning

We present an exact spin-elimination technique that reduces the dimensionality of both quadratic and k-local Ising Hamiltonians while preserving their original ground-state configurations. By systematically replacing each removed spin with an effective interaction among its neighbors, our method lowers the total spin count without invoking approximations or iterative recalculations. This capability is especially beneficial for hardware-constrained platforms, classical or quantum, that can directly implement multi-body interactions but have limited qubit or spin resources. We demonstrate three key advances enabled by this technique. First, we handle larger instances of benchmark problems such as Max-Cut on cubic graphs without exceeding a 2-local interaction limit. Second, we reduce qubit requirements in QAOA-based integer factorization on near-term quantum devices, thus extending the feasible range of integers to be factorized. Third, we improve memory capacity in Hopfield associative memories and enhance memory retrieval by suppressing spurious attractors, enhancing retrieval performance. Our spin-elimination procedure trades local spin complexity for higher-order couplings or higher node degrees in a single pass, opening new avenues for scaling up combinatorial optimization and energy-based machine learning on near-term hardware. Finally, these results underscore that the next-generation physical spin machines will likely capitalize on k-local spin Hamiltonians to offer an alternative to classical computations.