  The Quantum Alternating Operator Ansatz (QAOA) is a promising gate-model
meta-heuristic for combinatorial optimization. Applying the algorithm to
problems with constraints presents an implementation challenge for near-term
quantum resources. This work explores strategies for enforcing hard constraints
by using $XY$-Hamiltonians as mixing operators (mixers). Despite the complexity
of simulating the $XY$ model, we demonstrate that for problems represented
through one-hot-encoding, certain classes of the mixer Hamiltonian can be
implemented without Trotter error in depth $O(\kappa)$ where $\kappa$ is the
number of assignable colors. We also specify general strategies for
implementing QAOA circuits on all-to-all connected hardware graphs and linearly
connected hardware graphs inspired by fermionic simulation techniques.
Performance is validated on graph coloring problems that are known to be
challenging for a given classical algorithm. The general strategy of using
$XY$-mixers is borne out numerically, demonstrating a significant improvement
over the general $X$-mixer, and moreover the generalized $W$-state yields
better performance than easier-to-generate classical initial states when $XY$
mixers are used.
