Problem-size-independent angles for a Grover-driven quantum approximate optimization algorithm

The quantum approximate optimization algorithm (QAOA) requires that circuit parameters are determined that allow one to sample from high-quality solutions to combinatorial optimization problems. Such parameters can be obtained using either costly outer-loop optimization procedures and repeated calls to a quantum computer or, alternatively, via analytical means. In this work, we consider a context in which one knows a probability density function describing how the objective function of a combinatorial optimization problem is distributed. We show that, if one knows this distribution, then the expected value of strings, sampled by measuring a Grover-driven, QAOA-prepared state, can be calculated independently of the size of the problem in question. By optimizing this quantity, optimal circuit parameters for average-case problems can be obtained on a classical computer. Such calculations can help deliver insights into the performance of and predictability of angles in QAOA in the limit of large problem sizes, in particular, for the number partitioning problem.

Figure 1

Angles for the optimized infinite-size RCM are seen for QAOA depths 1 to 8. As the depth $p$ increases, a similar pattern of optimal parameters for the limiting distribution of the random cost model emerges with the problem Hamiltonian's angles monotonically increasing and the driver Hamiltonian angles monotonically decreasing. Such behavior invites comparison to adiabatic quantum computation, overlooking the nonzero start point of $\gamma$ and end point of $\beta$

Figure 2

Expectation value of the QAOA state for the random cost model at optimal angles exhibits an increasing solution quality at a decreasing rate.

Figure 3

For $p=1$, optimal parameters of the NPP converge to the infinite size angle for increasing $n$. QAOA states for 30 problem instances are optimized and angles averaged for each point.

Figure 4

Angles for the optimized infinite-size number partitioning problem are seen for QAOA depths 1 to 8. Optimal parameters follow annealing-reminiscent schedules and vary smoothly. Values are obtained here through the optimization of the formula derived in Appendix pp4 via the BFGS optimizer and a random start point strategy.

Figure 5

Optimizing the Grover-QAOA state for the number partitioning problem at increasing depth $p$ results in monotonically decreasing residue. The depth 0 value of 1 is added as a reference point attained by random sampling from the computational basis.

Figure 6

For $p=2$, optimal parameters of the NPP converge to the infinite size angle for increasing $n$. QAOA states for 30 problem instances are optimized and angles averaged for each point.

Figure 7

For $p=1$ the number partitioning problem landscape can be seen to converge to that of the large-$n$ limit for $n=5,7,12$. Periodicity is always observed in $\beta$, but as $n$ increases, for low $n$, local maxima and minima resurge in $\gamma$ due to common multiples in problem energy eigenvalues. For large $n$, increasing $\gamma$ past a region near zero results in the expectation monotonically returning to the mean value of 1.