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

Ising formulations of some graph-theoretic problems in psychological research: models and methods

Michael J. Brusco, Clintin P. Davis‐Stober, Douglas Steinley

Published Sep 1, 2020• 1 citation
Publisher

Abstract

It is well known that many NP-hard and NP-complete graph-theoretic problems can be formulated and solved as Ising spin models. We discuss several problems that have a particular history in mathematical psychology, most notably max-cut clustering, graph coloring, a linear ordering problem related to paired comparison ranking and directed acyclic graphs, and the problem of finding a minimum subset of points necessary to contain another point within a convex hull. New Ising spin models are presented for the latter two problems. In addition, we provide MATLAB software programs for obtaining solutions via enumeration of all spin ensembles (when computationally feasible) and simulated annealing. Although we are not advocating that the Ising spin model is the preferred approach for formulation and solution of graph-theoretic problems on conventional digital computers, it does provide a unifying framework for these problems. Moreover, recent progress in the development of quantum computing architecture has shown that Ising spin models can afford enormous improvements in algorithm efficiency when implemented on these platforms, which may ultimately lead to widespread use of the methodology in the future.

DOI
10.31234/osf.io/4udfw

Related papers

Quantum-Assisted Graph Clustering and Quadratic Unconstrained D-ary Optimisation

Sayantan Pramanik, M Girish Chandra

Of late, we are witnessing spectacular developments in Quantum Information Processing with the availability of Noisy Intermediate-Scale Quantum devices of different architectures and various software development kits to work on quantum algorithms. Different problems, which are hard to solve by classical computation, but can be sped up (significantly in some cases) are also being populated. Leveraging these aspects, this paper examines unsupervised graph clustering by quantum algorithms or, more precisely, quantum-assisted algorithms. By carefully examining the two cluster Max-Cut problem within the framework of quantum Ising model, an extension has been worked out for max 3-cut with the identification of an appropriate Hamiltonian. Representative results, after carrying out extensive numerical evaluations, have been provided including a suggestion for possible futuristic implementation with qutrit devices. Further, extrapolation to more than 3 classes, which can be handled by qudits, of both annealer and gate-circuit varieties, has also been touched upon with some preliminary observations; quantum-assisted solving of Quadratic Unconstrained D-ary Optimisation is arrived at within this context. As an additional novelty, a qudit circuit to solve max-d cut through Quantum Approximate Optimization algorithm is systematically constructed.

arXiv:2004.02608•Apr 3, 2020•4 citations

On connection among quantum-inspired algorithms of the Ising model

Bowen Liu, Kaizhi Wang, Dongmei Xiao +1 more

Various combinatorial optimization NP-hard problems can be reduced to finding the minimizer of an Ising model, which is a discrete mathematical model. It is an intellectual challenge to develop some mathematical tools or algorithms for solving the Ising model. Over the past decades, some continuous approaches or algorithms have been proposed from physical, mathematical or computational views for optimizing the Ising model such as quantum annealing, the coherent Ising machine, simulated annealing, adiabatic Hamiltonian systems, etc.. However, the mathematical principle of these algorithms is far from being understood. In this paper, we reveal the mathematical mechanism of dynamical system algorithms for the Ising model by Morse theory and variational methods. We prove that the dynamical system algorithms can be designed to minimize a continuous function whose local minimum points give all the candidates of the Ising model and the global minimum gives the minimizer of Ising problem. Using this mathematical mechanism, we can easily understand several dynamical system algorithms of the Ising model such as the coherent Ising machine, the Kerr-nonlinear parametric oscillators and the simulated bifurcation algorithm. Furthermore, motivated by the works of C. Conley, we study transit and capture properties of the simulated bifurcation algorithm to explain its convergence by the low energy transit and capture in celestial mechanics. A detailed discussion on $2$-spin and $3$-spin Ising models is presented as application.

arXiv:2012.01156•Communications in Mathematical Sciences•Jan 1, 2023•2 citations

Approximation Meets Quantum: A Parameterized Framework for Large-Scale Graph Coloring

