2025/08/01 by Robbe De Prins, De Prins, Robbe, Guy Van der Sande +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Adaptation and Self-Organizing Systems (nlin.AO) #Applied Physics (physics.app-ph) #Cellular Automata and Lattice Gases (nlin.CG) #Complexity and Algorithms in Graphs #DNA and Biological Computing #FOS: Physical sciences #Mathematical Physics (math-ph) #Quantum Computing Algorithms and Architecture #Statistical Mechanics (cond-mat.stat-mech)
paper · pdf · doi:10.48550/arxiv.2508.00565
openalex publication_date 2025/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 multi-valued 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, which is the smallest fundamental COP with multi-valued integer variables. 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 significantly faster solutions than the Ising baseline. Interestingly, we find that an empirical rescaling of some terms in the Ising formulation - a heuristic proposed in prior work - approaches the performance of the higher-order Ising formulation, underscoring the importance of empirical parameter tuning in COP encodings.