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:2211.05365

Constructing Dynamical Systems to Model Higher Order Ising Spin Interactions and their Application in Solving Combinatorial Optimization Problems

Mohammad Khairul Bashar, Nikhil Shukla

Published Nov 10, 2022• 1 citation
arXivHTMLPDF

Abstract

The Ising model provides a natural mapping for many computationally hard combinatorial optimization problems (COPs). Consequently, dynamical system-inspired computing models and hardware platforms that minimize the Ising Hamiltonian, have recently been proposed as a potential candidate for solving COPs, with the promise of significant performance benefit. However, the Ising model, and consequently, the corresponding dynamical system-based computational models primarily consider quadratic interactions among the nodes. Computational models considering higher order interactions among Ising spins remain largely unexplored. Therefore, in this work, we propose dynamical-system-based computational models to consider higher order (>2) interactions among the Ising spins, which subsequently, enables us to propose computational models to directly solve many COPs that entail such higher order interactions (COPs on hypergraphs). Specifically, we demonstrate our approach by developing dynamical systems to compute the solution for the Boolean NAE-K-SAT (K is greater than 3) problem as well as solve the Max-K-Cut of a hypergraph. Our work advances the potential of the physics-inspired 'toolbox' for solving COPs.

DOI
10.48550/arxiv.2211.05365

Related papers

Dynamical System-Based Computational Models for Solving Combinatorial Optimization on Hypergraphs

Mohammad Khairul Bashar, Antik Mallick, Avik W. Ghosh +1 more

The intrinsic energy minimization in dynamical systems offers a valuable tool for minimizing the objective functions of computationally challenging problems in combinatorial optimization. However, most prior works have focused on mapping such dynamics to combinatorial optimization problems whose objective functions have quadratic degree (e.g., MaxCut); such problems can be represented and analyzed using graphs. However, the work on developing such models for problems that need objective functions with degree greater than two, and subsequently, entail the use of hypergraph data structures, is relatively sparse. In this work, we develop dynamical system-inspired computational models for several such problems. Specifically, we define the ‘energy function’ for hypergraph-based combinatorial problems ranging from Boolean SAT and its variants to integer factorization, and subsequently, define the resulting system dynamics. We also show that the design approach is applicable to optimization problems with quadratic degree, and use it develop a new dynamical system formulation for minimizing the Ising Hamiltonian. Our work not only expands on the scope of problems that can be directly mapped to, and solved using physics-inspired models, but also creates new opportunities to design high-performance accelerators for solving combinatorial optimization.

arXiv:2207.09618•IEEE Journal on Exploratory Solid-State Computational Devices and Circuits•Jan 9, 2023•5 citations

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

Solving the MAX-$k$-CUT problem for hypergraphs with quantum computing

V. S. Yarmus, Kh. P. Gnatenko

We investigate the MAX-$k$-CUT problem on hypergraphs by considering their representation as spin systems with Ising interactions. The corresponding cost Hamiltonian for MAX-$k$-CUT problem on hypergraphs is reduced to an Ising Hamiltonian with pairwise interactions. This reduction simplifies the solution of the MAX-$k$-CUT problem using quantum computing. As illustrative examples, a 3-uniform tight-star hypergraph and a sunflower hypergraph are considered. The corresponding Hamiltonians are constructed, and quantum protocols for the MAX-$k$-CUT problems are presented. The MAX-3-CUT and MAX-4-CUT instances are investigated for these hypergraphs by varying the number of Quantum Approximate Optimization Algorithm (QAOA) layers from (p=2) to (p=15) with quantum computing on IBM's Qiskit AerSimulator.

quant-pharXiv:2610.41678•Nov 2, 2026

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.

Communications Physics•Aug 5, 2026•0 citations

A reduction scheme for general-order Ising-like Hamiltonians in quantum heuristic solvers

Chengsi Mao, Pavel Mosharev, Yao Wang +1 more

