# Quantum Computing Approaches for Mission Covering Optimization
## 4 Algorithm Implementation
### Scenario 2 (Two Constraints)
#### 4.2.2 Qaoah  
For this scenario, it is more challenging to construct the mixing Hamiltonian to describe how to move in the constrained space in QAOA. Unlike the Lagrange multiplier's case, it is not easy to linearly combine two constraint encodings to obtain the final constraint Hamiltonian. In other words, one cannot add \(H_{m1}+H_{m2}\) to obtain \(H_{m1+m2}\), where \(H_{m1}\)\(H_{m2}\), \(H_{m1 amdm2}\) are mixing Hamiltonian's representing 1 st, 2 nd and 1 st and 2 nd constraints, respectively. This scenario presents two challenges:  
1. If a mixing operator allowed a resource in \(\mathbf{R}_{1}\) to move from an unallocated state to an allocated state by pairing it with a mission, then it must also move a resource from \(\mathbf{R}_{2}\) to the same mission. 2. The mixing operator must operate such that it is possible after multiple applications to visit every classical state from the starting quantum state. These two obstacles require a slightly different mixing operator and more qubits. The strategy for creating a two-constraint mixing operator is to reallocate resources in pairs--one from \(\mathbf{R}_{1}\) and one from \(\mathbf{R}_{2}\). These pairs will always move together. However, the problem is that not every possible classical state can be produced from the mixing. For example, let us say that there are resources \(\mathbf{R}_{1}=\{1,2,3,4\}\) and \(\mathbf{R}_{2}=\{5,6,7,8\}\). If resource 1 and resource 5 move together, then it is never possible to see resource 2 just be paired with resource 5 without also being paired with 1. A way to resolve this problem is to introduce an additional mixing operator to swap entire columns within just \(\mathbf{R}_{1}\) or \(\mathbf{R}_{2}\) resources. However, every time columns are swapped, the classical state must remember what mappings are paired with others so that if another reallocation is performed, the buddy constraint will not be violated. For this reason, new qubits are introduced to each column. These qubits represent the pair ID that is present in the columns for resources in \(\mathbf{R}_{1}\) and \(\mathbf{R}_{2}\). Resources with the same ID are reallocated together. When columns are swapped, the pair IDs of the columns are also swapped. Consider an MCO with three missions (plus the unallocated mission) and eight resources evenly split between \(\mathbf{R}_{1}\) and \(\mathbf{R}_{2}\). Our initialized state is shown in Figure 4(a). Each column has two extra ID qubits (lowest two rows) with a unique bit-encoding that matches another column from the opposite qualification type. This means that these columns are paired together. For example, consider the case where the mixer operation reallocates resource 2 from the unallocated mission to mission 2. Since this column has an ID of \({}^{\text{-}}10_{\text{b}}\)' (top ID qubit true, bottom one false), it is paired with resource 6 because it has the same ID. In order to respect this pairing, both resource 2 and 6 are swapped together using a dual swap gate C-DSWAP, as shown in Figure 4(b). Consider the situation when the mixing operator performs a column swap between columns 2 and 4 (see Figure 4(c)). Note that the IDs of these columns are also swapped. If the mixer chooses to move resource 6 back to the unallocated state, it also would move resource 4 into the unallocated state since they have the same ID. This can be ensured if the mixer uses the dual swap operation once again (see Figure 4(d)). The added qubits to represent the IDs of each of the columns are notated as \(\ket{\text{ID}}\) and defined as:  
\[\ket{\text{ID}}=\bigotimes_{j_{1}=0}^{\text{ID}_{\text{max}}}\ket{j_{1}} \otimes\bigotimes_{j_{2}=0}^{\text{ID}_{\text{max}}}\ket{j_{2}}. \tag{25}\]  
The starting state \(\ket{\psi}\) is:  
\[\ket{\psi}=\ket{\text{ID}}\otimes\bigotimes_{(m,r)\in\mathbf{M}\times\mathbf{R }} \begin{cases}\ket{1}&m=U\\ \ket{0}&m\
eq U\end{cases}