The quantum approximate optimization algorithm (QAOA) has rapidly become a cornerstone of contemporary quantum algorithm development. Despite a growing range of applications, only a few results have been developed towards understanding the algorithm’s ultimate limitations. Here we report that QAOA exhibits a strong dependence on a problem instances constraint to variable ratio—this problem density places a limiting restriction on the algorithms capacity to minimize a corresponding objective function (and hence solve optimization problem instances). Such reachability deficits persist even in the absence of barren plateaus and are outside of the recently reported level-1 QAOA limitations. These findings are among the first to determine strong limitations on variational quantum approximate optimization.

• Received 25 July 2019
• Revised 24 October 2019
• Accepted 3 February 2020

DOI:https://doi.org/10.1103/PhysRevLett.124.090504