  The quantum alternating operator ansatz (QAOA) is a heuristic hybrid
quantum-classical algorithm for finding high-quality approximate solutions to
combinatorial optimization problems, such as Maximum Satisfiability. While QAOA
is well-studied, theoretical results as to its runtime or approximation ratio
guarantees are still relatively sparse. We provide some of the first lower
bounds for the number of rounds (the dominant component of QAOA runtimes)
required for QAOA. For our main result, (i) we leverage a connection between
quantum annealing times and the angles of QAOA to derive a lower bound on the
number of rounds of QAOA with respect to the guaranteed approximation ratio. We
apply and calculate this bound with Grover-style mixing unitaries and (ii) show
that this type of QAOA requires at least a polynomial number of rounds to
guarantee any constant approximation ratios for most problems. We also (iii)
show that the bound depends only on the statistical values of the objective
functions, and when the problem can be modeled as a $k$-local Hamiltonian, can
be easily estimated from the coefficients of the Hamiltonians. For the
conventional transverse field mixer, (iv) our framework gives a trivial lower
bound to all bounded occurrence local cost problems and all strictly $k$-local
cost Hamiltonians matching known results that constant approximation ratio is
obtainable with constant round QAOA for a few optimization problems from these
classes. Using our novel proof framework, (v) we recover the Grover lower bound
for unstructured search and -- with small modification -- show that our bound
applies to any QAOA-style search protocol that starts in the ground state of
the mixing unitaries.
