Furkejuvvon:
| Váldodahkkit: | , , , |
|---|---|
| Materiálatiipa: | Preprint |
| Almmustuhtton: |
2025
|
| Fáttát: | |
| Liŋkkat: | https://arxiv.org/abs/2508.00565 |
| Fáddágilkorat: |
Lasit fáddágilkoriid
Eai fáddágilkorat, Lasit vuosttaš fáddágilkora!
|
Sisdoallologahallan:
- 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.