# 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
First, hardware that natively implements the multiqubit gate \(U_{\text{ring}}^{\text{(enc)}}\) directly may be plausible (much as quantum annealers already support the simultaneous application of a Hamiltonian to a large set of qubits), but most proposals for universal quantum processors are based on two-qubit gates, so a compilation to such gates is desirable both for applicability to hardware likely to be available in the near term and for error-correction and fault tolerance in the longer term. Second, we could use constructions used in quantum many-body physics to compile \(U_{\text{ring}}^{\text{(enc)}}\) into a circuit of 2-local gates [38]. Third, the multiqubit gate \(U_{\text{ring}}^{\text{(enc)}}\) could be implemented approximately via Trotterization or other Hamiltonian simulation algorithms. A different approach, and the alternative we explore most extensively here, is to implement a different unitary rather than \(U_{r\text{-}\text{NV}}\), one related to \(U_{r\text{-}\text{NV}}\)and sharing its desirable mixing properties, as encapsulated in the design criteria of Section 3.1, which is easier to implement. The form of the circuit obtained by Trotterization is suggestive. We considered sequentially applying unitaries corresponding to subsets of terms in the Hamiltonian, each subset chosen in such a way that the corresponding unitary is readily implementable. This reasoning mirrors the relation of H-QAOA circuits to Trotterized AQO. We give a few examples of mixers obtained in this way. **Parity single-qudit ring mixer. ** Still in the one-hot encoding, we partitioned the \(d\) terms \(e^{-i\beta(X_{a}X_{a+1}+Y_{a}Y_{a+1})}\) by the parity of their indices. Let:  
\[U_{\text{parity}}(\beta)=U_{\text{last}}(\beta)U_{\text{even}}(\beta)U_{\text {odd}}(\beta), \tag{7}\]  
where:  
\[U_{\text{odd}}(\beta)=\prod_{a\text{ odd, }a\
eq n}e^{-i\beta(X_{a}X_{a +1}+Y_{a}Y_{a+1})},\qquad\qquad U_{\text{even}}(\beta)=\prod_{a\text{ even}}e^{-i\beta(X_{a}X_{a+1}+Y_{a}Y_{a+1})}, \tag{8}\] \[U_{\text{last}}(\beta)= \begin{cases}e^{-i\beta(X_{d}X_{1}+Y_{d}Y _{1})},&d\text{ odd},\\ I,&d\text{ even}.\end{cases}  \tag{9}\]  
Such \"XY\" gates are natively implemented on certain superconducting processors [39]. It is easy to see that the parity single-qudit ring mixer preserves the Hamming weight and hence meets the first criterion of keeping the evolution within the feasible single-qudit subspace. To see that it also meets the second, providing transitions between all feasible computational basis states, it is useful to consider the quantum swap gate, which behaves in exactly the same way as the XY gate on the subspace spanned by \(\left\{\left|0_{i}1_{j}\right\rangle,\left|1_{i}0_{j}\right\rangle\right\}\). The swap gate \(\text{SWAP}_{i,j}=\frac{1}{2}(I+X_{i}X_{j}+Y_{i}Y_{j}+Z_{i}Z_{j})\) is both unitary and Hermitian, and thus:  
\[e^{i\theta\text{SWAP}_{i,j}}=\cos(\theta)I+i\sin(\theta)\text{SWAP}_{i,j}. \tag{10}\]  
For \(0<\beta<\pi/2\), each term in the parity single-qudit ring mixer is a superposition of a swap gate and the identity. 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. Nevertheless, this mixer meets the second criteria because all possible orderings of \(d\) swap gates appear in \(\lceil\frac{d}{2}\rceil\) repeats of the parity operator for any \(0<\beta<\pi/2\), thus providing nonzero amplitude transitions between all feasible computational basis states for a single-vertex graph. When \(d\) is an integer power of two, there is also a straightforward, though more resource-intensive, compilation of the parity single-qudit ring mixer using the binary encoding. Applying a Pauli \(X\) gate to the least-significant qubit acts as \(H_{\text{even}}\) on the encoded subspace. Incrementing the register by one, applying the Pauli gate to the least-significant qubit, and finally decrementing the register by one overall acts as \(H_{\text{odd}}\).