# Petri Net Modeling for Ising Model Formulation in Quantum Annealing
## 2 Preliminaries
### Petri Net Fundamentals  
A Petri net \(PN=(P,T,F,\mathbf{M}_{0})\) is a directed bipartite graph \(N=(P,T,F)\) with initial marking \(\mathbf{M}_{0}\)[16]. The bipartite graph has two types of vertex sets: a set of places \(P=\{P_{1},P_{2},\ldots,P_{|P|}\}\) and a set of transitions \(T=\{T_{1},T_{2},\ldots,T_{|T|}\}\). The arc function \(F:(P\times T)\cup(T\times P)\rightarrow\mathbb{N}\) defines the connection from places to transitions, and vice versa, where \(\mathbb{N}\) is the set of natural numbers. The returned values of \(F\) indicate the number of removed tokens from the starting place when \((P\times T)\rightarrow\mathbb{N}\) or the number of generated tokens to the ending place when \((T\times P)\rightarrow\mathbb{N}\) upon the firing of the transition. Instead of an arc function, a matrix representation is often used for the connection. Here, _Pre_ and _Post_ show the incident matrix of size \(|P|\times|T|\) to indicate the connection from places to transitions and from transitions to places, respectively. It should be noted that \(\mathit{Pre}(P_{i},T_{j})=F((P_{i},T_{j}))\) and \(\mathit{Post}(P_{i},T_{j})=F((T_{j},P_{i}))\). Tokens are located in places such that the token distribution on \(P\) represents the status of the modeled system. The vector \(\mathbf{M}_{k}\) of size \(|P|\) represents the number of tokens in each place \(P_{i}\in P\) at step \(k\). In addition, \(\mathbf{M}_{0}\), called the _initial marking_, is the marking at step \(0\), which corresponds to the initial status of the system. Therefore, the Petri net \(PN=(N,\mathbf{M}_{0})\) represents the structure and initial states of the modeled system. The transition \(T_{j}\in T\) is _enabled_ at step \(k\) only when \(M_{k}(P_{i})\geq\mathit{Pre}(P_{i},T_{j})\) for each \(P_{i}\) in \({}^{\bullet}T_{j}\), where \({}^{\bullet}T_{j}\) and \(T_{j}^{\bullet}\) denote the set of input and output places of \(T_{j}\), respectively. Similarly, \({}^{\bullet}P_{i}\) and \(P_{i}^{\bullet}\) are the sets of input and output transitions of \(P_{i}\), respectively. An enabled transition \(T_{j}\) can fire. Firing implies the occurrence of an event in the system. The firing of transition \(T_{j}\) removes \(\mathit{Pre}(P_{i},T_{j})\) tokens from each \(P_{i}\in{}^{\bullet}T_{j}\) and adds \(\mathit{Post}(P_{i},T_{j})\) tokens to each \(P_{i}\in T_{j}^{\bullet}\). Firing changes the token distribution, which indicates the change in status of the system by the corresponding event. The following mathematical form shows the change in status caused by the firing of transitions at step \(k\):  
\[\mathbf{M}_{k+1} =\mathbf{M}_{k}-\mathit{Pre}\cdot\mathbf{X}_{k}+\mathit{Post} \cdot\mathbf{X}_{k}\] \[=\mathbf{M}_{k}+(\mathit{Post}-\mathit{Pre})\cdot\mathbf{X}_{k}, \tag{3}\]where \(\mathbf{X}_{k}\) is a vector of size \(|T|\) showing the number of times each \(T_{j}\) fires at step \(k\), and \(\mathbf{X}_{k}\) is called the _firing count vector_ at step \(k\). For a quantitative analysis of the dynamical behavior of a system, _time_ was introduced to Petri nets [23]. The timing methods can be categorized into three types: firing duration (FD), holding duration (HD), and enabling duration (ED) [23]. The FD assigns time to transitions to represent the firing duration. The HD is referred to as place time Petri nets, where tokens are unavailable for firing for a particular period after being located in the place. In the last method, i.e., the ED, a transition cannot be fired for a given period after being enabled. Although other types can be allowed with our method, this paper focuses on timed Petri nets with the FD. A timed Petri net is a six-tuple \(TPN=(P,T,F,TS,FD,\mathbf{M}_{0})\), where \(TS\) is the set of time values, and \(FD:T\to TS\) is a function that returns the firing duration time of transition \(T_{j}\in T\). In this study, we assume that \(TS=\mathbb{N}\) and is a set of natural numbers. A timestamp is also attached to tokens to record the token generation time.