The Duel of the Mixers in Quantum Approximate Optimization

Our new paper "Equivariant QAOA and the Duel of the Mixers" has been accepted in IEEE Transactions on Quantum Engineering!

In this work, we show that the choice of mixer Hamiltonian plays a critical role in QAOA performance. Many combinatorial optimization problems have natural symmetries, but standard QAOA mixers do not take advantage of them. We introduce new symmetry aware mixers that are tailored to the structure of the problem and can be efficiently implemented as quantum circuits. Through numerical experiments on graph coloring and graph partitioning, we demonstrate that these mixers consistently outperform the standard approach. We also explain why warm start QAOA often fails to improve results, identifying a fundamental limitation that prevents guaranteed convergence. This work shows that exploiting symmetry is a powerful and practical way to improve quantum optimization algorithms.

Congratulations and huge thanks to our co-authors Boris Tsvelikhovskiy and Yuri Alexeev! Check our paper at https://arxiv.org/abs/2405.07211