# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 4 QAOA Mappings: Strings
### Example: Max-\(\kappa\)-ColorableSubgraph
#### 4.1.2 Full QAOA Mapping  
Having introduced several partial mixers for single qudits, we now show a complete QAOA circuit for MaxColorableSubgraph with \(n\) vertices, \(m\) edges, and \(\kappa\) colors, compiled to 2-local gates on qubits. Using the one-hot encoding, we require \(n\kappa\) qubits. Mixing operator. We used as the full mixer a parity ring mixer made up of parity single-qudit ring mixers, one for each of the qudits corresponding to each vertex:  
\[U_{\text{M}}=\prod_{p=1}^{n}U_{\text{$\text{$\text{$\text{$\text{$\text{$ \text{$\text{$\text{$\text{$\text{$\text{$\text{$}}${\text{$\text{$ \text{$}}}{}{}{}{}{}{}{}{}{}{}{}{{}{{}{{}{{}{}{{}{}{}{}{{}{}{}{}{}{}{{}{}{}{}{}{}{}{}{}{}{}{}{{}{}{}{}{}{}{}{}{  
The single qubit mixers act on different qubits and can be applied in parallel. The overall parity mixing operator required a depth-2 or depth-3 circuit (for even and odd \(\kappa\), respectively) of \(n\kappa\) gates. Other single-qudit mixers we defined above, including \(r\) repeats of the parity ring mixer, other partitioned mixers, or the binary mixer, could be used in place of the parity single-qudit mixer in this construction. All of these unitary mixers by construction meet our first criterion for a mixer: Keeping the evolution in the feasible subspace. Further, each of these mixers, after at most \(\lceil\frac{\kappa}{2}\rceil\) repeats, provides nonzero amplitude transitions between all colors at a given vertex, with the product providing transitions between any two feasible states.  
Phase-separation operator.The objective function can be written in classical one-hot encoding as:  
\[m-\sum_{\{u,v\}\in E}\sum_{a=1}^{k}x_{u,a}x_{v,a}, \tag{15}\]  
where \(x_{v,a}=1\), indicating that vertex \(v\) has been assigned color \(a\). To obtain a phase-separation Hamiltonian, we substituted \((I-Z)/2\) for each binary variable to obtain:  
\[H_{\text{P}}^{\prime}=\frac{4-\kappa}{4}mI+\frac{1}{4}\sum_{\{u,v\}\in E}\sum_ {a=1}^{\kappa}\left(Z_{u,a}+Z_{v,a}-Z_{u,a}Z_{v,a}\right). \tag{16}\]  
The constant term affects only a physically-irrelevant global phase, and since we are only concerned about the feasible subspace, we can disregard each sum \(\sum_{a=1}^{\kappa}Z_{u,a}\) of all \(\kappa\) single \(Z\) operators corresponding to a single qudit, since they multiply each of the \(d\) Hamming weight 1 elements corresponding to the \(d\) single qudit values by the same constant, resulting in a global phase. Removing those terms and rescaling, the phase separator now has the simpler form:  
\[H_{\text{P}}^{\text{(enc)}}=\sum_{\{u,v\}\in E}\sum_{a=1}^{\kappa}Z_{u,a}Z_{v,a}, \tag{17}\]  
where \(Z_{v,a}\) acts on the \(a\)th qubit in the one-hot encoding of the \(v\)th qudit, corresponding to coloring vertex \(v\) with color \(a\). The phase separator requires a circuit containing \(n\kappa\) two-qubit gates with depth at most \(D_{G}+1\), where \(D_{G}\) is the maximum degree over all vertices in the instance graph \(G\). Translated back to acting on qudits, Equation (17) acts as \(H_{\text{P}}=H_{g}\) (as defined in Equation (3)), where \(g(\mathbf{x})=\kappa m-4f(\mathbf{x})\). We refer to this function \(g\) as the \"phase function\", which will typically be an affine transformation of the objective function, which corresponds simply to a physically irrelevant global phase and a rescaling of the parameter. Defining \(H_{\text{P}}\) using such a phase function allows us to write a simpler encoded version \(H_{\text{P}}^{\text{(enc)}}\) that corresponds exactly to \(H_{\text{P}}\), without qualification, on the encoded subspace. Initial state.Any encoded coloring can be generated by a depth-1 circuit of at most \(n\) single-qubit \(X\) gates. A reasonable initial state is one in which all vertices are assigned the same color. Alternatively, we could start with any other feasible state, or the initial state could be obtained by applying one or more rounds of the mixer to a single feasible state, so that the algorithm begins with a superposition of feasible states.