Comparative Study of Potts Machine Dynamics and Performance for Max-k-Cut
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916000683786240 |
|---|---|
| author | Frederiksen, Bjarke Almer De Prins, Robbe Bienstman, Peter |
| author_facet | Frederiksen, Bjarke Almer De Prins, Robbe Bienstman, Peter |
| contents | Combinatorial optimization problems in logistics, finance, energy, and scheduling routinely involve multi-state decision variables. Ising machines (IMs) require binary expansions (e.g., one-hot encoding) to encode such variables, whereas Potts machines (PMs) represent them natively. By doing so, PMs are expected to outperform IMs on multi-state problems. To the best of our knowledge, no systematic study of PM models has yet assessed whether this expectation holds. We therefore benchmark five representative PMs against a reference IM on Max-3-Cut and Max-4-Cut, using 800-vertex GSet graphs and random graphs of up to 50 vertices. Surprisingly, the reference IM still outperforms every PM, and the IM supremacy increases significantly in going from Max-3-Cut to Max-4-Cut. These results provide clear evidence that current PM dynamics underperform relative to binary approaches, even in regimes where they are presumed advantageous. We provide a way forward by quantifying the underperformance of current PMs, as well as by identifying three dynamical properties that correlate strongly with their performance ranking. Our work stresses the need for more systematic assessments of algorithmic performance in order to guide the design of more effective Potts machines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_06425 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Comparative Study of Potts Machine Dynamics and Performance for Max-k-Cut Frederiksen, Bjarke Almer De Prins, Robbe Bienstman, Peter Statistical Mechanics Mathematical Physics Adaptation and Self-Organizing Systems Cellular Automata and Lattice Gases Applied Physics Combinatorial optimization problems in logistics, finance, energy, and scheduling routinely involve multi-state decision variables. Ising machines (IMs) require binary expansions (e.g., one-hot encoding) to encode such variables, whereas Potts machines (PMs) represent them natively. By doing so, PMs are expected to outperform IMs on multi-state problems. To the best of our knowledge, no systematic study of PM models has yet assessed whether this expectation holds. We therefore benchmark five representative PMs against a reference IM on Max-3-Cut and Max-4-Cut, using 800-vertex GSet graphs and random graphs of up to 50 vertices. Surprisingly, the reference IM still outperforms every PM, and the IM supremacy increases significantly in going from Max-3-Cut to Max-4-Cut. These results provide clear evidence that current PM dynamics underperform relative to binary approaches, even in regimes where they are presumed advantageous. We provide a way forward by quantifying the underperformance of current PMs, as well as by identifying three dynamical properties that correlate strongly with their performance ranking. Our work stresses the need for more systematic assessments of algorithmic performance in order to guide the design of more effective Potts machines. |
| title | Comparative Study of Potts Machine Dynamics and Performance for Max-k-Cut |
| topic | Statistical Mechanics Mathematical Physics Adaptation and Self-Organizing Systems Cellular Automata and Lattice Gases Applied Physics |
| url | https://arxiv.org/abs/2605.06425 |