IEEE International Conference on Quantum Artificial Intelligence (QAI)

Scalable Quantum Approximate Optimisation with Adaptive Bayesian Dimensionality Reduction

Amir Alizadeh, Amir Pourabdollah, Ahmad Lotfi

Published Nov 2, 2025• 0 citations

Abstract

Quantum Approximate Optimisation Algorithm (QAOA) has emerged as a promising hybrid quantum-classical approach for tackling NP-hard combinatorial optimisation problems by combining quantum and classical computational paradigms. However, efficiently optimising QAOA parameters is notoriously challenging due to the complex, high-dimensional landscapes involved, characterised by numerous local minima and barren plateaus. Bayesian Optimisation (BO) has shown promise in addressing these challenges, yet its effectiveness diminishes significantly with increasing problem dimensionality. In this work, we adopt the Minimum Average Variance Estimation for Bayesian Optimisation (MAVE-BO) method to address this scalability bottleneck. By leveraging the low-dimensional structure inherent in QAOA parameter spaces, our approach improves optimisation efficiency and robustness. We applied our model to a practical power systems problem, optimising eigenvector centrality (EC) in an IEEE 14-bus network. The proposed method demonstrates superior performance in both efficiency and solution quality compared to classical optimisers such as standard Bayesian Optimisation (Vanilla BO), COBYLA, L-BFGS-B, and genetic algorithms. These results underscore the potential of dimensionality-aware BO frameworks for realworld quantum applications in noisy, resource-constrained environments.

DOI: 10.1109/qai63978.2025.00037

Related papers

Hybrid Quantum–Classical Optimization: Enhancing QAOA Performance via Classical Optimizer Selection

Xuezhu Chen

Hybrid Quantum–Classical Optimization combines the advantages of quantum computing and classical optimization to address complex combinatorial optimization problems. The Quantum Approximate Optimization Algorithm (QAOA), as an outstanding Variational Quantum Algorithm (VQA), shows great potential in solving combinatorial optimization problems. Classical optimization methods play a crucial role in tuning the parameters of quantum circuits, affecting the algorithm’s convergence speed and solution quality. This paper designs and simulates QAOA circuits based on the Qiskit framework, focusing on comparing the performance of three classical optimizers— Adaptive Moment Estimation (Adam), Constrained Optimization BY Linear Approximations (COBYLA), and Simultaneous Perturbation Stochastic Approximation (SPSA)—in parameter optimization. Adam and SPSA perform more stably in deeper circuits, making them suitable for high-dimensional parameter spaces, whereas COBYLA tends to get trapped in local optima and exhibits greater fluctuations under limited iterations. The results further highlight the importance of classical optimizer selection and hyperparameter tuning in enhancing the performance of hybrid quantum–classical optimization algorithms.

International Conference on Machine Learning, Computational Intelligence and Pattern Recognition (MLCIPR)Dec 19, 20250 citations

Quantum approximate optimization via learning-based adaptive optimization

Lixue Cheng, Yuqin Chen, Shi‐Xin Zhang +1 more

Abstract Combinatorial optimization problems are ubiquitous and computationally hard to solve in general. Quantum approximate optimization algorithm (QAOA), one of the most representative quantum-classical hybrid algorithms, is designed to solve combinatorial optimization problems by transforming the discrete optimization problem into a classical optimization problem over continuous circuit parameters. QAOA objective landscape is notorious for pervasive local minima, and its viability significantly relies on the efficacy of the classical optimizer. In this work, we design double adaptive-region Bayesian optimization (DARBO) for QAOA. Our numerical results demonstrate that the algorithm greatly outperforms conventional optimizers in terms of speed, accuracy, and stability. We also address the issues of measurement efficiency and the suppression of quantum noise by conducting the full optimization loop on a superconducting quantum processor as a proof of concept. This work helps to unlock the full power of QAOA and paves the way toward achieving quantum advantage in practical classical tasks.

arXiv:2303.14877Communications PhysicsMar 6, 202448 citations

Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation

Tom Krüger, Wolfgang Mauerer

