# From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
## 4 QAOA Mappings: Strings
### Example: Max-\(\kappa\)-ColorableSubgraph
#### 4.1.1 Single Qudit Mixing Operators
Therefore, we can implement \(U_{\text{parity}}\) by incrementing the register by one, applying an \(X(\beta)=e^{-i\beta X}\) to the least-significant qubit, decrementing the register by one, and then again applying an \(X(\beta)\) gate to the least-significant qubit. For an \(l\)-bit register, each incrementing and decrementing operation can be written as a series of \(l\) multiply-controlled \(X\) gates, with the numbers of control ranging from \(0\) to \(l-1\). **Repeated parity single-qudit ring mixers. ** As we mentioned above, a single application of \(U_{\text{parity}}(\beta)\) will have nonzero transition amplitudes only between pairs of colors with indices no more than two apart, which suggests that it may be useful to repeat the parity mixer within one mixing step. Partition single-qudit ring mixers. We now generalize the above construction for the parity single-qudit ring mixer to more general partition mixers. For a given ordered partition \(\mathcal{P}=(P_{1},\dots,P_{p})\) of the terms of \(H_{r\text{-}\text{NV}}\) such that all pairs of terms within a \(P_{i}\) act on disjoint states of the qudit, let:  
\[U_{\mathcal{P}\text{-}r\text{-}\text{NV}}(\beta)=U_{P_{p}\text{-}XY}(\beta) \cdots U_{P_{1}\text{-}XY}(\beta), \tag{11}\]  
where:  
\[U_{\mathcal{P}\text{-}XY}(\beta)=\prod_{\{\alpha,b\}\in P}e^{-i\beta(|a\rangle \langle b|+|b\rangle\langle a|)}. \tag{12}\]  
By construction, in the one-hot encoding, the terms of \(U_{P\text{-}XY}\) commute (because they act on disjoint pairs of qubits), and so the ordering does not matter; all can be implemented in parallel. We call \(U_{\mathcal{P}\text{-}r\text{-}\text{NV}}\) the \"partition \(\mathcal{P}\)\" \(r\)-nearby-values single-qudit ring mixer, and \(U_{\text{r-}\text{NV}}\) the \"simultaneous\" \(r\)-nearby-values single-qudit ring mixer to distinguish the latter from the former. The latter is member of H-QAOA, while the former is not. Even more generally, for a set of single-qudit ring mixers \(\{H_{\alpha}\}\) indexed by some \(\alpha\) and an ordered partition \(\mathcal{P}=(P_{1},\dots,P_{p})\) thereof, in which the single-qudit mixers within each part mutually commute, we defined a simultaneous version, \(e^{-i\beta\sum_{\alpha}H_{\alpha}}\) and a \(\mathcal{P}\)-partitioned version, \(\prod_{i=1}^{p}\left[\prod_{\alpha\in P_{i}}e^{-i\beta H_{\alpha}}\right]\), where the order of the product over the elements of each part does not matter because they commute, and the order of the product over the parts of the partition is given by their ordering within the ordered partition \(\mathcal{P}\). Binary single-qudit mixer for \(d=2^{l}\). We now return briefly to the binary encoding, and describe a different single-qudit mixer. An alternative to the \(r\)-nearby values single-qudit mixer, which is easily implementable using the binary encoding when \(d=2^{l}\) is a power of two, is the \"simple binary\" single-qudit mixer:  
\[H_{\text{binary}}^{\text{(enc)}}=\sum_{i=1}^{l}X_{i}, \tag{13}\]  
where \(X_{i}\) acts on the \(i\)th qubit in the binary encoding of the qudit. Since the ordering of the colors was arbitrary to begin with, it does not much matter whether the Hamiltonian mixes nearby values in the ordering or mixes the colors in a different way, in this case to colors with indices whose binary representations have Hamming distance 1. When \(d\) is not a power of 2, a straightforward generalization of the binary single-qudit mixer experiences difficulty in meeting the first of the design criteria, since swapping one of the bit values in the binary representation may take the evolution out of the feasible subspace. While requiring \(d\) to be a power of 2 restricts its general applicability, the binary single-qudit mixer could be useful in some interesting cases, such as 4-coloring. For 2-coloring (a problem equivalent to MaxCut), the full binary single-qudit mixer is simply the standard mixer \(X\).