# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## Appendix A Compendium of Mappings and Compilations
### XY Mixers
#### a.4.1 Max-\(\kappa\)-ColorableInducedSubgraph [Section 4.3]  
**Problem:** Given a graph \(G\) and \(\kappa\) colors, maximize the size of a subset of vertices \(V^{\prime}\subset V\) whose induced subgraph is \(\kappa\)-colorable. **Approximability:** Equivalent to MaxIndependentSet for \(k=1\). Both as easy and as hard to approximate as MaxIndependentSet for \(k\geq 1\)[50; 81]. On bounded degree graphs, can be approximated to \((D_{\mathrm{G}}/k+1)/2\), but remains APX-complete [82]. **Configuration space:**\(\left[\kappa+1\right]^{n}\). (0-th color is \"uncolored\" and represents \(v\
otin V^{\prime}\).) **Domain:**\(\kappa\)-colorable induced subgraphs, \(\left\{\mathbf{x}:\bigwedge_{\{i,j\}\in E}\left(\mathsf{EQ}(x_{i},0)\lor\mathsf{ EQ}(x_{j},0)\lor\mathsf{NEQ}(x_{i},x_{j})\right)\right\}\). **Objective:**\(\min\sum_{i=1}^{n}\mathsf{NEQ}(x_{i},0)\). **Initial state:** All vertices uncolored, \(\left|10\ldots 0\right\rangle^{\otimes n}\). **Mixing rule:** A vertex can switch between being uncolored and colored \(j\) only if none of its neighbours are colored \(j\). **Partial mixing Hamiltonian:** Controlled null-swap mixer at a vertex. **Encoding:** One-hot. **Phase separator:**\(U_{\mathsf{P}}(\gamma)=\exp(\frac{i}{2}\gamma\sum_{u\in V}\sum_{j=1}^{ \kappa}Z_{u,j})\). **Resource count:**  
\(\bullet\) **Partitioned controlled null-swap mixers:**\(n\kappa\) partial mixers, each acting on at most \(D_{G}+1\) qubits. Depth at most \(n\kappa\) but will be much less for sparsely connected graphs. \(\bullet\) **Phase separator:**\(n\) single-qubit \(Z\)-rotations. Depth 1. \(\bullet\) **Initial state:**\(\left|s\right\rangle=\left(\left|1\right\rangle\otimes\left|0\right\rangle ^{\otimes\kappa}\right)^{\otimes n}\), implemented in depth 1 with \(n\)\(X\) gates. Appendix A.4.2. MinGraphColoring [Section 4.4]  
**Problem:** Given a graph \(G\), minimize the number of colors required to properly color it. **Approximability:** The best classical algorithm [83] achieves approximation ratio \(O(n\frac{(\log\log n)^{2}}{\log^{3}n})\), and we cannot do better than \(n^{1-\epsilon}\) for any \(\epsilon>0\) unless \(P=NP\)[71]. For edge-colorings of multigraphs, there is a \((1.1+0.8/\kappa^{*})\)-approximate algorithm [84]. **Configuration space:**\([\kappa]^{n},\ \kappa=D_{G}+2\). **Domain:** Proper \(\kappa\)-colorings of \(G\) (many of which use fewer than \(\kappa\) colors), \(\left\{\mathbf{x}:\bigwedge_{\{i,j\}\in E}\mathsf{NEQ}(x_{i},x_{j})\right\}\). **Objective:** Minimize number of used colors: \(\sum_{a=1}^{\kappa}\mathsf{OR}(\mathsf{EQ}(x_{1},a),\ldots,\mathsf{EQ}(x_{n}, a))\). **Mixing rule:** The color of vertex \(u\) may be swapped between colors \(c\) and \(c^{\prime}\) if none of its neighbours are already colored \(c\) or \(c^{\prime}\). **Partial mixing Hamiltonian:** Controlled-swap partial mixing Hamiltonian. **Encoding:** One-hot. **Phase separator:**\(\prod_{a=1}^{\kappa}\Lambda_{\mathsf{OR}(x_{\left|a\right|,a})}\left(e^{-i \gamma}\right)\). **Resource count:**  
\(\bullet\) **Partitioned controlled-swap mixers:**\(\kappa(\kappa-1)n/2\) controlled gates on no more than \(D_{G}+2\) qubits. \(\bullet\) **Phase separator:**\(\kappa\) partial phase separators acting on \(n+1\) qubits, one target qubit and \(n\) control qubits. Depth 2 in partial phase separators, or depth 1 with the addition of \(\kappa\) ancilla qubits. \(\bullet\) **Initial state:** Any valid \(\kappa\) coloring (can be efficiently computed classically). Can be implemented in depth 1 using \(n\) single-qubit \(X\) gates. **Reduction from MinEdgeColoring:** In MinEdgeColoring, the objective is to minimize the number of colors needed to color the edges so that no two adjacent edges have the same color. This is equivalent to MinGraphColoring on the line graph. Appendix A.4.3. MinCliqueCover  
**Problem:** Given a graph \(G\), we seek the smallest collection of cliques \(S_{1},\ldots,S_{k}\subset V\), such that every vertex belongs to at least one clique.