Towards a Linear-Ramp QAOA protocol: Evidence of a scaling advantage in solving some combinatorial optimization problems
J. A. Montañez-Barrera, Kristel F. L. Michielsen · arXiv (Cornell University) · 2024
The Quantum Approximate Optimization Algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs), with performance governed by variational parameters $\{γ_i, β_i\}_{i=0}^{p-1}$. While most prior work has focused on classically optimizing these parameters, we demonstrate that fixed linear ramp schedules, linear ramp QAOA (LR-QAOA), can efficiently approximate optimal solutions across diverse COPs. Simulations with up to $N_q=42$ qubits and $p=400$ layers suggest that the success probability scales as $P(x^*) \approx 2^{-η(p) N_q + C}$, where $η(p)$ decreases with increasing $p$. For example, in Weighted Maxcut instances, $η(10) = 0.22$ improves to $η(100) = 0.05$. Comparisons with classical algorithms, including simulated annealing, Tabu Search, and branch-and-bound, show a scaling advantage for LR-QAOA. We show results of LR-QAOA on multiple QPUs (IonQ, Quantinuum, IBM) with up to $N_q = 109$ qubits, $p=100$, and circuits requiring 21,200 CNOT gates. Finally, we present a noise model based on two-qubit gate counts that accurately reproduces the experimental behavior of LR-QAOA.