Efficient Ising Model Mapping for Induced Subgraph Isomorphism Problems Using Ising Machines Ising machines have attracted attention as they are expected to solve combinatorial optimization problems at high speed with Ising models corresponding to those problems. An induced subgraph isomorphism problem is one of the decision problems, which determines whether a specific graph structure is included in a whole graph or not. The problem can be represented by equality constraints. By using the penalty functions correspond to the equality constraints, we can utilize an Ising machine to the induced subgraph isomorphism problem. The induced subgraph isomorphism problem can be seen in many practical problems, for example, finding out a particular malicious circuit in a device or particular network structure of chemical bonds in a compound. However, due to the limitation of the number of spin variables in the current Ising machines, reducing the number of spin variables is a major concern. Here, we propose an efficient Ising model mapping method to solve the induced subgraph isomorphism problem by Ising machines. Our proposed method theoretically solves the induced subgraph isomorphism problem. Furthermore, the number of spin variables in the Ising model generated by our proposed method is theoretically smaller than that of the conventional method. Experimental results demonstrate that our proposed method can successfully solve the induced subgraph isomorphism problem using the Isingmodel based simulated annealing.

Mapping Constrained SlotPlacement Problems to Ising Models and its Evaluations by an Ising Machine Ising machines have attracted attention, which is expected to obtain better solutions of various combinatorial optimization problems at high speed by mapping the problems to natural phenomena. A slotplacement problem is one of the combinatorial optimization problems, regarded as a quadratic assignment problem, which relates to the optimal logicblock placement in a digital circuit as well as optimal delivery planning. Here, we propose a mapping to the Ising model for solving a slotplacement problem with additional constraints, called a constrained slotplacement problem, where several item pairs must be placed within a given distance. Since the behavior of Ising machines is stochastic, the obtained solution does not always satisfy the slotplacement constraint, which is different from the conventional methods such as the conventional simulated annealing. To resolve the problem, we propose an interpretation method in which a feasible solution is generated by postprocessing procedures. Using an Ising machine computer, feasible solutions could be obtained up to 50 times faster than the conventional simulated annealing without degrading accuracy for constrained slotplacement problems with 6 x 6 slots and 27 items at the maximum.