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:2508.00565 · Physical Review Applied

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

Robbe De Prins, Guy Van der Sande, Peter Bienstman, Thomas Van Vaerenbergh

Published Mar 27, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.1103/vqsv-jzk4

Related papers

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

Bjarke A. Frederiksen, Robbe De Prins, Peter Bienstman

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.

arXiv:2605.06425•May 7, 2026•0 citations

Discretized spin interactions enhance higher-order analog Ising machines

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

Ising machines are specialized devices designed to efficiently solve combinatorial optimization problems. Among such problems, Boolean Satisfiability (SAT) is particularly relevant in industrial applications. To solve SAT problems using Ising machines, it is crucial to incorporate higher-order interactions. However, in analog Ising machines, interactions of different orders scale unevenly with the continuous spin amplitudes, introducing imbalances that can significantly degrade performance. Here we present a numerical comparison of methods to mitigate these imbalances, evaluating time-to-solution and success rate on uniform random 3-SAT and 4-SAT instances. Our results show that the most effective approach employs spin interactions that are proportional to the signs of spins, rather than their continuous amplitudes. We further demonstrate that smooth approximations of this method make it compatible with analog hardware. These findings underscore the central role of spin-sign-based interactions in enabling robust and scalable analog Ising machine dynamics. Ising machines (IMs) offer promising solutions for combinatorial optimization problems yet face challenges with imbalances in higher-order interactions when applied to Boolean Satisfiability (SAT) tasks. Here, the authors demonstrate that employing spin-sign-based interactions effectively mitigates these imbalances, enhancing performance and compatibility with analog hardware, thus advancing robust and scalable IM dynamics.

arXiv:2507.23621•Communications Physics•Aug 5, 2026•3 citations

Efficient Implementation of Parallel Annealing Method with Heisenberg Model

Kazuma Kanai, T. Kawahara

Annealing processors that can quickly solve combinatorial optimization problems (COPs) are attracting attention. They solve COPs by converting them into spin-spin interactions and external fields of the Ising model. Annealing processors that use fully-coupled spin coupling can solve a wide range of COPs. However, it is difficult to execute parallel annealing in fully-coupled spin coupling because one spin is updated by referring to all the other spins. In this paper, we proposed multi-state pseudo annealing (MSPA), which is an annealing method for changing the spin value from a conventional binary to a multi state that takes into account intermediate states. In a software validation, we solved the Maxcut problem and the traveling salesman problem and confirmed that the proposed method improves the solution quality in parallel annealing compared with simulated annealing and pseudo annealing. In addition, we implemented MSPA on a field-programmable gate array as a 1024 -spin 16 -parallel system using a scalable structure. With the proposed system, we solved the Max-cut problem and confirmed that it achieves a 9.40 times faster solving speed and yields a 1% larger Max-cut value compared with the conventional parallelized annealing processors.

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS)•Nov 7, 2024•3 citations

Self-Adaptive Ising Machines for Constrained Optimization

Corentin Delacour

Ising machines (IM) are physics-inspired alternatives to von Neumann architectures for solving hard optimization tasks. By mapping binary variables to coupled Ising spins, IMs can naturally solve unconstrained combinatorial optimization problems such as finding maximum cuts in graphs. However, despite their importance in practical applications, constrained problems remain challenging to solve for IMs that require large quadratic energy penalties to ensure the correspondence between energy ground states and constrained optimal solutions. To relax this requirement, we propose a self-adaptive IM that iteratively shapes its energy landscape using a Lagrange relaxation of constraints and avoids prior tuning of penalties. Using a probabilistic-bit (p-bit) IM emulated in software, we benchmark our algorithm with multidimensional knapsack problems (MKP) and quadratic knapsack problems (QKP), the latter being an Ising problem with linear constraints. For QKP with 300 variables, the proposed algorithm finds better solutions than state-of-the-art IMs such as Fujitsu's Digital Annealer and requires 7,500x fewer samples. Our results show that adapting the energy landscape during the search can speed up IMs for constrained optimization.

arXiv:2501.04971•Design, Automation, and Test in Europe•Mar 31, 2025•3 citations

Efficient Optimization with Encoded Ising Models

Devrath Iyer, Sara Achour

Many promising computing substrates, including quantum computers, oscillator-based computers, and p computers solve constrained combinatorial optimization problems by minimizing energy functions called Ising models. Because Ising solvers explore an unconstrained search space, Ising models for many popular optimization problems must include penalty terms to raise the energy of infeasible solutions that would appear optimal otherwise. We observe that for some problems, Ising solvers spend the majority of computation time exploring this invalid state and often never find a feasible solution. We introduce the encoded Ising model (E-I model), an extension to the Ising model that uses a digital encoding circuit to vastly reduce the proportion of time a solver spends exploring invalid states. We present Fuse, a software framework that enables the description of such functions and automatically lowers them to a p-computer. Our formulation reduces the number of iterations to a solution by a factor of $7.2-52000 \mathrm{x}$ and achieves up to $\mathbf{1 0 0. 0 \%}$ higher estimated success probability over baseline formulations.

IEEE International Symposium on High-Performance Computer Architecture (HPCA)•Mar 1, 2025•7 citations

Spin Connection Topology and Multi-Bit Spin Interaction Coefficients of Ising Spin Model with Digital Logic Gates

Tsukasa Miki, M. Shimada, Jun‐ichi Shirakashi

