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

Repository containing the code to reproduce the experiments in the paper "From Ising to Potts: physics-inspired Potts machines in coupled oscillators for low-energy sampling and combinatorial optimization". It contains four standalone Python scripts: Max_2_cut.py — OPM solver for Max-2-Cut Max_3_cut.py — OPM solver for Max-3-Cut Max_4_cut.py — OPM solver for Max-4-Cut Max_5_cut.py — OPM solver for Max-5-Cut The benchmark graph instances G1–G5 are included as text files (G1.txt–G5.txt) in the same folder. Requirements Python 3.9+ and the packages listed in requirements.txt (notably: numpy, scipy, matplotlib, torch, torchsde). How to run (Jupyter / terminal) After installing dependencies: In a Jupyter notebook: %run Max_2_cut.py %run Max_3_cut.py %run Max_4_cut.py %run Max_5_cut.py Or in a terminal: python Max_2_cut.py (and similarly for Max-3/4/5) The scripts generate the output figures in the working directory (e.g., box plots summarizing solution quality across instances). GPU recommendation For best performance, we recommend running the code on a GPU. The runtime numbers reported below were measured on NVIDIA GeForce RTX 2080 Ti (CUDA 12.8; driver 570.124.06). Actual wall-clock time may vary with hardware and system load. Reproducibility and runtime For a faster sanity check, start with seed_num = 1 (typical wall-clock times to finish all instances G1–G5: Max-3-Cut ~12 min, Max-4-Cut ~16 min, Max-5-Cut ~24 min).To reproduce the results reported in the paper, use seed_num = 20.