# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## Appendix A Compendium of Mappings and Compilations
### Controlled-Bit-Flip (\(\Lambda_{f}(X)\)) Mixers  
All problems in this section are graph or subset problems with QAOA mappings that use controlled-bit-flip mixers on bit strings. (See Section 4.2). Note that MaxSetPacking (Appendix A.2.4)reduces to MaxIndependentSet (Appendix A.2.1) on the constraint graph; MinVertexCover (Appendix A.2.3) is a special case of MinSetCover (Appendix A.2.5), in which the universe is the set of edges, and each subset in the collection corresponds to the edges adjacent to a single vertex; and MaxClique (Appendix A.2.2) is simply MaxIndependentSet on the complement graph. **Configuration space:** The configuration space of each problem is the subsets \(V^{\prime}\) of some set \(V\) (resp., \(S^{\prime}\subset S\)), represented by bitstrings \(\mathbf{x}\in\left\{0,1\right\}^{n}\), with \(x_{v}=1\) indicating \(v\in V^{\prime}\). **Constraint graph:** An instance of each problem is either specified by a graph or has a natural corresponding constraint graph whose vertices correspond to the variables and with respect to which each variable \(v\) is graph-adjacent to \(\operatorname{nbhd}(v)\). **Domain:** Elements of the configuration space that satisfy some CNF formula (whose clauses correspond to the edges of the problem or the constraint graph, except for MinSetCover) that specifies a required property. **Objective:** Maximize or minimize the subset cardinality. **Mixing rule:** Swap an element \(v\) in or out of \(V^{\prime}\) if some predicate \(\chi(\mathbf{x}_{\operatorname{nbhd}(v)})\) is satisfied by the partial state of its neighbors. (The predicate \(\chi\) will depend on the problem.) **Partial mixing Hamiltonian:**\(H_{\operatorname{CX},v}=X_{v}H_{P_{v}}\), which can be used to define both a simultaneous controlled bit-flip mixer and a class of partitioned controlled bit-flip mixers. (See Section 4.2). **Appendix A.2.1. ** MaxIndependentSet [Section 4.2]  
**Problem:** Given \(G=(V,E)\), maximize the size of a subset \(V^{\prime}\subset V\) of mutually non-adjacent vertices. **Prior QAOA work:**[1]. See Section 4.2 for a detailed discussion of the mapping and generalization. **Approximability:** Poly-APX-complete [69], and has no constant factor approximation unless \(P=NP\). On bounded degree graphs with maximum degree \(D_{G}\geq 3\) can be approximated to \((D_{G}+2)/3\)[69], but remains APX-complete [51]. **Domain:** Independent sets, \(\left\{\mathbf{x}:\bigwedge_{\{u,v\}\in E}\tilde{x}_{u}\vee\tilde{x}_{v}\right\}\). **Objective:** max \(|V^{\prime}|=\sum_{v\in V}x_{v}\). **Mixing rule:** Swap \(v\) in or out of \(V^{\prime}\) if none of its neighbors are in \(V^{\prime}\). **Partial mixing Hamiltonian:**\(H_{\operatorname{CX},v}=X_{v}H_{\operatorname{NOR}(x_{\operatorname{nbhd}(v)})}\). **Phase separator:**\(U_{\operatorname{P}}(\gamma)=\exp(-i\gamma\sum_{u\in V}Z_{u})\). **Initial state:**\(\left|s\right\rangle=\left|0\right\rangle^{\otimes n}\), i.e., \(V^{\prime}=\emptyset\). **Resource count:**  
* **Controlled-bit-flip mixers:**\(n\) multiqubit-controlled-\(X(\beta)\) gates, each with at most \(D_{G}\) controls (exactly \(D_{v}\) controls for each vertex). Depth at most \(n\) but will be much less for sparsely connected graphs. * **Phase separator:**\(n\) single-qubit \(Z\)-rotations. Depth 1. **Variants:** Extends easily to weighted-MaxIndependentSet with objective function \(f=\sum_{i=1}^{n}w_{i}x_{i}\). **Appendix A.2.2. ** MaxClique  
**Problem:** Given \(G=(V,E)\), maximize the size of a clique in \(G\) (a subset \(V^{\prime}\subset V\) that induces a subgraph in which all pairs of vertices are adjacent). **Approximability:** A \(O(n/\log^{2}n)\)-approximation is known [70], but cannot be efficiently approximated classically better than \(O(n^{1-\varepsilon})\) for any \(\varepsilon>0\) unless \(P=NP\)[71]. **Domain:** Cliques, \(\left\{\mathbf{x}:\bigwedge_{\{u,v\}\in E(\overline{G})}\tilde{x}_{u}\vee \tilde{x}_{v}\right\}\). **Objective:** max \(|V^{\prime}|=\sum_{v\in V}x_{v}\).