The Quantum Approximate Optimisation Algorithm (QAOA) is a widely studied quantum-classical iterative heuristic for combinatorial optimisation. While QAOA targets problems in complexity class NP, the classical optimisation procedure required in every iteration is itself known to be NP-hard. Still, advantage over classical approaches is suspected for certain scenarios, but nature and origin of its computational power are not yet satisfactorily understood. By introducing means of efficiently and accurately approximating the QAOA optimisation landscape from solution space structures, we derive a new algorithmic variant of unit-depth QAOA for two-level Hamiltonians (including all problems in NP): Instead of performing an iterative quantum-classical computation for each input instance, our non-iterative method is based on a quantum circuit that is instance-independent, but problem-specific. It matches or outperforms unit-depth QAOA for key combinatorial problems, despite reduced computational effort. Our approach is based on proving a long-standing conjecture regarding instance-independent structures in QAOA. By ensuring generality, we link existing empirical observations on QAOA parameter clustering to established approaches in theoretical computer science, and provide a sound foundation for understanding the link between structural properties of solution spaces and quantum optimisation.

arXiv:2408.06493QuantumNov 6, 20253 citations

Bayesian Optimization for QAOA

Simone Tibaldi, Davide Vodola, Edoardo Tignone +1 more

The Quantum Approximate Optimization Algorithm (QAOA) adopts a hybrid quantum-classical approach to find approximate solutions to variational optimization problems. In fact, it relies on a classical subroutine to optimize the parameters of a quantum circuit. In this work we present a Bayesian optimization procedure to fulfil this optimization task, and we investigate its performance in comparison with other global optimizers. We show that our approach allows for a significant reduction in the number of calls to the quantum circuit, which is typically the most expensive part of the QAOA. We demonstrate that our method works well also in the regime of slow circuit repetition rates, and that few measurements of the quantum ansatz would already suffice to achieve a good estimate of the energy. In addition, we study the performance of our method in the presence of noise at gate level, and we find that for low circuit depths it is robust against noise. Our results suggest that the method proposed here is a promising framework to leverage the hybrid nature of QAOA on the noisy intermediate-scale quantum devices.

arXiv:2209.03824IEEE Transactions on Quantum EngineeringJan 1, 202318 citations

Sample-Efficient Tuning of Quantum Circuit Parameters via Bayesian Optimization

Alessandro Pannone, Federico Tosone, Daniel Faccini +2 more

In this work, we present a Bayesian Optimization (BO) approach for tuning the parameters of the Quantum Approximate Optimization Algorithm (QAOA) applied to max-cut problems. Within our black-box optimization framework, BO achieves competitive solutions while requiring significantly fewer quantum circuit evaluations compared to standard non-Bayesian global optimizers. These results highlight the potential of BO to enhance both the efficiency and the overall performance of variational quantum algorithms.

Jan 1, 20250 citations

Quantum Approximate Optimisation Applied to Graph Similarity

Nicholas Pritchard

Quantum computing promises solutions to classically difficult and new-found problems through controlling the subtleties of quantum computing. The Quantum Approximate Optimisation Algorithm (QAOA) is a recently proposed quantum algorithm designed to tackle difficult combinatorial optimisation problems utilising both quantum and classical computation. The hybrid nature, generality and typically low gate-depth make it a strong candidate for near-term implementation in quantum computing. Finding the practical limits of the algorithm is currently an open problem. Until now, no tools to facilitate the design and validation of probabilistic quantum optimisation algorithms such as the QAOA on a non-trivial scale exist. Graph similarity is a long standing classically difficult problem withstanding decades of research from academia and industry. Determining the maximal edge overlap between all possible node label permutations is an NP-Complete task and provides an apt measure of graph similarity. We introduce a novel quantum optimisation simulation package facilitating investigation of all constituent components of the QAOA from desktop to cluster scale using graph similarity as an example. Our simulation provides flexibility and performance. We investigate eight classical optimisation methods each at six levels of decomposition. Moreover an encoding for permutation based problems such as graph similarity through edge overlap to the QAOA allows for significant quantum memory savings at the cost of additional operations. This compromise extends into the classical portion of the algorithm as the inclusion of infeasible solutions creates a challenging cost-function landscape. We present performance analysis of our simulation and of the QAOA setting a precedent for investigating and validating numerous other difficult problems to the QAOA as we move towards realising practical quantum computation.

arXiv:2412.17309Dec 23, 20240 citations