# Petri Net Modeling for Ising Model Formulation in Quantum Annealing
## 3 Binary Quadratic Nets
### Formal Definition  
**Definition 1**. : _(Binary Quadratic Net) A binary quadratic net is a colored Petri net denoted by \(BQN=(\hat{\Sigma},\hat{P},\hat{T},\hat{F},\hat{C},\hat{w})\):_  
\[\Sigma \in\{\{-1,+1\},\{0,1\}\} \tag{6}\] \[\hat{P} =\{\hat{p}_{1},\hat{p}_{2},...,\hat{p}_{n}\}\] (7) \[\hat{T} =\{\hat{t}_{i,j}\mid\hat{p}_{i},\hat{p}_{j}\in\hat{P},\{\hat{p}_{i },\hat{p}_{j}\}=\hat{t}^{\bullet}_{i,j}=\hat{t}^{\bullet}_{i,j},i<j\}\] (8) \[\hat{F} :(\hat{P}\times\hat{T})\cup(\hat{T}\times\hat{P})\rightarrow \begin{cases} 1&\text{if }(\hat{p}_{i},\hat{t}_{i,j})\text{ and }(\hat{t}_{i,j},\hat{p}_{j}),\hat{t}_{i,j}\in\hat{T}\\ 0&\text{otherwise}\end{cases} \] (9) \[\hat{C}(\hat{p})\in\hat{\Sigma},\forall\hat{p}\in\hat{P}\] (10) \[\hat{w} :\hat{P}\cup\hat{T}\rightarrow\mathbb{R} \tag{11}\]  
There is one token in each place, where a place corresponds to a spin variable in the Ising models and a binary variable in the QUBO models, respectively. For simplicity, we denote the value of a variable associated with place \(\hat{p}_{i}\) by \(M(\hat{p}_{i})\), that is, \(M(\hat{p}_{i})\in\{-1,+1\}\) in the Ising models or \(M(\hat{p}_{i})\in\{0,1\}\) in the QUBO models. Note that in the QUBO model, \(M(\hat{p}_{i})=0\) indicates that the place \(\hat{p}_{i}\) includes a token with color 0. Current quantum annealing platforms have various physical topologies, chimera graphs for D-waves, and three-dimensional lattices for CMOS annealers [25]. Thus, we need to embed the logical Ising model to a specific graph topology to run the annealing process. However, we do not treat the embedding process in this study because we can use existing embedding algorithms for each platform. Moreover, Fujitsu Digital Annealer allows fully connected topologies. For reference, Figure 2 depicts the binary quadratic net model for the 2D array Ising model shown in Figure 1.  
Figure 2: Binary Quadratic Net for 2D-Array Ising Model shown in Figure 1.  
To combine binary quadratic nets and Ising models, we introduce a measure to represent the state of binary quadratic nets with a marking \(\mathbf{M}\). We define this as an energy function of binary quadratic nets corresponding to the Hamiltonian in the Ising models. **Definition 2**. : _(Energy Function of Binary Quadratic Net) For a binary quadratic net \(BQN=(\hat{\mathbf{\Sigma}},\hat{P},\hat{T},\hat{F},\hat{C},\hat{w})\) with a marking \(\mathbf{M}\), the energy function is defined as follows:_  
\[H_{BQN}(\mathbf{M})=\sum_{\hat{p}_{i}\in\hat{P}}w(\hat{p}_{i})M(\hat{p}_{i})+ \sum_{\hat{t}_{i,j}\in\hat{T}}w(\hat{t}_{i,j})M(\hat{p}_{i})M(\hat{p}_{j}). \tag{12}\]  
The first summed terms show the energy derived from token existence at each place. The second summed term represents the energy from the interaction between tokens on both sides of each transition. The weight parameters \(w(\hat{p}_{i})\) and \(w(\hat{t}_{i,j})\) are defined for \(\hat{p}_{i}\) and \(\hat{t}_{i,j}\), respectively. The energy function in Definition 2 is equivalent to the Ising model shown in Equation (1), and the energy function is uniquely defined from the corresponding binary quadratic net. Although it is straightforward, we simply summarize this fact as a proposition for the readability of the remaining parts. **Proposition 1**. : _For an Ising model, we have an equivalent binary quadratic net \(BQN\) in the sense that the energy function \(H_{BQN}(\mathbf{M})\) is equivalent to the Hamiltonian of the Ising model._  
In our binary quadratic nets, transitions represent interactive relations between tokens on both sides. There may be numerous interaction types. We choose interaction types carefully depending on the target optimization problems. In the Appendix, we summarize the primitive interaction for QUBO and the Ising model, respectively. Table 1 shows the interaction primitives \(I_{i}^{qubo},i=0,1,\ldots,15\), for two binary variables in \(\{0,1\}\), where \((0,0),(0,1),(1,0)\), and \((1,1)\) express all possible combinations of the two binary variables.