IEEE International Conference on Rebooting Computing (ICRC)
Gradient matching of higher order combinatorial optimization in quadratic Ising machines
Dmitrii Dobrynin, Mauricio Tedeschi, Arne Heittmann, John Paul Strachan
Abstract
The key limitation of physics-inspired hardware accelerators such as Ising machines (IM) or Hopfield neural networks (HNN) is their lack of support of higher order couplings of spins/neurons. As a result, many classes of combinatorial optimization problems featuring polynomial interactions (PUBO) require quadratic hardware embeddings, QUBO mappings. Such embeddings were shown to risk severe performance reduction due to mismatched configuration space features (energy landscape) compared to the native space formulation. Here, we propose a gradient matching (GM) algorithm which leverages existing IM or in-memory HNN architectures and approximately recovers the native energy landscape. We show an exponential scaling advantage of the GM algorithm time-to-solution. Finally, we propose a hardware design to physically realize our GM in an HNN-based solver.