Towards a universal QAOA protocol: Evidence of a scaling advantage in
  solving some combinatorial optimization problems
The quantum approximate optimization algorithm (QAOA) is a promising
algorithm for solving combinatorial optimization problems (COPs). In this
algorithm, there are alternating layers consisting of a mixer and a problem
Hamiltonian. Each layer $i=0,\ldots,p-1$ is parameterized by $\beta_i$ and
$\gamma_i$. How to find these parameters has been an open question with the
majority of the research focused on finding them using classical algorithms. In
this work, we present evidence that fixed linear ramp schedules constitute a
universal set of QAOA parameters, i.e., a set of $\gamma$ and $\beta$
parameters that rapidly approximate the optimal solution, $x^*$, independently
of the COP selected, and that the success probability of finding it,
$probability(x^*)$, increases with the number of QAOA layers $p$. We simulate
linear ramp QAOA protocols (LR-QAOA) involving up to $N_q=42$ qubits and $p =
400$ layers on random instances of 9 different COPs. The results suggest that
$probability(x^*) \approx 1/2^{(\eta N_q / p)}$ for a constant $\eta$. For
example, when implementing LR-QAOA with $p=42$, the $probability(x^*)$ for
42-qubit Weighted MaxCut problems (W-MaxCut) increases from $2/2^{42}\approx
10^{-13}$ to an average of 0.13. We compare LR-QAOA, simulated annealing (SA),
and branch-and-bound (B\&B) finding a scaling improvement in LR-QAOA. We test
LR-QAOA on real hardware using IonQ Aria, Quantinuum H2-1, IBM Brisbane, IBM
Kyoto, and IBM Osaka, encoding random weighted MaxCut (W-MaxCut) problems from
5 to 109 qubits and $p=3$ to $100$. Even for the largest case, $N_q=109$ qubits
and $p=100$, information about the LR-QAOA optimization protocol is present.
The circuit involved requires 21200 CNOT gates. These results show that LR-QAOA
effectively finds high-quality solutions for a large variety of COPs and
suggest a scaling advantage of quantum computation for combinatorial
optimization.
J. A. Montanez-Barrera Kristel Michielsen