Towards 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 $\{{\gamma }_i,{\beta }_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^{\ast })\approx 2^{-\eta (p)N_q+C}$, where $\eta (p)$ decreases with increasing $p$. For example, in Weighted Maxcut instances, $\eta (10)=0.22$ improves to $\eta (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.

26 pages, 17 figures

References in corpus (16)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• Randomized Benchmarking of Quantum Gates
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• An introduction to quantum annealing
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms
• Computationally Efficient Zero Noise Extrapolation for Quantum Gate Error Mitigation
• Benchmarking Quantum Processor Performance at Scale
• Transfer learning of optimal QAOA parameters in combinatorial optimization
• Improving Performance in Combinatorial Optimization Problems with Inequality Constraints: An Evaluation of the Unbalanced Penalization Method on D-Wave Advantage
• Quantum Alternating Operator Ansatz (QAOA) beyond low depth with gradually changing unitaries
• Threshold for Fault-tolerant Quantum Advantage with the Quantum Approximate Optimization Algorithm
• Connectivity-aware Synthesis of Quantum Algorithms

Cited by in corpus (18)

• Quantum Approximate Multi-Objective Optimization
• Optimization via Quantum Preconditioning
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Extrapolation method to optimize linear-ramp QAOA parameters: Evaluation of QAOA runtime scaling
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• IF-QAOA: A Penalty-Free Approach to Accelerating Constrained Quantum Optimization
• Digitized Counter-Diabatic Quantum Optimization for Bin Packing Problem
• Predict and Conquer: Navigating Algorithm Trade-offs with Quantum Design Automation
• It's Quick to be Square: Fast Quadratisation for Quantum Toolchains
• Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms
• Qubit-efficient quantum combinatorial optimization solver
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits
• Evidence for effectively constant shot complexity in the quantum approximate optimization algorithm without per-instance optimization
• Quantum circuit evolutionary framework applied on set partitioning problem
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems
• Exploring Entanglement and Parameter Sensitivity in QAOA through Quantum Fisher Information
• Diagnosing crosstalk in large-scale QPUs using zero-entropy classical shadows
• Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers