Polynomial scaling of QAOA for ground-state preparation of the fully-connected p-spin ferromagnet

Abstract

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 Quantum Annealing (QA) approach, due to the exponentially small gaps encountered at first-order phase transition for $\mathrm{p}\ge 3$. For a target ground state at arbitrary transverse field, we find that an appropriate QAOA parameter initialization is necessary to achieve a good performance of the algorithm when the number of variational parameters $2\mathrm{P}$ is much smaller than the system size $\mathrm{N}$, because of the large number of sub-optimal local minima. Instead, when $\mathrm{P}$ exceeds a critical value ${\mathrm{P}}_{\mathrm{N}}^{\ast }\propto \mathrm{N}$, the structure of the parameter space simplifies, as all minima become degenerate. This allows to achieve the ground state with perfect fidelity with a number of parameters scaling extensively with $\mathrm{N}$, and with resources scaling polynomially with $\mathrm{N}$.

4 pages, 4 figures, Appendices 5 pages

Cited by in corpus (5)

• Digitized-counterdiabatic quantum approximate optimization algorithm
• Parameter Concentration in Quantum Approximate Optimization
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Progress towards analytically optimal angles in quantum approximate optimisation