Optimizing QAOA: Parameter Strategies and Performance Analysis for Combinatorial Problems
| dc.contributor.author | TEGGUICHE ,ISHAK | |
| dc.contributor.author | TALBI , HICHEM Supervisor | |
| dc.date.accessioned | 2026-11-17T08:23:25Z | |
| dc.date.issued | 2026 | |
| dc.description.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. | |
| dc.description.sponsorship | L’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.other | MAI/1169 | |
| dc.identifier.uri | https://repository.univ-setif.dz/handle/123456789/4315 | |
| dc.language.iso | en | |
| dc.publisher | Unuversity Setif 1 Ferhat Abbas . Faculty of Sciences | |
| dc.subject | Quantum Approximate Optimization Algorithm (QAOA) | |
| dc.subject | Variational Quantum Algo-rithms | |
| dc.subject | Combinatorial Optimization | |
| dc.subject | Maximum Cut (Max-Cut) | |
| dc.subject | Parameter Optimization | |
| dc.subject | Classical Optimizers | |
| dc.subject | Parameter Initialization | |
| dc.subject | NISQ Devices | |
| dc.subject | Optimization Landscape Anal-ysis | |
| dc.subject | Quantum-Classical Hybrid Algorithms | |
| dc.title | Optimizing QAOA: Parameter Strategies and Performance Analysis for Combinatorial Problems | |
| dc.type | Thesis |