Rahul Pitale, Kapil Tajane, Prashant Ahire +4 more

Graph coloring is a well-known combinatorial optimization problem with broad applications in network security, scheduling, and register allocation. Being an NP-hard problem, exact solutions for large instances are computationally infeasible, calling for other solution strategies. In this study, parameterized and approximation methods to tackle the graph coloring problem are investigated. While approximation algorithms yield near-optimal solutions with theoretical guarantees of performance that are well-suited for large-scale applications, parameterized algorithms utilize graph-specific structural properties to manage constrained instances efficiently. We examine the trade-offs in these approaches, highlighting their strengths and weaknesses. In addition, we introduce a hybrid approach that combines both parameterized and approximation methods to best optimize computational resources and balance accuracy versus feasibility. Furthermore, we discuss the newly realized potential of quantum computing—specifically quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA)—to speed up graph coloring by leveraging quantum parallelism and state superposition. Such quantum-based techniques represent a promising line of attack for breaking up large and hard instances that overwhelm classical approaches. Future research will aim to tighten approximation guarantees, create quantum-augmented hybrid models, and test theoretical results against real-world datasets.

Asian Conference on Innovation in Technology (ASIANCON)•Aug 22, 2025•0 citations

Efficient Ising Model Mapping to Solving Slot Placement Problem

Sho Kanamaru, Daisuke Oku, Masashi Tawada +5 more

Ising model-based computation has attracted attention as it can obtain better solutions of various combinatorial optimization problems at high speed by mapping the problems to natural phenomena. A slot placement problem is one of the combinatorial optimization problems which plays an important role in the optimal logic-block placement as well as optimal delivery decisions but it is known as an NP-hard problem. Solving it efficiently is one of the largest challenges. In this paper, we propose an efficient Ising model mapping to solve the slot placement problem and an interpretation method for the obtained Ising solutions to satisfy the slot-placement constraints. First, we propose slot-placement constraint terms that minimize the energy function or Hamiltonian of the Ising model when satisfying the slot-placement constraints. Secondly, we propose an objective function term in the energy function that minimizes the total weighted wiring length between items to be placed to the slots. In Ising model-based computations, the final spin states cannot necessarily satisfy the slot-placement constraints, which gives one of the largest differences from the conventional computations. Hence we newly propose an interpretation method for the obtained Ising solutions to satisfy the slot-placement constraints. On a fully-connected annealing machine, we could obtain feasible solutions with almost the same accuracy as the simulated annealing for slot placement problem with two orders of magnitude faster.

International Conference on Consumer Electronics•Jan 1, 2019•15 citations

Graph Theoretic Algorithms Adaptable to Quantum Computing

Siddhartha Srivastava

Computational methods are rapidly emerging as an essential tool for understanding and solving complex engineering problems, which complement the traditional tools of experimentation and theory. When considered in a discrete computational setting, many engineering problems can be reduced to a graph coloring problem. Examples range from systems design, airline scheduling, image segmentation to pattern recognition, where energy cost functions with discrete variables are extremized. However, using discrete variables over continuous variables introduces some complications when defining differential quantities, such as gradients and Hessians involved in scientific computations within solid and fluid mechanics. Consequently, graph techniques are under-utilized in this important domain. However, we have recently witnessed great developments in quantum computing where physical devices can solve discrete optimization problems faster than most well-known classical algorithms. This warrants further investigation into the re-formulation of scientific computation problems into graph-theoretic problems, thus enabling rapid engineering simulations in a soon-to-be quantum computing world. The computational techniques developed in this thesis allow the representation of surface scalars, such as perimeter and area, using discrete variables in a graph. Results from integral geometry, specifically Cauchy-Crofton relations, are used to estimate these scalars via submodular functions. With this framework, several quantities important to engineering applications can be represented in graph-based algorithms. These include the surface energy of cracks for fracture prediction, grain boundary energy to model microstructure evolution, and surface area estimates (of grains and fibers) for generating conformal meshes. Combinatorial optimization problems for these applications are presented first. The last two chapters describe two new graph coloring algorithms implemented on a physical quantum computing device: the D-wave quantum annealer. The first algorithm describes a functional minimization approach to solve differential equations. The second algorithm describes a realization of the Boltzmann machine learning algorithm on a quantum annealer. The latter allows generative and discriminative learning of data, which has vast applications in many fields. Theoretical aspects and the implementation of these problems are outlined with a focus on engineering applications.

