Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems

Abstract

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=0p−1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\{{\gamma }_{i},{\beta }_{i}\}}_{i = 0}^{p-1}$$\end{document}. 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 Nq = 42 qubits and p = 400 layers suggest that the success probability scales as P(x*)≈2−η(p)Nq+C\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P({x}^{* })\approx {2}^{-\eta (p){N}_{q}+C}$$\end{document}, 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 Nq = 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.