# Petri Net Modeling for Ising Model Formulation in Quantum Annealing
## 1 Introduction  
Quantum annealing is a metaheuristic for combinatorial optimization in quantum mechanics research [1, 2]. This new approach solves unconstrained optimization problems formulated as a Hamiltonian by evolving the time-dependent Schrodinger equation from a quantum mechanical superposition of all possible states to its ground state in physical systems [3]. A quantum annealing machine is a special-purpose quantum computer that solves combinatorial optimization problems. D-wave is the first commercial quantum annealing machine [4]. Combinatorial optimization contributes to a more effective and reasonable life by minimizing the total costs or maximizing the benefits under certain constraints. Although sophisticated solvers can efficiently solve small problems, many practical problems are computationally intractable. Such problems are formally characterized as NP-hard; that is, there are no polynomial-time algorithms to solve the problems. Many researchers in computer science and operations research believe that there are no polynomial-time algorithms for NP-hard problems and continue to develop efficient heuristic algorithms to solve larger problems [5]. Quantum annealing is a metaheuristic that does not restrict the target problems. Thus far, some combinatorial optimization problems, but not many, have been formulated as Ising or Quadratic Unconstrained Binary Optimization (QUBO) models and solved using annealing machines [6, 7, 8, 9]. Theoretical and experimental studies have contributed to improving the performance of annealing processes [10, 11, 12, 13]. Useful software tools have been developed to utilize quantum annealing machines [14]. Digital implementations of the quantum annealing process have also emerged because this new optimization technique has the potential to outperform traditional meta-heuristic algorithms. A graphics processingunit (GPU) based quantum annealing simulator has shown high-performance optimization by utilizing spatial and temporal parallelism during the annealing process [15]. Therefore, we have high hopes for this new innovative optimizer. However, obstacles to quantum annealing usability include the hardness of the parameter tuning and formulation of the target problems as Ising or QUBO models. The constraints of the original problem and objective functions are represented as a penalty function, minimized as an unconstrained optimization problem. Search processes can reach infeasible solutions, and to avoid such situations, it is necessary to carefully tune the parameters in pre-performing annealing process. The difficulty of the Ising model formulation is also an essential obstacle to the usability of quantum annealing. The new annealer requires users to create quadratic penalty functions, Ising, or QUBO models, for target optimization problems. This study focuses solely on the latter problem, which is the difficulty of formulating the Ising and QUBO models. To overcome this problem, we propose a method for generating Ising or QUBO models from Petri net models representing the target optimization problems. Our proposal is a Petri net modeling approach in which, once we model the optimization problem with Petri nets, we can systematically obtain the Ising or QUBO formulation. A Petri net is a mathematical and graphical modeling language for various systems, such as computer networks, manufacturing systems, transportation networks, biological systems, agricultural production processes, and other applications [16; 17]. We only need the domain knowledge of the target systems for modeling because the rules and components of Petri nets are simple and intuitive. Petri net modeling is quite efficient for representing integer linear programming problems because Petri nets have mathematical forms, denoted as linear expressions [18]. The authors proposed an algorithm for generating mixed-integer linear programming (MILP) based on Petri net models for practical scheduling and optimal resource assignment problems [19; 20].