# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 4 QAOA Mappings: Strings
### Example: MaxColorableInducedSubgraph
#### 4.3.2 Full QAOA Mapping  
**Mixing operators.** Define:  
\[H_{\text{NS}}=\sum_{i=1}^{n}\sum_{a=1}^{\kappa}H_{\text{NS},i,a}. \tag{30}\]  
We defined two distinct types of mixers:  
* The _simultaneous_ controlled null-swap mixer, \(U_{\text{sim-NS}}(\beta)=e^{-i\beta H_{\text{NS}}}\), and;
* A family of _partitioned_ controlled null-swap mixers, \(U_{\text{P-NS}}(\beta)=\prod_{a=1}^{\kappa}\prod_{i=1}^{|\mathcal{P}|}\prod_{ \mathcal{D}\in P_{i}}U_{\text{NS},\mathcal{D},a}\).  
Again, we have a variety of partitioned mixers, each specified by an ordered partition \(\mathcal{P}\) of the vertices such that for each color the terms corresponding to the vertices in the partition commute. We segregated the colors into separate stages, but other orderings are possible.  
We used the one-hot encoding of Section 4.1, but with additional variables \(x_{v,0}\) for the uncolored states: The binary variables for each vertex \(v\) are \(x_{v,0},x_{v,1},\ldots,x_{v,k}\). This encoding uses \(n(\kappa+1)\) computational qubits. In this encoding, a single partial mixer has the form:  
\[U_{\text{NS},v,a}^{\text{(comp)}}(\beta)=\Lambda_{\text{NOR}(\pi_{\text{nbhd}( v),a})}\left(e^{-i\beta(X_{v,0}X_{v,a}+Y_{v,a}Y_{v,0})}\right), \tag{31}\]  
where \(\bar{\pi}_{\text{nbhd}(v),a}=\left(x_{v,a}\right)_{v\in\text{nbhd}(v)}\). Reasoning similar to that we used for the mixers discussed for the MaxIndependentSet and MaxColorableSubgraph problems shows that this mixer has nonzero transition amplitude between any feasible computational-basis state and the trivial state corresponding to the empty set as the induced subgraph. Two applications of this mixer give nonzero transition amplitudes between any two feasible computational-basis states.  
To ease compilation, each partial mixer can be implemented as:  
\[U_{\text{NS},v,a}^{\text{(comp)}}(\beta)=\Lambda_{\text{NOR}(\pi_{\text{nbhd}( v),a})}\left(X_{\text{anc}}\right)\Lambda_{x_{\text{anc}}}\left(e^{-i\beta(X_{v,0}X _{v,a}+Y_{v,a}Y_{v,0})}\right)\Lambda_{\text{NOR}(\pi_{\text{nbhd}(v),a})} \left(X_{\text{anc}}\right), \tag{32}\]  
where the control is intermediated by an ancilla qubit, which is initialized and returns to the zero state. Altogether, this construction uses \(\kappa n\) partial mixers, which can then be compiled into single- and two-qubit gates. For many graphs, partitions in which each set contains multiple commuting partial mixers exist, reducing the depth.  
**Phase-separation operator.** We can translate the objective function to a Hamiltonian as usual, or translate a linear modification of the objective function to obtain a simpler form. The phase separator function \(g(\mathbf{x})=n-2f(\mathbf{x})\) yields the simple phase separator Hamiltonian:  
\[H_{\text{P}}^{\text{(comp)}}=\sum_{v}Z_{v,0}, \tag{33}\]  
for which the corresponding unitary operator can be implemented using a depth-1 circuit of \(n\) single-qubit \(Z\)-rotations.  
**Initial state.** A reasonable initial state is \(\ket{s}=\left(\ket{1}\otimes\ket{0}^{\otimes\kappa}\right)^{\otimes n}\), corresponding to all vertices uncolored.