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 $\kappa$ discrete values represented through one-hot encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth $O\left(\kappa \right)$. 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.

• Received 1 August 2019

DOI:https://doi.org/10.1103/PhysRevA.101.012320