The new formulation of ising problem

Jaka Strajn

Morikazu Nakamura, Kohei Kaneshima, Takeo Yoshida

Quantum annealing is an emerging new platform for combinatorial optimization, requiring an Ising model formulation for optimization problems. The formulation can be an essential obstacle to the permeation of this innovation into broad areas of everyday life. Our research is aimed at the proposal of a Petri net modeling approach for an Ising model formulation. Although the proposed method requires users to model their optimization problems with Petri nets, this process can be carried out in a relatively straightforward manner if we know the target problem and the simple Petri net modeling rules. With our method, the constraints and objective functions in the target optimization problems are represented as fundamental characteristics of Petri net models, extracted systematically from Petri net models, and then converted into binary quadratic nets, equivalent to Ising models. The proposed method can drastically reduce the difficulty of the Ising model formulation.

Shohei Mori, Satoshi Nishimura

We propose a novel algorithm for finding a similar region in images using Ising machines, which are a new type of non-von Neumann computers that specialize in solving combinatorial optimization problems. Applications of Ising machine are expected to be promising in diverse fields such as media processing and delivery. To leverage Ising machine-based approaches, a problem must be formulated in a quadratic unconstrained binary optimization (QUBO) form. In this study, to unleash the potentials of Ising machines in image processing, we present a method for formulating a similar region search as a QUBO problem. Experiments show that the QUBO-based algorithm realizes the detection of similar regions in accordance with policies for the similarity between images and the clumpiness of detected regions.

F. Mancini

Huey Wen Huang

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

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.