Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2605.06425

Comparative Study of Potts Machine Dynamics and Performance for Max-k-Cut

Bjarke A. Frederiksen, Robbe De Prins, Peter Bienstman

Published May 7, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2605.06425

Related papers

Improved Ising formulation of max-3-cut using higher-order spin interactions

Robbe De Prins, Guy Van der Sande, Peter Bienstman +1 more

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 multivalued 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, a canonical COP involving integers with three possible states that provides a minimal setting for assessing multivalued formulations on IMs. 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 higher success rates and faster time-to-solution than when one-hot encoding is employed.

arXiv:2508.00565•Physical Review Applied•Mar 27, 2026•1 citation

A comprehensive benchmark of an Ising machine on the Max-Cut problem

Salwa Shaglel, Markus Kirsch, Mårten Winkler +4 more

Abstract Quadratic unconstrained binary optimization (QUBO) formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum–classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.

arXiv:2507.22117•New Journal of Physics•Jun 5, 2026•2 citations

Accelerating the Max-Cut Problems via Distributed Ising Machine Solvers

Xing-Yu Wu, Yi-Xin Zhang, Chen-rui Fan +1 more

The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.

IEEE Transactions on Quantum Engineering•Jan 1, 2026•0 citations

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

Yi Cheng, Zongli Lin

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.

arXiv:2507.18379•Jul 23, 2025•6 citations

Performance Comparison of Typical Binary-Integer Encodings in an Ising Machine

Kensuke Tamura, Tatsuhiko Shirai, Hosho Katsura +2 more

The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.

IEEE Access•Jan 1, 2021•63 citations

A Comparative Study of Coherent Ising Machine Architectures Through a Unified Simulation Model

Vidisha Singhal, Peter A. Bermel

Coherent Ising Machines (CIMs) have emerged as promising hardware solvers for NP-hard combinatorial optimization problems, potentially offering energy-efficiency, accuracy, speed, and scalability. These problems span applications including scheduling, routing, resource allocation, and machine learning. Spin amplitude inhomogeneity (an artifact of its analog nature) can hinder CIM convergence to the ground state. Several CIM modifications have been proposed to address this issue. However, no prior work has systematically compared the performance of these concepts. This paper presents the first side-by-side evaluation of six promising CIM architectures using a unified simulation model. We develop stochastic differential equations, find optimal hyperparameters via Bayesian optimization per problem-architecture pair, and assess the performance on multiple metrics using MaxCut instances from the Gset and BiqMac datasets. CIM-SNN outperforms the rest on most metrics, with a 54.21% average success probability (SP) improvement and 1.36× less time-to-solution (TTS) at 96% GS energy compared to the Standard CIM on BiqMac graphs. Other CIMs show some advantages on certain Gset graphs. CIM-QA is usually the worst-performing, with an 18.55% average SP loss and a 1.30× higher TTS at 96% GS compared to the Standard CIM on BiqMac graphs. CIM-SNN demonstrates the greatest noise robustness and promise for further tuning via a linear pump schedule. CIM-QA benefits from high noise levels. This study makes two key contributions: (1) identifying promising CIM architectures to guide targeted research and accelerate practical adoption, and (2) providing a unified framework for evaluating future architectural modifications against existing ones.

IEEE Access•Jan 1, 2025•0 citations
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.
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 multivalued 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, a canonical COP involving integers with three possible states that provides a minimal setting for assessing multivalued formulations on IMs. 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 higher success rates and faster time-to-solution than when one-hot encoding is employed.
Abstract Quadratic unconstrained binary optimization (QUBO) formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum–classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.
The Ising machine, as a quantum-inspired computing system, can be used to efficiently solve combinatorial optimization problems. Ongoing studies have positioned it to potentially surpass the performance limitations of traditional computers. However, such Ising machines also suffer from scalability as the solution quality becomes sub-optimal when the problem size increases. In this work, we propose an Ising-based framework that uses a distributed Ising algorithm to find the near-optimal solution for large-scale Max-Cut problems through parallel processing via graph segmentation and reassembly. We selected the coherent Ising machine as the hardware solver and successfully found the solution for a 2000-node instance utilizing 20 computational bits on the Gset standard dataset. Additionally, we investigated the key factors influencing the system's performance and discovered that setting the number of reorganizations to one results in higher accuracy. Building on this configuration, we utilized a 100-bit CIM hardware platform (CPQC-1) to solve instances with varying numbers of nodes. The experimental results agree well with the theoretical simulations, confirming the practical feasibility of our method. Moreover, compared to existing Ising-based solvers, our algorithm significantly reduces computational resource requirements while achieving superior performance on large-scale combinatorial optimization problems, highlighting its effectiveness on quantum-inspired hardware.
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.
The differences in performance among binary-integer encodings in an Ising machine, which can solve combinatorial optimization problems, are investigated. Many combinatorial optimization problems can be mapped to find the lowest-energy (ground) state of an Ising model or its equivalent model, the Quadratic Unconstrained Binary Optimization (QUBO). Since the Ising model and QUBO consist of binary variables, they often express integers as binary when using Ising machines. A typical example is the combinatorial optimization problem under inequality constraints. Here, the quadratic knapsack problem is adopted as a prototypical problem with an inequality constraint. It is solved using typical binary-integer encodings: one-hot encoding, binary encoding, and unary encoding. Unary encoding shows the best performance for large-sized problems.
Coherent Ising Machines (CIMs) have emerged as promising hardware solvers for NP-hard combinatorial optimization problems, potentially offering energy-efficiency, accuracy, speed, and scalability. These problems span applications including scheduling, routing, resource allocation, and machine learning. Spin amplitude inhomogeneity (an artifact of its analog nature) can hinder CIM convergence to the ground state. Several CIM modifications have been proposed to address this issue. However, no prior work has systematically compared the performance of these concepts. This paper presents the first side-by-side evaluation of six promising CIM architectures using a unified simulation model. We develop stochastic differential equations, find optimal hyperparameters via Bayesian optimization per problem-architecture pair, and assess the performance on multiple metrics using MaxCut instances from the Gset and BiqMac datasets. CIM-SNN outperforms the rest on most metrics, with a 54.21% average success probability (SP) improvement and 1.36× less time-to-solution (TTS) at 96% GS energy compared to the Standard CIM on BiqMac graphs. Other CIMs show some advantages on certain Gset graphs. CIM-QA is usually the worst-performing, with an 18.55% average SP loss and a 1.30× higher TTS at 96% GS compared to the Standard CIM on BiqMac graphs. CIM-SNN demonstrates the greatest noise robustness and promise for further tuning via a linear pump schedule. CIM-QA benefits from high noise levels. This study makes two key contributions: (1) identifying promising CIM architectures to guide targeted research and accelerate practical adoption, and (2) providing a unified framework for evaluating future architectural modifications against existing ones.