The Ising model is ubiquitous in various optimization problems but notoriously difficult to solve due to combinatorial explosion. In view of this, Hamiltonian reduction is a useful preprocessing technique for reducing the effective problem size before applying heuristic solvers. However, existing reduction techniques mainly target second-order Ising models, whereas many pseudo-Boolean formulations naturally contain higher-order interactions. In this work, we generalize the concept of non-separable groups to arbitrary-order Ising-like models and develop a Hamiltonian reduction framework that iteratively detects and merges constrained spin groups into single variables. We benchmark the reduction on synthetic hypergraphs and higher-order network datasets, and evaluate its integration with downstream order-reduction and solver workflows. Our results establish a foundation for Hamiltonian reduction in higher-order Ising-like optimization problems.

quant-pharXiv:2607.19871•Quantum Information Processing•Jul 23, 2026•0 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
The Ising model provides a natural mapping for many computationally hard combinatorial optimization problems (COPs). Consequently, dynamical system-inspired computing models and hardware platforms that minimize the Ising Hamiltonian, have recently been proposed as a potential candidate for solving COPs, with the promise of significant performance benefit. However, the Ising model, and consequently, the corresponding dynamical system-based computational models primarily consider quadratic interactions among the nodes. Computational models considering higher order interactions among Ising spins remain largely unexplored. Therefore, in this work, we propose dynamical-system-based computational models to consider higher order (>2) interactions among the Ising spins, which subsequently, enables us to propose computational models to directly solve many COPs that entail such higher order interactions (COPs on hypergraphs). Specifically, we demonstrate our approach by developing dynamical systems to compute the solution for the Boolean NAE-K-SAT (K is greater than 3) problem as well as solve the Max-K-Cut of a hypergraph. Our work advances the potential of the physics-inspired 'toolbox' for solving COPs.
The intrinsic energy minimization in dynamical systems offers a valuable tool for minimizing the objective functions of computationally challenging problems in combinatorial optimization. However, most prior works have focused on mapping such dynamics to combinatorial optimization problems whose objective functions have quadratic degree (e.g., MaxCut); such problems can be represented and analyzed using graphs. However, the work on developing such models for problems that need objective functions with degree greater than two, and subsequently, entail the use of hypergraph data structures, is relatively sparse. In this work, we develop dynamical system-inspired computational models for several such problems. Specifically, we define the ‘energy function’ for hypergraph-based combinatorial problems ranging from Boolean SAT and its variants to integer factorization, and subsequently, define the resulting system dynamics. We also show that the design approach is applicable to optimization problems with quadratic degree, and use it develop a new dynamical system formulation for minimizing the Ising Hamiltonian. Our work not only expands on the scope of problems that can be directly mapped to, and solved using physics-inspired models, but also creates new opportunities to design high-performance accelerators for solving combinatorial optimization.
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.
Solving the MAX-kkk-CUT problem for hypergraphs with quantum computing
We investigate the MAX-kkk-CUT problem on hypergraphs by considering their representation as spin systems with Ising interactions. The corresponding cost Hamiltonian for MAX-kkk-CUT problem on hypergraphs is reduced to an Ising Hamiltonian with pairwise interactions. This reduction simplifies the solution of the MAX-kkk-CUT problem using quantum computing. As illustrative examples, a 3-uniform tight-star hypergraph and a sunflower hypergraph are considered. The corresponding Hamiltonians are constructed, and quantum protocols for the MAX-kkk-CUT problems are presented. The MAX-3-CUT and MAX-4-CUT instances are investigated for these hypergraphs by varying the number of Quantum Approximate Optimization Algorithm (QAOA) layers from (p=2) to (p=15) with quantum computing on IBM's Qiskit AerSimulator.
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.
The Ising model is ubiquitous in various optimization problems but notoriously difficult to solve due to combinatorial explosion. In view of this, Hamiltonian reduction is a useful preprocessing technique for reducing the effective problem size before applying heuristic solvers. However, existing reduction techniques mainly target second-order Ising models, whereas many pseudo-Boolean formulations naturally contain higher-order interactions. In this work, we generalize the concept of non-separable groups to arbitrary-order Ising-like models and develop a Hamiltonian reduction framework that iteratively detects and merges constrained spin groups into single variables. We benchmark the reduction on synthetic hypergraphs and higher-order network datasets, and evaluate its integration with downstream order-reduction and solver workflows. Our results establish a foundation for Hamiltonian reduction in higher-order Ising-like optimization problems.
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.