  The quantum approximate optimization algorithm (QAOA) is a variational
quantum algorithm, where a quantum computer implements a variational ansatz
consisting of $p$ layers of alternating unitary operators and a classical
computer is used to optimize the variational parameters. For a random
initialization, the optimization typically leads to local minima with poor
performance, motivating the search for initialization strategies of QAOA
variational parameters. Although numerous heuristic initializations exist, an
analytical understanding and performance guarantees for large $p$ remain
evasive. We introduce a greedy initialization of QAOA which guarantees
improving performance with an increasing number of layers. Our main result is
an analytic construction of $2p+1$ transition states - saddle points with a
unique negative curvature direction - for QAOA with $p+1$ layers that use the
local minimum of QAOA with $p$ layers. Transition states connect to new local
minima, which are guaranteed to lower the energy compared to the minimum found
for $p$ layers. We use the GREEDY procedure to navigate the exponentially
increasing with $p$ number of local minima resulting from the recursive
application of our analytic construction. The performance of the GREEDY
procedure matches available initialization strategies while providing a
guarantee for the minimal energy to decrease with an increasing number of
layers $p$.
