# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 4 QAOA Mappings: Strings
### Example: MaxIndependentSet  
ProblemGiven a graph \(G=(V,E)\), with \(|V|=n\) and \(|E|=m\), find the largest subset \(V^{\prime}\subset V\) of mutually non-adjacent vertices.  
This problem was discussed in Section VII of Reference [1] as a \"variant\" of the quantum approximate optimization algorithm introduced in that paper. To handle this problem, [PERSON] et al. suggested restricting the evolution to what we are calling the feasible subspace of the overall Hilbert space, the subspace spanned by computational basis elements corresponding to independent sets, through modification of what we are calling the mixing operator. We made the construction of the H-QAOA mixer [PERSON] et al. defined more explicit, and introduced partitioned mixers that have implementation advantages over the H-QAOA, or simultaneous, mixer defined in [PERSON] et al.  
The configuration space is the set of \(n\)-bit strings, representing subsets \(V^{\prime}\subset V\) of vertices, where \(i\in V^{\prime}\) if and only if \(x_{i}=1\). The domain \(F\) is represented by the subset of all \(n\)-bit strings corresponding to independent sets of \(G\). In contrast to the domain for MaxColorableSubgraph, this domain is dependent on the problem instance, not just on the size of the problem. Because the configuration is already bit-based, some aspects of mapping this problem to QAOA are simpler, but the partitioned mixing operators are more complicated in that they require controlled operation.  
To support the discussion of controlled operators, we used the notation \(\Lambda_{\mathbf{y}}(Q)\) to indicate a unitary _target operator_\(Q\) applied to a set of target qubits controlled by the state \(\mathbf{y}\) of a set of control qubits:  
\[\Lambda_{\mathbf{y}}(Q)=\sum_{\mathbf{y}^{\prime}\
eq\mathbf{y}}\left|\mathbf{ y}^{\prime}\right\rangle\left\langle\mathbf{y}^{\prime}\right|\otimes I+\left| \mathbf{y}\right\rangle\left\langle\mathbf{y}\right|\otimes Q. \tag{18}\]  
More generally, we used \(\Lambda_{\chi}(Q)\) when the operation was controlled on a predicate \(\chi\):  
\[\Lambda_{\chi}(Q)=\sum_{\mathbf{y}:\sim\chi(\mathbf{y})}\left|\mathbf{y} \right\rangle\left\langle\mathbf{y}\right|\otimes I+\sum_{\mathbf{y}:\chi( \mathbf{y})}\left|\mathbf{y}\right\rangle\left\langle\mathbf{y}\right|\otimes Q. \tag{19}\]  
Whether the subscript of \(\Lambda\) is a string or predicate will be clear from context. For a Hamiltonian \(H_{\mathrm{Q}}\) such that \(Q=e^{-iH_{\mathrm{Q}}}\), we can write the controlled unitary Equation (19) as:  
\[\Lambda_{\chi}(Q)=e^{-iH_{\chi}\otimes H_{\mathrm{Q}}}. \tag{20}\]  
We refer to \(H_{\chi}\otimes H_{\mathrm{Q}}\) as the _controlled Hamiltonian_, \(\chi\)-controlled-\(H_{\mathrm{Q}}\). Note that the Hamiltonian \(H_{\chi}\) that acts as the predicate \(\chi\) on computational basis states, in the sense of Equation (3), is precisely the projector \(H_{\chi}=\sum_{\mathbf{x}:\chi(\mathbf{x})=1}\left|\mathbf{x}\right\rangle \left\langle\mathbf{x}\right|\) that projects onto the subspace on which the predicate is \(1\). We used this relation to connect corresponding controlled Hamiltonians and controlled unitaries. In particular, when we want to apply a phase only on the part of the Hilbert space picked out by a predicate \(\chi\), we can write:  
\[\Lambda_{\chi}\left(e^{-i\theta}\right)=e^{-i\theta H_{\chi}}, \tag{21}\]  
where we have adapted the control notation of Equation (20) to mean applying the operator \(Q=e^{-i\theta}\) to zero target qubits. We often compile controlled unitaries (both phase separators and mixers) by using ancilla qubits to intermediate the control, e.g., for a single ancilla qubit (initialized at \(\left|0\right\rangle\) and returned thereto):  
\[\left(\Lambda_{\chi}\left(Q\right)\right)^{\left(\mathrm{comp}\right)}=\Lambda _{\chi}\left(X_{\mathrm{anc}}\right)\Lambda_{x_{\mathrm{anc}}}\left(Q\right) \Lambda_{\chi}\left(X_{\mathrm{anc}}\right). \tag{22}\]  
We explore in detail the construction of such controlled Hamiltonians and unitaries in Reference [5].