Classical symmetries and QAOA

We study the relationship between the quantum approximate optimization algorithm (QAOA) and the classical symmetries of the problem cost function to be optimized. Our approach formalizes the connection between (i) symmetry properties of the QAOA dynamics and (ii) the group of symmetries of the cost function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. We show how classical cost function symmetries lead to invariant measurement probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. We provide an illustrative application of the developed connection by using symmetry properties of graphs as features in a machine learning model used to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important and well-studied setting where QAOA schedules are constrained to be linear and hence easier to optimize.