  An important property of QAOA with Grover mixer is that its expectation value
is invariant over any permutation of states. As a consequence, the algorithm is
independent of the structure of the problem. If, on the one hand, this
characteristic raises serious doubts about the capacity of the algorithm to
overcome the bound of the unstructured search problem, on the other hand, it
can pave the way to its analytical study. In this sense, a prior work
introduced a statistical approach to analyze GM-QAOA that results in an
analytical expression for the expectation value depending on the probability
distribution associated with the problem Hamiltonian spectrum. Although the
method provides surprising simplifications in calculations, the expression
depends exponentially on the number of layers, which makes direct analytical
treatment unfeasible. In this work, we extend the analysis to the more simple
context of Grover Mixer Threshold QAOA (GM-Th-QAOA), a variant that replaces
the phase separation operator of GM-QAOA to encode a threshold function. As a
result, we obtain an expression for the expectation value independent of the
number of layers and, with it, we provide bounds for different performance
metrics. Furthermore, we extend the analysis to a more general context of QAOA
with Grover mixer, which we called Grover-based QAOA. In that framework, which
allows the phase separation operator to encode any compilation of the cost
function, we generalize all the bounds by using a contradiction argument with
the optimality of Grover's algorithm on the unstructured search problem. As a
result, we get the main contribution of this work, an asymptotic lower bound on
the quantile achieved by the expectation value that formalizes the notion that
the Grover mixer, at most, reflects a quadratic Grover-style speed-up over
classical brute force.
