Variational Quantum Algorithms (VQAs) are leading candidates for achieving near-term quantum advantage, yet important questions remain regarding parameter relevance and the role of entanglement in shaping their behavior. In this work, we employ the Quantum Fisher Information (QFI) as a diagnostic tool to quantify the sensitivity and correlations of QAOA states with respect to parameter variations. We study Max-Cut on cyclic and complete graphs, as well as random Ising model (RIM) instances, comparing RX-only and hybrid RX-RY mixers up to depth ( ) with optional entanglement stages and patterns. Across problem classes, complete-graph Max-Cut instances generate substantially larger QFI eigenvalues and covariance fractions than cyclic ones, exceeding the shot-noise scaling ( ) while remaining below the Heisenberg limit ( ). Entanglement primarily amplifies cross-parameter correlations, and its benefits saturate rapidly: the first entangling stage produces the dominant increase in QFI, while additional stages often yield diminishing or even adverse returns. A key methodological contribution of this work is the use of averaged QFI matrices over random parameter samples, which exposes robust global trends and reveals strongly non-uniform parameter relevance across architectures and depths. Leveraging these insights, we propose a QFI-Informed Mutation (QIm) heuristic that adapts mutation probabilities and step sizes using diagonal QFI entries. QIm improves convergence and stability over uniform and random-restart baselines, especially at large depths and in RIM landscapes. In general, our results position QFI as both a structural probe of QAOA ansätze and a practical resource to guide the design of effective optimization strategies in the NISQ regime.
Variational Quantum Algorithms (VQAs) are leading candidates for achieving near-term quantum advantage, yet important questions remain regarding parameter relevance and the role of entanglement in shaping their behavior. In this work, we employ the Quantum Fisher Information (QFI) as a diagnostic tool to quantify the sensitivity and correlations of QAOA states with respect to parameter variations. We study Max-Cut on cyclic and complete graphs, as well as random Ising model (RIM) instances, comparing RX-only and hybrid RX-RY mixers up to depth ( ) with optional entanglement stages and patterns. Across problem classes, complete-graph Max-Cut instances generate substantially larger QFI eigenvalues and covariance fractions than cyclic ones, exceeding the shot-noise scaling ( ) while remaining below the Heisenberg limit ( ). Entanglement primarily amplifies cross-parameter correlations, and its benefits saturate rapidly: the first entangling stage produces the dominant increase in QFI, while additional stages often yield diminishing or even adverse returns. A key methodological contribution of this work is the use of averaged QFI matrices over random parameter samples, which exposes robust global trends and reveals strongly non-uniform parameter relevance across architectures and depths. Leveraging these insights, we propose a QFI-Informed Mutation (QIm) heuristic that adapts mutation probabilities and step sizes using diagonal QFI entries. QIm improves convergence and stability over uniform and random-restart baselines, especially at large depths and in RIM landscapes. In general, our results position QFI as both a structural probe of QAOA ansätze and a practical resource to guide the design of effective optimization strategies in the NISQ regime.
This study investigates the efficacy of Stochastic Hill Climbing with Random Restarts (SHC-RR) compared to Local Search (LS) strategies within the Quantum Approximate Optimization Algorithm (QAOA) framework across various problem models. Employing uniform parameter settings, including the number of restarts and SHC steps, we analyze LS with two distinct perturbation operations: multiplication and summation. Our comparative analysis encompasses multiple versions of max-cut and random Ising model (RI) problems, utilizing QAOA models with depths ranging from 1L to 3L. These models incorporate diverse mixing operator configurations, which integrate RX and RY gates, and explore the effects of an entanglement stage within the mixing operator. Our results consistently show that SHC-RR outperforms LS approaches, showcasing superior efficacy despite its ostensibly simpler optimization mechanism. Furthermore, we observe that the inclusion of entanglement stages within mixing operators significantly impacts model performance, either enhancing or diminishing results depending on the specific problem context.
Structured variational quantum algorithms such as the Quantum Approximate Optimisation Algorithm (QAOA) have emerged as leading candidates for exploiting advantages of near-term quantum hardware. They interlace classical computation, in particular optimisation of variational parameters, with quantum-specific routines, and combine problem-specific advantages -- sometimes even provable -- with adaptability to the constraints of noisy, intermediate-scale quantum (NISQ) devices. While circuit depth can be parametrically increased and is known to improve performance in an ideal (noiseless) setting, on realistic hardware greater depth exacerbates noise: The overall quality of results depends critically on both, variational parameters and circuit depth. Although identifying optimal parameters is NP-hard, prior work has suggested that they may exhibit regular, predictable patterns for increasingly deep circuits and depending on the studied class of problems. In this work, we systematically investigate the role of classical parameters in QAOA performance through extensive numerical simulations and suggest a simple, yet effective heuristic scheme to find good parameters for low-depth circuits. Our results demonstrate that: (i) high-quality parameters often deviate substantially from expected patterns; (ii) QAOA performance becomes progressively less sensitive to specific parameter choices as depth increases; and (iii) iterative component-wise fixing performs on par with, and at shallow depth may even outperform, several established parameter-selection strategies. We identify conditions under which structured parameter patterns emerge, and when deviations from the patterns warrant further consideration. These insights for low-depth circuits may inform more robust pathways to harnessing QAOA in realistic quantum computing scenarios.
Many classical optimization problems can be mapped to finding the ground states of diagonal Ising Hamiltonians, for which variational quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) provide heuristic methods. Because the solutions of such classical optimization problems are necessarily product states, it is unclear how entanglement affects their performance. An Adaptive Derivative-Assembled Problem-Tailored (ADAPT) variation of QAOA improves the convergence rate by allowing entangling operations in the mixer layers whereas it requires fewer CNOT gates in the entire circuit. In this work, we study the entanglement generated during the execution of ADAPT-QAOA. Through simulations of the weighted Max-Cut problem, we show that ADAPT-QAOA exhibits substantial flexibility in entangling and disentangling qubits. By incrementally restricting this flexibility, we find that a larger amount of entanglement entropy at earlier stages coincides with faster convergence at later stages. In contrast, while the standard QAOA quickly generates entanglement within a few layers, it cannot remove excess entanglement efficiently. Our results demonstrate that the role of entanglement in quantum optimization is subtle and provide guidance for building favorable features into quantum optimization algorithms.
Entanglement is widely regarded as a key resource underlying the power of quantum algorithms and their potential to achieve quantum advantage. With the emergence of variational quantum algorithms, however, questions have arisen regarding how entanglement relates to problem structure and algorithmic performance in near-term quantum applications. Here, we examine this relationship through the Quantum Approximate Optimization Algorithm (QAOA), a specific class of variational algorithms, applied to the MaxCut problem. We show that suboptimal variational parameter training can significantly modify the observed entanglement profile, obscuring its scaling behavior. By employing a high-performance optimizer, we find empirical evidence that QAOA exhibits entanglement scaling consistent with that of fermionic Gaussian states (up to a scaling factor) across a broad range of MaxCut instances. We further compare these results with adiabatic quantum computation, observing annealing-schedule-dependent entanglement profiles whose scaling behavior differs markedly from that of QAOA. Together, these findings provide new insight into how entanglement manifests in and distinguishes these two algorithmic paradigms, highlighting its connection to both computational performance and problem structure.
In recent years, Variational Quantum Algorithms (VQAs) have emerged as a promising approach for solving optimization problems on quantum computers in the NISQ era. However, one limitation of VQAs is their reliance on fixed-structure circuits, which may not be taylored for specific problems or hardware configurations. A leading strategy to address this issue are Adaptative VQAs, which dynamically modify the circuit structure by adding and removing gates, and optimize their parameters during the training. Several Adaptative VQAs, based on heuristics such as circuit shallowness, entanglement capability and hardware compatibility, have already been proposed in the literature, but there is still lack of a systematic comparison between the different methods. In this paper, we aim to fill this gap by analyzing three Adaptative VQAs: Evolutionary Variational Quantum Eigensolver (EVQE), Variable Ansatz (VAns), already proposed in the literature, and Random Adapt-VQE (RA-VQE), a random approach we introduce as a baseline. In order to compare these algorithms to traditional VQAs, we also include the Quantum Approximate Optimization Algorithm (QAOA) in our analysis. We apply these algorithms to QUBO problems and study their performance by examining the quality of the solutions found and the computational times required. Additionally, we investigate how the choice of the hyperparameters can impact the overall performance of the algorithms, highlighting the importance of selecting an appropriate methodology for hyperparameter tuning. Our analysis sets benchmarks for Adaptative VQAs designed for near-term quantum devices and provides valuable insights to guide future research in this area.
The quantum approximate optimization algorithm (QAOA) is widely recognized for its potential to deliver quantum advantage in combinatorial optimization tasks. As a hybrid classical-quantum algorithm, it achieves an approximate solution to the combinatorial optimization problem by preparing a specific quantum state via a classical optimization of the quantum circuit parameters. A key property of QAOA is the observed concentration and transferability of optimal parameters across distinct problem instances, linked to local graph characteristics such as subgraph types (lightcones) and node degrees (parity) [1]. However, quantum noise poses a critical challenge in the current NISQ era, hindering the performance of QAOA, particularly for large system sizes. In this follow-up study, we investigate the resilience of parameter transferability under noisy conditions. Leveraging zero-noise extrapolation (ZNE), we evaluate the transferability's robustness across various random graphs under different noise levels. Our analysis reveals that the transferability of optimal parameters from smaller ‘donor’ graphs to larger ‘acceptor’ graphs retains its effectiveness, even under substantial noise when combined with ZNE. Importantly, by illustrating that QAOA parameter transferability can still be exploited effectively among NISQ devices, we offer a pragmatic approach to enhance the algorithm's performance. Our research reinforces the promise of QAOA for large-scale applications under the practical challenges of quantum noise.