Paper detail

From Ising to Potts: Physics-inspired Potts machines of coupled oscillators for low-energy sampling and combinatorial optimization

The $q$-state Potts model is a fundamental model in statistical physics that generalizes the Ising model and plays a key role in the study of phase transitions, critical phenomena, complex systems, and combinatorial optimization. Sampling low-energy configurations of the $q$-state Potts model is essential to these studies, but it remains challenging. While physics-inspired dynamical sampling has been extensively explored for the Ising case ($q=2$) in the form of Ising machines, its generalization to general $q$-state Potts models remains largely unexplored. To fill this gap, we propose a class of physics-inspired dynamical samplers that directly target general $q$-state Potts models, which we refer to as the oscillator Potts machine (OPM). We show, through theoretical analysis and numerical experiments, that the OPM exhibits a systematic low-energy bias with respect to the underlying Potts energy landscape. Furthermore, we demonstrate, via phase perturbation analysis, that the OPM, as overdamped Langevin dynamics, can be realized with a network of self-sustaining oscillators, demonstrating that the OPM is naturally realizable in hardware using standard technology such as CMOS. We design a small-scale ring-oscillator circuit that implements a three-state OPM and validate its operation through transistor-level simulation. Leveraging the low-energy bias of the OPM for Potts models, we then apply it to large-scale max-$K$-cut problems by mapping these instances to $q$-state Potts Hamiltonians and compare its performance against established algorithms. Our results position the OPM as a promising, physically grounded dynamical system framework for multi-state sampling and combinatorial optimization.