  We study the relationship between the Quantum Approximate Optimization
Algorithm (QAOA) and the underlying symmetries of the objective function to be
optimized. Our approach formalizes the connection between quantum symmetry
properties of the QAOA dynamics and the group of classical symmetries of the
objective 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. In particular we show how
classical objective function symmetries lead to invariant measurement outcome
probabilities across states connected by such symmetries, independent of the
choice of algorithm parameters or number of layers. To illustrate the power of
the developed connection, we apply machine learning techniques towards
predicting QAOA performance based on symmetry considerations. We provide
numerical evidence that a small set of graph symmetry properties suffices to
predict the minimum QAOA depth required to achieve a target approximation ratio
on the MaxCut problem, in a practically important setting where QAOA parameter
schedules are constrained to be linear and hence easier to optimize.