Combinatorial optimization problems often arise naturally in various fields of research. However, finding the global optimum solution of these problems remains computationally difficult. Ising spin model is considered to be an effective method to solve combinatorial optimization problems because these problems can be mapped and embedded into the Ising spin model. In general, Ising spin model requires to adjust and tune the spin connection parameters, for example, topology of spin connection and resolution of exchange interaction coefficient values between spins, according to the problems. In this paper, we focus on the number of spin connection, which is one of the spin connection parameters, and perform the calculation experiments through solving max-cut problems with Ising spin computing. As a result, all-to-all connectivity makes Ising spin computing well suited for searching the ground states of complex combinatorial optimization problems.

IEEE International Conference on Design & Test of Integrated Micro & Nano-Systems (DTS)•Jun 1, 2020•4 citations
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.
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.
Ising machines are specialized devices designed to efficiently solve combinatorial optimization problems. Among such problems, Boolean Satisfiability (SAT) is particularly relevant in industrial applications. To solve SAT problems using Ising machines, it is crucial to incorporate higher-order interactions. However, in analog Ising machines, interactions of different orders scale unevenly with the continuous spin amplitudes, introducing imbalances that can significantly degrade performance. Here we present a numerical comparison of methods to mitigate these imbalances, evaluating time-to-solution and success rate on uniform random 3-SAT and 4-SAT instances. Our results show that the most effective approach employs spin interactions that are proportional to the signs of spins, rather than their continuous amplitudes. We further demonstrate that smooth approximations of this method make it compatible with analog hardware. These findings underscore the central role of spin-sign-based interactions in enabling robust and scalable analog Ising machine dynamics. Ising machines (IMs) offer promising solutions for combinatorial optimization problems yet face challenges with imbalances in higher-order interactions when applied to Boolean Satisfiability (SAT) tasks. Here, the authors demonstrate that employing spin-sign-based interactions effectively mitigates these imbalances, enhancing performance and compatibility with analog hardware, thus advancing robust and scalable IM dynamics.
Annealing processors that can quickly solve combinatorial optimization problems (COPs) are attracting attention. They solve COPs by converting them into spin-spin interactions and external fields of the Ising model. Annealing processors that use fully-coupled spin coupling can solve a wide range of COPs. However, it is difficult to execute parallel annealing in fully-coupled spin coupling because one spin is updated by referring to all the other spins. In this paper, we proposed multi-state pseudo annealing (MSPA), which is an annealing method for changing the spin value from a conventional binary to a multi state that takes into account intermediate states. In a software validation, we solved the Maxcut problem and the traveling salesman problem and confirmed that the proposed method improves the solution quality in parallel annealing compared with simulated annealing and pseudo annealing. In addition, we implemented MSPA on a field-programmable gate array as a 1024 -spin 16 -parallel system using a scalable structure. With the proposed system, we solved the Max-cut problem and confirmed that it achieves a 9.40 times faster solving speed and yields a 1% larger Max-cut value compared with the conventional parallelized annealing processors.
Ising machines (IM) are physics-inspired alternatives to von Neumann architectures for solving hard optimization tasks. By mapping binary variables to coupled Ising spins, IMs can naturally solve unconstrained combinatorial optimization problems such as finding maximum cuts in graphs. However, despite their importance in practical applications, constrained problems remain challenging to solve for IMs that require large quadratic energy penalties to ensure the correspondence between energy ground states and constrained optimal solutions. To relax this requirement, we propose a self-adaptive IM that iteratively shapes its energy landscape using a Lagrange relaxation of constraints and avoids prior tuning of penalties. Using a probabilistic-bit (p-bit) IM emulated in software, we benchmark our algorithm with multidimensional knapsack problems (MKP) and quadratic knapsack problems (QKP), the latter being an Ising problem with linear constraints. For QKP with 300 variables, the proposed algorithm finds better solutions than state-of-the-art IMs such as Fujitsu's Digital Annealer and requires 7,500x fewer samples. Our results show that adapting the energy landscape during the search can speed up IMs for constrained optimization.
Many promising computing substrates, including quantum computers, oscillator-based computers, and p computers solve constrained combinatorial optimization problems by minimizing energy functions called Ising models. Because Ising solvers explore an unconstrained search space, Ising models for many popular optimization problems must include penalty terms to raise the energy of infeasible solutions that would appear optimal otherwise. We observe that for some problems, Ising solvers spend the majority of computation time exploring this invalid state and often never find a feasible solution. We introduce the encoded Ising model (E-I model), an extension to the Ising model that uses a digital encoding circuit to vastly reduce the proportion of time a solver spends exploring invalid states. We present Fuse, a software framework that enables the description of such functions and automatically lowers them to a p-computer. Our formulation reduces the number of iterations to a solution by a factor of 7.2−52000x7.2-52000 \mathrm{x}7.2−52000x and achieves up to 100.0%\mathbf{1 0 0. 0 \%}100.0% higher estimated success probability over baseline formulations.
Combinatorial optimization problems often arise naturally in various fields of research. However, finding the global optimum solution of these problems remains computationally difficult. Ising spin model is considered to be an effective method to solve combinatorial optimization problems because these problems can be mapped and embedded into the Ising spin model. In general, Ising spin model requires to adjust and tune the spin connection parameters, for example, topology of spin connection and resolution of exchange interaction coefficient values between spins, according to the problems. In this paper, we focus on the number of spin connection, which is one of the spin connection parameters, and perform the calculation experiments through solving max-cut problems with Ising spin computing. As a result, all-to-all connectivity makes Ising spin computing well suited for searching the ground states of complex combinatorial optimization problems.