Reachability deficit of variational Grover search

The quantum approximate optimization algorithm (QAOA) is promising for achieving quantum computational advantage with near-term quantum devices. It was numerically shown that the QAOA cost functions exhibit a phenomenon called reachability deficit (RD), where the success probability cannot reach unity until the circuit depth exceeds a certain critical value. However, an in-depth theoretical understanding of RD remains lacking. Here we focus on a variational variant of Grover search on multiple marked solutions as a prototype for analyzing the RD problem, where we further relax the criterion of reachability by tolerating a certain probability of failure. Specifically, we obtain a general analytical expression relating the critical depth of the quantum circuit to the solution density. In the dilute limit, the critical depth is consistent with the Grover bound, exhibiting a robust quadratic scaling that is insensitive to the failure probability. Moreover, we also find that the projective mixing Hamiltonian performs significantly better than the traditional mixing Hamiltonian in the QAOA, although it is less favorable in terms of physical implementation. However, by taking into account two-body interactions in the mixing Hamiltonian, the performance becomes on par with the projective mixing Hamiltonian at the cost of $O\left(n^2\right)$ additional terms. These results represent a simplified but insightful model of the QAOA, fully addressing the dependence of required circuit depth over the ground-state degeneracy.