The quantum alternating operator ansatz (QAOA) is a promising gate-model metaheuristic for combinatorial optimization. Applying the algorithm to problems with constraints presents an implementation challenge for near-term quantum resources. This paper 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 an integer variable admitting $\ensuremath{\kappa}$ discrete values represented through one-hot encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth $O(\ensuremath{\kappa})$. 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.
The Quantum Alternating Operator Ansatz is a generalization of the Quantum Approximate Optimization Algorithm (QAOA) designed for finding approximate solutions to combinatorial optimization problems with hard constraints. In this paper, we study Maximum k-Vertex Cover under this ansatz due to its modest complexity, while still being more complex than the well studied problems of Max-Cut and Max E3-LIN2. Our approach includes (i) a performance comparison between easy-to-prepare classical states and Dicke states as starting states, (ii) a performance comparison between two XY-Hamiltonian mixing operators: the ring mixer and the complete graph mixer, (iii) an analysis of the distribution of solutions via Monte Carlo sampling, and (iv) the exploration of efficient angle selection strategies. Our results are: (i) Dicke states improve performance compared to easy-to-prepare classical states, (ii) an upper bound on the simulation of the complete graph mixer, (iii) the complete graph mixer improves performance relative to the ring mixer, (iv) numerical results indicating the standard deviation of the distribution of solutions decreases exponentially in
p(the number of rounds in the algorithm), requiring an exponential number of random samples to find a better solution in the next round, and (v) a correlation of angle parameters which exhibit high quality solutions that behave similarly to a discretized version of the Quantum Adiabatic Algorithm.