# 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  
We focused initially on designing _partial mixers_, component operators that will be used to construct full mixing operators. For this mapping of the maxColorableSubgraph problem, the partial mixers are operators acting on a qudit with dimension \(d=\kappa\) that mix between the colors associated to a single vertex \(v\). As we see in subsequent sections, this is a particularly simple case of partial mixers which are often more complicated multiqubit-controlled operators. Once we have defined these single-qudit partial mixing operators, we put them together to create a full mixer for the problem. We began by considering the following family of single-qudit mixing operators expressed in terms of qudits, and qudit operators, and then considered encodings and compilations to qubit-based architectures, which inspired us to consider other families of single-qubit mixing operators. See Appendix C.2 and References [36; 37] for a review of qudit operators, including the generalized Pauli operators \(\hat{X}\) and \(\hat{Z}\). \(r\)-nearby-values single-qudit mixer. Let \(U_{r\text{-}\text{NV}}(\beta)=e^{-i\beta H_{r\text{-}\text{NV}}}\), where \(H_{r\text{-}\text{NV}}=\sum_{i=1}^{r}\left(\hat{X}^{i}+\left(\hat{X}^{t}\right) ^{i}\right)\), which acts on a single qudit, with \(\hat{X}=\sum_{a=0}^{d-1}\left|a+1\right\rangle\left\langle a\right|\). We identified two special cases by name: The \"single-qudit ring mixer\" for \(r=1\), \(H_{\text{ring}}=H_{1\text{-}\text{NV}}\) and the \"fully-connected\" mixer for \(r=d-1\), \(H_{\text{FC}}=H_{(d-1)\text{-}\text{NV}}\). Whenever we introduced a Hamiltonian, we also implicitly introduced its corresponding family of unitaries, as with \(H_{r\text{-}\text{NV}}\) and \(U_{r\text{-}\text{NV}}(\beta)\). The single-qudit ring mixer is a cornerstone of many of the mixing constructions that we discuss. We concentrated on qubit encodings thereof, given the various projections of hardware with at least 40 qubits that will be available in the next year or two [11; 12], though it could alternatively be implemented directly using a qudit-based architecture. We explored two natural encodings of a qudit into qubits: (1) The _one-hot_ encoding using \(d\) qubits, in which each qudit basis state \(\left|a\right\rangle\), \(a=0,1,\ldots,d-1\), is encoded as \(\left|0\right\rangle^{\otimes d}\otimes\left|1\right\rangle\otimes\left|0 \right\rangle^{\otimes d-1-a}\); and (2) the _binary_ encoding using \(\left\lceil\log_{2}d\right\rceil\) qubits, in which each qudit state \(\left|a\right\rangle\) is encoded as the qubit computational basis state labeled by the binary representation of the integer \(a\). The one-hot encoding uses more qubits but supports a simpler compilation of the single-qudit ring mixer for general \(d\), both in the sense of it being much easier to write down a compilation, and in the sense that it uses many fewer two-qubit gates; in the one-hot encoding, 2-local mixing interactions suffice, whereas binary encoding requires \(\left\lceil\log_{2}d\right\rceil\)-local Hamiltonian terms, with the corresponding unitary requiring further compilation to two-qubit gates. In the one-hot encoding, the single-qudit ring mixer is encoded as a qubit unitary \(U_{\text{ring}}^{\text{(enc)}}\) corresponding to the qubit Hamiltonian:  
\[H_{\text{ring}}^{\text{(enc)}}=\sum_{a=0}^{d-1}\left(X_{a}X_{a+1}+Y_{a}Y_{a+1} \right), \tag{6}\]  
which acts on the qubit Hilbert space in a way that preserves the Hamming weight of computational basis states and acts as \(U_{\text{ring}}\) on the encoded subspace spanned by unit Hamming weight computational basis states. Although \(H_{\text{ring}}^{\text{(enc)}}\) is 2-local, its terms do not mutually commute. There are several implementation options.