XY-mixers: analytical and numerical results for QAOA

The Quantum Alternating Operator Ansatz (QAOA) is a promising gate-model meta-heuristic for combinatorial optimization. Extending the algorithm to include hard constraints presents an implementation challenge for near-term quantum resources. This work explores strategies for enforcing hard constraints by using XY-hamiltonians as the mixer. Despite the complexity of the XY-Hamiltonian mixer, 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 graphs and linearly connected 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 the XY-mixers is validated numerically demonstrating a significant improvement over the general X-mixer.

• Algorithms and Theory

• Quantum Computing