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

Abstract

Abstract The quantum approximate optimization algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs), with performance governed by variational parameters $${\{{\gamma }_{i},{\beta }_{i}\}}_{i = 0}^{p-1}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mrow> <mml:mrow> <mml:mo>{</mml:mo> <mml:mrow> <mml:msub> <mml:mrow> <mml:mi>γ</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>i</mml:mi> </mml:mrow> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mrow> <mml:mi>β</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>i</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> <mml:mo>}</mml:mo> </mml:mrow> </mml:mrow> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>=</mml:mo> <mml:mn>0</mml:mn> </mml:mrow> <mml:mrow> <mml:mi>p</mml:mi> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msubsup> </mml:math> . 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}^{-\eta (p){N}_{q}+C}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>P</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:msup> <mml:mrow> <mml:mi>x</mml:mi> </mml:mrow> <mml:mrow> <mml:mo>*</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≈</mml:mo> <mml:msup> <mml:mrow> <mml:mn>2</mml:mn> </mml:mrow> <mml:mrow> <mml:mo>−</mml:mo> <mml:mi>η</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mrow> <mml:mi>p</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> <mml:msub> <mml:mrow> <mml:mi>N</mml:mi> </mml:mrow> <mml:mrow> <mml:mi>q</mml:mi> </mml:mrow> </mml:msub> <mml:mo>+</mml:mo> <mml:mi>C</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> , 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.

Topics & Concepts