# Quantum Approximation for Wireless Scheduling
## 4 Quantum Approximate Optimization for Scheduling (QAOS)
### Design of the Problem Hamiltonian
#### 4.1.2 Design of the Constraint Hamiltonian  
In the MWIS-based wireless scheduling problem, a banned event is a case where both adjacent nodes of the conflict graph are scheduled, as shown in _Case C_ of Figure 1. If the weights of \(N_{i}\) and \(N_{j}\) in _Case C_ are defined as \(W_{N_{i}}\) and \(W_{N_{j}}\) respectively; then the constraint function \(C^{\prime}(i,j)\), which counts the banned events, can be represented as follows:  
\[C^{\prime}(i,j)=\sum_{i=1}^{n}\sum_{j=1}^{n}(W_{N_{i}}+W_{N_{j}})\big{|}E_{C}( N_{i},N_{j})\big{|}\text{ where }i>j. \tag{22}\]  
Here, \(n\) is the number of nodes and \(\big{|}E_{C}(N_{i},N_{j})\big{|}\) is the number of \(E_{C}(N_{i},N_{j})\); \(i>j\) is a condition to avoid the duplication of the same edge.  
According to Equations (13)-(17), \(C^{\prime}(i,j)\) can be redefined as \(C(i,j)\) with symbols in Section 3 as follows:  
\[C(i,j) = \sum_{\forall l_{1}\in\mathcal{L}}\sum_{\forall l_{j}\in\mathcal{ L}}(w_{i}+w_{j})\mathcal{E}_{(i,j)}\text{ where }i>j \tag{23}\] \[= \sum_{\forall l_{1}\in\mathcal{L}}\sum_{\forall l_{j}\in\mathcal{ L}}(w_{i}+w_{j})(\mathcal{I}_{i}\wedge\mathcal{I}_{j})\text{ where }i>j.\]  
Here, \(\wedge\) is a Boolean AND operator and \(C(i,j)\), which counts the banned events, must be 0 or the minimum value. Due to quantum Fourier expansion, the AND Boolean function \(B_{2}(x_{1},x_{2})\) can be mapped to the following Boolean Hamiltonian \(H_{B_{2}}\)[25]:  
Figure 1: The number of possible cases when a single edge exists between two nodes in the conflict graph. The scheduled and unscheduled nodes have states \(|1\rangle\) and \(|0\rangle\), respectively. \(N_{i}\) and \(N_{j}\) represent arbitrary nodes, and \(E_{A}(N_{i},N_{j})\), \(E_{B}(N_{i},N_{j})\), and \(E_{C}(N_{i},N_{j})\) represent edges in each case.  
\[B_{2}(x_{1},x_{2}) = x_{1}\wedge x_{2}\text{ where } \tag{24}\] \[x_{1}\in\{0,1\}\text{ and }x_{2}\in\{0,1\},\] \[H_{B_{2}} = \frac{1}{4}(I-Z_{1}-Z_{2}+Z_{1}Z_{2}), \tag{25}\]  
where \(Z_{1}\) and \(Z_{2}\) are the Pauli-\(Z\) operators applying on \(x_{1}\) and \(x_{2}\), respectively.  
According to Equations (24) and (25), the constraint function Equation (23) can be represented as following Hamiltonian:  
\[H_{C^{\prime}}=\sum_{\forall i_{i}\in\mathcal{L}}\sum_{\forall i_{j}\in \mathcal{L}}\frac{1}{4}(w_{i}+w_{j})(I-Z_{i}-Z_{j}+Z_{i}Z_{j})\text{ where }i>j. \tag{26}\]  
Here, \(Z_{i}\) and \(Z_{j}\) are the Pauli-\(Z\) operators applied to \(\mathcal{I}_{i}\) and \(\mathcal{I}_{j}\), respectively. Since \(\mathcal{C}(i,j)\) must be 0 or the minimum value, \(H_{C^{\prime}}\), mapped from \(\mathcal{C}(i,j)\), should be minimized. Therefore, the constraint Hamiltonian \(H_{C}\), which is a simplified form of \(H_{C^{\prime}}\), is as follows:  
\[H_{C}=\sum_{\forall i_{i}\in\mathcal{L}}\sum_{\forall i_{j}\in\mathcal{L}}- \frac{1}{4}(w_{i}+w_{j})(Z_{i}+Z_{j}-Z_{i}Z_{j})\text{ where }i>j. \tag{27}\]  
Based on the definitions of \(H_{O}\) and \(H_{C}\), the problem Hamiltonian \(H_{P}\) can be defined as follows:  
\[H_{P}=H_{O}+\rho H_{C}, \tag{28}\]  
where \(\rho\geq 1\) is the penalty rate, which indicates the rate at which \(H_{C}\) affects \(H_{P}\) compared to \(H_{O}\) in the implementation.