Optimizing QAOA: Parameter Strategies and Performance Analysis for Combinatorial Problems

dc.contributor.authorTEGGUICHE ,ISHAK
dc.contributor.authorTALBI , HICHEM Supervisor
dc.date.accessioned2026-11-17T08:23:25Z
dc.date.issued2026
dc.description.abstractThe 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.
dc.description.sponsorshipL’algorithme d’optimisation approximative quantique (QAOA) est un algorithme variationnel prometteur pour résoudre des problèmes d’optimisation combinatoire sur les dispositifs quan-tiques bruités (NISQ). Cependant, ses performances dépendent fortement de ses paramètres (γ, β), dont l’optimisation reste coûteuse. Cette thèse présente une étude empirique systé-matique des stratégies d’optimisation des paramètres du QAOA pour le problème de la coupe maximale (Max-Cut), afin de fournir des lignes directrices pratiques pour son implémentation. D’abord, l’impact de la profondeur du circuit p ∈ {1, 2, 3, 4} est analysé sur trois familles de graphes (3-régulier, Erdős-Rényi, Barabási-Albert) de tailles n ∈ {8, 10, 12}. Les résultats montrent que l’augmentation de p améliore le taux d’approximation avec les méthodes sans gradient, tandis que les approches basées sur le gradient se dégradent aux fortes profondeurs à cause des plateaux stériles. Ensuite, une évaluation comparative de six optimiseurs classiques (L-BFGS-B, COBYLA, AdaGrad, SPSA, Évolution Différentielle et un hybride DE+L-BFGS-B) montre qu’à p = 2, les méthodes déterministes offrent une qualité équivalente, L-BFGS-B étant la plus efficace. De plus, parmi quatre stratégies d’initialisation (Aléatoire, Fixe, TQA, Warm-Start), les ap-proches Fixe et Warm-Start surpassent les autres, Warm-Start offrant le meilleur compromis performance/coût. Enfin, la cartographie complète du paysage d’optimisation pour p = 1 révèle 10 minima locaux structurés en trois niveaux de qualité, de forts gradients, et une complexité exponentielle avec p. Ces observations explicitent les résultats empiriques et fournissent des règles concrètes pour optimiser l’usage du QAOA.
dc.identifier.otherMAI/1169
dc.identifier.urihttps://repository.univ-setif.dz/handle/123456789/4315
dc.language.isoen
dc.publisherUnuversity Setif 1 Ferhat Abbas . Faculty of Sciences
dc.subjectQuantum Approximate Optimization Algorithm (QAOA)
dc.subjectVariational Quantum Algo-rithms
dc.subjectCombinatorial Optimization
dc.subjectMaximum Cut (Max-Cut)
dc.subjectParameter Optimization
dc.subjectClassical Optimizers
dc.subjectParameter Initialization
dc.subjectNISQ Devices
dc.subjectOptimization Landscape Anal-ysis
dc.subjectQuantum-Classical Hybrid Algorithms
dc.titleOptimizing QAOA: Parameter Strategies and Performance Analysis for Combinatorial Problems
dc.typeThesis

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
MAI1169.pdf
Size:
282.87 KB
Format:
Adobe Portable Document Format

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed to upon submission
Description: