Analytical Expressions for the Quantum Approximate Optimization Algorithm and its Variants

The quantum approximate optimization algorithm (QAOA) is a near-term quantum algorithm aimed at solving combinatorial optimization problems. Since its introduction, various generalizations have emerged, spanning modifications to the initial state, phase unitaries, and mixer unitaries. In this work, we present an analytical study of broad families of QAOA variants. We begin with the family of QAOA featuring product mixers, which includes single-body mixers parametrized by multiple variational angles, and derive exact analytical expressions for the cost expectation on weighted problem graphs, using a single circuit ansatz layer. We then investigate a family of QAOA with many-body Grover-type mixers, and derive analogous analytical results for weighted problem hypergraphs and arbitrarily many circuit ansatz layers. For both families, we accommodate individual phase angles for each node and edge (hyperedge) on the problem graph (hypergraph). Our results reveal that, in contrast to product mixers, the Grover mixer is sensitive to contributions from cycles of all lengths in the problem graph, exhibiting a form of non-locality. Our study advances the understanding of QAOA's behavior in general scenarios, providing a foundation for further theoretical exploration.