# Petri Net Modeling for Ising Model Formulation in Quantum Annealing
## 3 Binary Quadratic Nets
### Binary Quadratic Net Examples  
As we describe in Proposition 1, binary quadratic net models are equivalent to the Ising models. We show the binary quadratic net models for well-known graph partitioning and minimum vertex cover problems. These problems are straightforwardly modeled with binary quadratic nets and formulated as marking problems in such nets. **Example 1**. : _Minimum Vertex Cover: For a given undirected graph \(G=(V,E)\), with vertex set \(V\) and edge set \(E\), a vertex cover set satisfies the condition such that every edge in \(E\) is incident on a vertex in the cover set. The problem is to find the minimum vertex cover set. The problem is known as NP-hard [5]._  
_We choose the QUBO model for the problem, where we generate the place set and transition set of the binary quadratic net under the one-to-one correspondence with the vertex set and the edge set, respectively. We express a vertex cover by a marking, where we place a token with a color of 1 to show that the corresponding vertex is in the vertex cover, and where a color of 0 is not in the cover. To satisfy the feasibility of the vertex cover, we need to avoid a token with a color of 0 in both input places of each transition because the situation does not cover the corresponding edge. We formulate the feasibility of the condition corresponding to \(I_{8}^{qubo}\) in Table 1 as follows:_\[H_{\text{constraint}}(\mathbf{M})=\sum_{i<j,\hat{p}_{i}^{\prime}\cap\hat{p}_{j}^{ \prime}\
eq\varnothing}(1-M(\hat{p}_{i}))(1-M(\hat{p}_{j})), \tag{15}\]  
_To minimize the objective function, we attempt to reduce the number of color 1 tokens in \(\mathbf{M}\). Therefore, the following penalty function is suitable because only color 1 tokens increase the penalty._  
\[H_{\text{cost}}(\mathbf{M})=(\sum_{i=1}^{|P|}M(\hat{p}_{i})) \tag{16}\]  
_Based on the superposition principle, we have the total formulation by combining the binary quadratic nets corresponding to (15) and (16):_  
\[H_{\text{total}}(\mathbf{M})=A\cdot H_{\text{constraint}}(\mathbf{M})+B\cdot H _{\text{cost}}(\mathbf{M}) \tag{17}\]  
_where \(H_{\text{constraint}}(\mathbf{M})\) counts the number of transitions, both of which have a 0 color token. In addition, \(H_{\text{cost}}(\mathbf{M})\) denotes the number of places colored with 1 to minimize the vertex cover. Moreover, \(A\) and \(B\) show the parameters for a trade-off between the constraint and the objective function. The formulation is equivalent to the QUIBO model in [6]._  
_Consider the graph shown in Figure 3 as a problem instance of the vertex cover problem. We can formulate the problem instance as a marking problem in the corresponding binary quadratic net in Figure 4. Marking \(\mathbf{M}=(1,0,1,0,0,1,0,1)\) is a feasible solution to the instance._  
Figure 4: Binary Quadratic Net for Vertex Cover Problem Instance shown in Figure 3.  
Figure 3: Example of Undirected Graphs. **Example 2**. : _Graph Partitioning: Graph partitioning is an optimization problem, which is explained as follows: Let us consider an undirected graph \(G=(V,E)\) with vertex set \(V\) and edge set \(E\), where \(|V|\) is the number of vertices. The problem is partitioning \(V\) into two subsets whose sizes are equal to \(|V|/2\), minimizing the number of edges between the subsets. The problem is known as NP-hard [5]._  
_We reduce the problem to a marking problem in binary quadratic nets, where each vertex in the given graph corresponds to a place in the binary quadratic net, and the marking such that \(M(\hat{p}_{i})\in\{-1,+1\},\forall\hat{p}_{i}\in\hat{P}\) shows the partition. The objective function minimizes the number of edges connecting the two partitioned groups. The transitions have a one-to-one correspondence with the edges. To minimize the objective function, we want to reduce the different color tokens in pairs of places that share the output transition.