Optimizing QAOA: Parameter Strategies and Performance Analysis for Combinatorial Problems

Loading...
Thumbnail Image

Date

Journal Title

Journal ISSN

Volume Title

Publisher

Unuversity Setif 1 Ferhat Abbas . Faculty of Sciences

Abstract

The Quantum Approximate Optimization Algorithm (QAOA) has emerged as one of the most promising variational algorithms for solving combinatorial optimization problems on near-term Noisy Intermediate-Scale Quantum (NISQ) devices. However, QAOA’s performance is highly sensitive to its variational parameters (γ, β), and finding optimal parameters remains computationally expensive, often requiring hundreds of quantum circuit evaluations. This thesis presents a systematic empirical study of QAOA parameter optimization strategies for the Maximum Cut problem (Max-Cut), with the goal of providing practical guidelines for QAOA implementation on NISQ devices. We begin by investigating the impact of circuit depth p ∈ {1, 2, 3, 4} on solution quality and computational cost across three graph families (3-Regular, Erdős-Rényi, and Barabási-Alber) of varying sizes (n ∈ {8, 10, 12}). Results show that increasing p consistently improves the approximation ratio when using gradient-free optimization, while gradient-based methods exhibit degradation at larger depths due to the barren plateau phenomenon. We then conduct a comparative evaluation of six classical optimizers (L-BFGS-B,COBYLA, AdaGrad, SPSA, Differential Evolution, and a Hybrid DE+L-BFGS-B) approach demon-strating that deterministic optimizers achieve equivalent solution quality at p = 2, with L-BFGS-B being the most computationally efficient. We further evaluate four parameter initialization strategies (Random, Fixed, TQA, and Warm-Start) showing that Fixed and Warm-Start consistently outperform Random and TQA, with Warm-Start offering the best balance between solution quality and computational efficiency. Finally, we characterize the QAOA optimization landscape through a complete visualiza-tion of the p = 1 landscape, revealing 10 local minima organized in three quality tiers, strong gradient magnitudes throughout the parameter space, and a dramatic growth in land-scape complexity with circuit depth. These findings provide rigorous theoretical explanations for all empirical results and offer concrete practical guidelines for QAOA implementation.

Description

Citation

Endorsement

Review

Supplemented By

Referenced By