•Jan 1, 2021•1 citation

Ising formulations of many NP problems

Andrew Lucas

We provide Ising formulations for many NP-complete and NP-hard problems, including all of Karp's 21 NP-complete problems. This collects and extends mappings to the Ising model from partitioning, covering and satisfiability. In each case, the required number of spins is at most cubic in the size of the problem. This work may be useful in designing adiabatic quantum optimization algorithms.

arXiv:1302.5843•Frontiers in Physics•Jan 1, 2014•2,511 citations
It is well known that many NP-hard and NP-complete graph-theoretic problems can be formulated and solved as Ising spin models. We discuss several problems that have a particular history in mathematical psychology, most notably max-cut clustering, graph coloring, a linear ordering problem related to paired comparison ranking and directed acyclic graphs, and the problem of finding a minimum subset of points necessary to contain another point within a convex hull. New Ising spin models are presented for the latter two problems. In addition, we provide MATLAB software programs for obtaining solutions via enumeration of all spin ensembles (when computationally feasible) and simulated annealing. Although we are not advocating that the Ising spin model is the preferred approach for formulation and solution of graph-theoretic problems on conventional digital computers, it does provide a unifying framework for these problems. Moreover, recent progress in the development of quantum computing architecture has shown that Ising spin models can afford enormous improvements in algorithm efficiency when implemented on these platforms, which may ultimately lead to widespread use of the methodology in the future.
Of late, we are witnessing spectacular developments in Quantum Information Processing with the availability of Noisy Intermediate-Scale Quantum devices of different architectures and various software development kits to work on quantum algorithms. Different problems, which are hard to solve by classical computation, but can be sped up (significantly in some cases) are also being populated. Leveraging these aspects, this paper examines unsupervised graph clustering by quantum algorithms or, more precisely, quantum-assisted algorithms. By carefully examining the two cluster Max-Cut problem within the framework of quantum Ising model, an extension has been worked out for max 3-cut with the identification of an appropriate Hamiltonian. Representative results, after carrying out extensive numerical evaluations, have been provided including a suggestion for possible futuristic implementation with qutrit devices. Further, extrapolation to more than 3 classes, which can be handled by qudits, of both annealer and gate-circuit varieties, has also been touched upon with some preliminary observations; quantum-assisted solving of Quadratic Unconstrained D-ary Optimisation is arrived at within this context. As an additional novelty, a qudit circuit to solve max-d cut through Quantum Approximate Optimization algorithm is systematically constructed.
Various combinatorial optimization NP-hard problems can be reduced to finding the minimizer of an Ising model, which is a discrete mathematical model. It is an intellectual challenge to develop some mathematical tools or algorithms for solving the Ising model. Over the past decades, some continuous approaches or algorithms have been proposed from physical, mathematical or computational views for optimizing the Ising model such as quantum annealing, the coherent Ising machine, simulated annealing, adiabatic Hamiltonian systems, etc.. However, the mathematical principle of these algorithms is far from being understood. In this paper, we reveal the mathematical mechanism of dynamical system algorithms for the Ising model by Morse theory and variational methods. We prove that the dynamical system algorithms can be designed to minimize a continuous function whose local minimum points give all the candidates of the Ising model and the global minimum gives the minimizer of Ising problem. Using this mathematical mechanism, we can easily understand several dynamical system algorithms of the Ising model such as the coherent Ising machine, the Kerr-nonlinear parametric oscillators and the simulated bifurcation algorithm. Furthermore, motivated by the works of C. Conley, we study transit and capture properties of the simulated bifurcation algorithm to explain its convergence by the low energy transit and capture in celestial mechanics. A detailed discussion on 222-spin and 333-spin Ising models is presented as application.
Graph coloring is a well-known combinatorial optimization problem with broad applications in network security, scheduling, and register allocation. Being an NP-hard problem, exact solutions for large instances are computationally infeasible, calling for other solution strategies. In this study, parameterized and approximation methods to tackle the graph coloring problem are investigated. While approximation algorithms yield near-optimal solutions with theoretical guarantees of performance that are well-suited for large-scale applications, parameterized algorithms utilize graph-specific structural properties to manage constrained instances efficiently. We examine the trade-offs in these approaches, highlighting their strengths and weaknesses. In addition, we introduce a hybrid approach that combines both parameterized and approximation methods to best optimize computational resources and balance accuracy versus feasibility. Furthermore, we discuss the newly realized potential of quantum computing—specifically quantum annealing and the Quantum Approximate Optimization Algorithm (QAOA)—to speed up graph coloring by leveraging quantum parallelism and state superposition. Such quantum-based techniques represent a promising line of attack for breaking up large and hard instances that overwhelm classical approaches. Future research will aim to tighten approximation guarantees, create quantum-augmented hybrid models, and test theoretical results against real-world datasets.
Ising model-based computation has attracted attention as it can obtain better solutions of various combinatorial optimization problems at high speed by mapping the problems to natural phenomena. A slot placement problem is one of the combinatorial optimization problems which plays an important role in the optimal logic-block placement as well as optimal delivery decisions but it is known as an NP-hard problem. Solving it efficiently is one of the largest challenges. In this paper, we propose an efficient Ising model mapping to solve the slot placement problem and an interpretation method for the obtained Ising solutions to satisfy the slot-placement constraints. First, we propose slot-placement constraint terms that minimize the energy function or Hamiltonian of the Ising model when satisfying the slot-placement constraints. Secondly, we propose an objective function term in the energy function that minimizes the total weighted wiring length between items to be placed to the slots. In Ising model-based computations, the final spin states cannot necessarily satisfy the slot-placement constraints, which gives one of the largest differences from the conventional computations. Hence we newly propose an interpretation method for the obtained Ising solutions to satisfy the slot-placement constraints. On a fully-connected annealing machine, we could obtain feasible solutions with almost the same accuracy as the simulated annealing for slot placement problem with two orders of magnitude faster.
Computational methods are rapidly emerging as an essential tool for understanding and solving complex engineering problems, which complement the traditional tools of experimentation and theory. When considered in a discrete computational setting, many engineering problems can be reduced to a graph coloring problem. Examples range from systems design, airline scheduling, image segmentation to pattern recognition, where energy cost functions with discrete variables are extremized. However, using discrete variables over continuous variables introduces some complications when defining differential quantities, such as gradients and Hessians involved in scientific computations within solid and fluid mechanics. Consequently, graph techniques are under-utilized in this important domain. However, we have recently witnessed great developments in quantum computing where physical devices can solve discrete optimization problems faster than most well-known classical algorithms. This warrants further investigation into the re-formulation of scientific computation problems into graph-theoretic problems, thus enabling rapid engineering simulations in a soon-to-be quantum computing world. The computational techniques developed in this thesis allow the representation of surface scalars, such as perimeter and area, using discrete variables in a graph. Results from integral geometry, specifically Cauchy-Crofton relations, are used to estimate these scalars via submodular functions. With this framework, several quantities important to engineering applications can be represented in graph-based algorithms. These include the surface energy of cracks for fracture prediction, grain boundary energy to model microstructure evolution, and surface area estimates (of grains and fibers) for generating conformal meshes. Combinatorial optimization problems for these applications are presented first. The last two chapters describe two new graph coloring algorithms implemented on a physical quantum computing device: the D-wave quantum annealer. The first algorithm describes a functional minimization approach to solve differential equations. The second algorithm describes a realization of the Boltzmann machine learning algorithm on a quantum annealer. The latter allows generative and discriminative learning of data, which has vast applications in many fields. Theoretical aspects and the implementation of these problems are outlined with a focus on engineering applications.