Improved Ising formulation of max-3-cut using higher-order spin interactions

Abstract

Many combinatorial optimization problems (COPs) are naturally expressed using variables that take on more than two discrete values. To solve such problems using Ising machines (IMs)—specialized analog or digital devices designed to solve COPs efficiently—these multivalued integers must be encoded using binary spin variables. A common approach is one-hot encoding, where each variable is represented by a group of spins constrained so that exactly one spin is in the “up” state. However, this encoding introduces energy barriers: changing an integer’s value requires flipping two spins and passing through an invalid intermediate state. This creates rugged energy landscapes that may hinder optimization. We propose a higher-order Ising formulation for max-3-cut, a canonical COP involving integers with three possible states that provides a minimal setting for assessing multivalued formulations on IMs. Our formulation preserves valid configurations under single-spin updates. The resulting energy landscapes are smoother, and we show that this remains true even when the binary variables are relaxed to continuous values, making it well suited for analog IMs as well. Benchmarking on such an IM, we find that the higher-order formulation leads to higher success rates and faster time-to-solution than when one-hot encoding is employed.