Polynomial scaling of the quantum approximate optimization algorithm for ground-state preparation of the fully connected p-spin ferromagnet in a transverse field

We show that the quantum approximate optimization algorithm (QAOA) can construct, with polynomially scaling resources, the ground state of the fully connected p-spin Ising ferromagnet, a problem that notoriously poses severe difficulties to a vanilla quantum annealing (QA) approach due to the exponentially small gaps encountered at first-order phase transition for p≥3. For a target ground state at arbitrary transverse field, we find that an appropriate QAOA parameter initialization is necessary to achieve good performance of the algorithm when the number of variational parameters $2P$ is much smaller than the system size N because of the large number of suboptimal local minima. Instead, when P exceeds a critical value PN*∝N, the structure of the parameter space simplifies, as all minima become degenerate. This allows achieving the ground state with perfect fidelity with a number of parameters scaling extensively with N and with resources scaling polynomially with N.