Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2405.08941

Parameter optimization comparison in QAOA using Stochastic Hill Climbing with Random Re-starts and Local Search with entangled and non-entangled mixing operators

Brian García Sarmina, Guo-Hua Sun, Shi‐Hai Dong

Published May 14, 2024• 0 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2405.08941

Related papers

Probing entanglement and parameter sensitivity in QAOA via Quantum Fisher Information

Brian García Sarmina, Jorge Saavedra Benavides, Guo-Hua Sun +1 more

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.

arXiv:2507.18844•Quantum Review Letters•Dec 12, 2025•0 citations

Principal Component Analysis and t-Distributed Stochastic Neighbor Embedding Analysis in the Study of Quantum Approximate Optimization Algorithm Entangled and Non-Entangled Mixing Operators

Brian García Sarmina, Guo-Hua Sun, Shi‐Hai Dong

In this paper, we employ PCA and t-SNE analyses to gain deeper insights into the behavior of entangled and non-entangled mixing operators within the Quantum Approximate Optimization Algorithm (QAOA) at various depths. We utilize a dataset containing optimized parameters generated for max-cut problems with cyclic and complete configurations. This dataset encompasses the resulting RZ, RX, and RY parameters for QAOA models at different depths (1L, 2L, and 3L) with or without an entanglement stage within the mixing operator. Our findings reveal distinct behaviors when processing the different parameters with PCA and t-SNE. Specifically, most of the entangled QAOA models demonstrate an enhanced capacity to preserve information in the mapping, along with a greater level of correlated information detectable by PCA and t-SNE. Analyzing the overall mapping results, a clear differentiation emerges between entangled and non-entangled models. This distinction is quantified numerically through explained variance in PCA and Kullback-Leibler divergence (post-optimization) in t-SNE. These disparities are also visually evident in the mapping data produced by both methods, with certain entangled QAOA models displaying clustering effects in both visualization techniques.

arXiv:2306.11060•Entropy•Oct 30, 2023•19 citations

Mechanism of Efficacy in QAOA for Random k-SAT: From Adiabatic Manifold to Sublinear Parameter Optimization

Mingyou Wu, Hanwu Chen

The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for demonstrating quantum advantage on near-term devices, yet the physical origins of its efficacy remain poorly understood. In this work, we study QAOA for random $k$-SAT problems within a universal-mixer $k$-local search framework, establishing a formal correspondence between adiabatic state transfer and the QAOA ansatz. This correspondence yields a rigorous performance guarantee for random instances with clause density $m=O(n^{1+ε})$ and circuit depth $Θ(n^2)$. We further investigate the NISQ regime with shallow circuits of depth $p=O(n)$. Surprisingly, the optimal parameters do not become stochastic under depth compression, but instead remain confined to a structured low-dimensional region, which we identify as a smooth adiabatic manifold. Numerical evidence indicates that this manifold persists across different circuit depths and arises from the variational suppression of adiabatic leakage. Based on this structure, we propose the smooth adiabatic-manifold parameterization (SAMP) strategy, transforming parameter optimization from an unstructured high-dimensional search into a guided refinement process. Numerical experiments on random 3-SAT instances show that SAMP achieves sublinear optimization scaling with circuit depth while providing robust zero-cost initialization for deep circuits.

quant-pharXiv:2605.20288•May 20, 2026•0 citations

Parameter Determination of Quantum Approximate Optimization Algorithm Using Layerwise Grid Search Method

Su‐Ling Lee, Chien‐Cheng Tseng

The quantum approximate optimization algorithm (QAOA) is an efficient method for solving combinatorial optimization problems in quantum computing. These problems involve finding the best solution from a finite set of possibilities. At its core, the QAOA uses an Ansatz circuit composed of alternating unitary operators, the mixing and problem Hamiltonians, that are controlled by a set of parameters. Its goal is to find the optimal parameters so that the final quantum state of the circuit encodes the problem’s solution. While this parameter optimization is often handled by classical optimizers, including constrained optimization by linear approximations (COBYLA) and Nelder–Mead, these methods frequently present local extrema. Therefore, we developed a layerwise grid search (LGS) method as an alternative. Since a full grid search is too time-consuming, the LGS method significantly reduces the search time while still finding a good solution. To demonstrate its effectiveness, we present experimental results for the max-cut problem, comparing the performance of our LGS method against conventional classical optimizers.

IEEE Eurasia Conference on IOT, Communication and Engineering (ECICE)•Apr 22, 2026•0 citations

Quantum approximate optimization algorithm for MaxCut: A fermionic view

Zhihui Wang, Stuart Hadfield, Jiang Zhang +1 more

Farhi et al. recently proposed a class of quantum algorithms, the quantum approximate optimization algorithm (QAOA), for approximately solving combinatorial optimization problems (E. Farhi et al., arXiv:1411.4028; arXiv:1412.6062; arXiv:1602.07674). A level-$p$ QAOA circuit consists of $p$ steps; in each step a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The $2p$ times for which these two Hamiltonians are applied are the parameters of the algorithm, which are to be optimized classically for the best performance. As $p$ increases, parameter optimization becomes inefficient due to the curse of dimensionality. The success of the QAOA approach will depend, in part, on finding effective parameter-setting strategies. Here we analytically and numerically study parameter setting for the QAOA applied to MaxCut. For the level-1 QAOA, we derive an analytical expression for a general graph. In principle, expressions for higher $p$ could be derived, but the number of terms quickly becomes prohibitive. For a special case of MaxCut, the ``ring of disagrees,'' or the one-dimensional antiferromagnetic ring, we provide an analysis for an arbitrarily high level. Using a fermionic representation, the evolution of the system under the QAOA translates into quantum control of an ensemble of independent spins. This treatment enables us to obtain analytical expressions for the performance of the QAOA for any $p$. It also greatly simplifies the numerical search for the optimal values of the parameters. By exploring symmetries, we identify a lower-dimensional submanifold of interest; the search effort can be accordingly reduced. This analysis also explains an observed symmetry in the optimal parameter values. Further, we numerically investigate the parameter landscape and show that it is a simple one in the sense of having no local optima.

arXiv:1706.02998•Physical Review A•Feb 5, 2018•351 citations

Linearly simplified QAOA parameters and transferability

Ryo Sakai, Hiromichi Matsuyama, Wai-Hong Tam +2 more

Quantum Approximate Optimization Algorithm (QAOA) provides a way to solve combinatorial optimization problems using quantum computers. QAOA circuits consist of time evolution operators by the cost Hamiltonian and of state mixing operators, and embedded variational parameter for each operator is tuned so that the expectation value of the cost function is minimized. The optimization of the variational parameters is taken place on classical devices while the cost function is measured in the sense of quantum. To facilitate the classical optimization, there are several previous works on making decision strategies for optimal/initial parameters and on extracting similarities among instances. In our current work, we consider simplified QAOA parameters that take linear forms along with the depth in the circuit. Such a simplification, which would be suggested from an analogy to quantum annealing, leads to a drastic reduction of the parameter space from 2p to 4 dimensions with the any number of QAOA layers p. In addition, cost landscapes in the reduced parameter space have some stability on differing instances. This fact suggests that an optimal parameter set for a given instance can be transferred to other instances. In this paper we present some numerical results that are obtained for instances of the random Ising model and of the max-cut problem. The transferability of linearized parameters is demonstrated for randomly generated source and destination instances, and its dependence on features of the instances are investigated.

arXiv:2405.00655•May 1, 2024•0 citations
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 1L1L1L to 3L3L3L. These models incorporate diverse mixing operator configurations, which integrate RXRXRX and RYRYRY 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.
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.
In this paper, we employ PCA and t-SNE analyses to gain deeper insights into the behavior of entangled and non-entangled mixing operators within the Quantum Approximate Optimization Algorithm (QAOA) at various depths. We utilize a dataset containing optimized parameters generated for max-cut problems with cyclic and complete configurations. This dataset encompasses the resulting RZ, RX, and RY parameters for QAOA models at different depths (1L, 2L, and 3L) with or without an entanglement stage within the mixing operator. Our findings reveal distinct behaviors when processing the different parameters with PCA and t-SNE. Specifically, most of the entangled QAOA models demonstrate an enhanced capacity to preserve information in the mapping, along with a greater level of correlated information detectable by PCA and t-SNE. Analyzing the overall mapping results, a clear differentiation emerges between entangled and non-entangled models. This distinction is quantified numerically through explained variance in PCA and Kullback-Leibler divergence (post-optimization) in t-SNE. These disparities are also visually evident in the mapping data produced by both methods, with certain entangled QAOA models displaying clustering effects in both visualization techniques.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate for demonstrating quantum advantage on near-term devices, yet the physical origins of its efficacy remain poorly understood. In this work, we study QAOA for random kkk-SAT problems within a universal-mixer kkk-local search framework, establishing a formal correspondence between adiabatic state transfer and the QAOA ansatz. This correspondence yields a rigorous performance guarantee for random instances with clause density m=O(n1+ε)m=O(n^{1+ε})m=O(n1+ε) and circuit depth Θ(n2)Θ(n^2)Θ(n2). We further investigate the NISQ regime with shallow circuits of depth p=O(n)p=O(n)p=O(n). Surprisingly, the optimal parameters do not become stochastic under depth compression, but instead remain confined to a structured low-dimensional region, which we identify as a smooth adiabatic manifold. Numerical evidence indicates that this manifold persists across different circuit depths and arises from the variational suppression of adiabatic leakage. Based on this structure, we propose the smooth adiabatic-manifold parameterization (SAMP) strategy, transforming parameter optimization from an unstructured high-dimensional search into a guided refinement process. Numerical experiments on random 3-SAT instances show that SAMP achieves sublinear optimization scaling with circuit depth while providing robust zero-cost initialization for deep circuits.
The quantum approximate optimization algorithm (QAOA) is an efficient method for solving combinatorial optimization problems in quantum computing. These problems involve finding the best solution from a finite set of possibilities. At its core, the QAOA uses an Ansatz circuit composed of alternating unitary operators, the mixing and problem Hamiltonians, that are controlled by a set of parameters. Its goal is to find the optimal parameters so that the final quantum state of the circuit encodes the problem’s solution. While this parameter optimization is often handled by classical optimizers, including constrained optimization by linear approximations (COBYLA) and Nelder–Mead, these methods frequently present local extrema. Therefore, we developed a layerwise grid search (LGS) method as an alternative. Since a full grid search is too time-consuming, the LGS method significantly reduces the search time while still finding a good solution. To demonstrate its effectiveness, we present experimental results for the max-cut problem, comparing the performance of our LGS method against conventional classical optimizers.
Farhi et al. recently proposed a class of quantum algorithms, the quantum approximate optimization algorithm (QAOA), for approximately solving combinatorial optimization problems (E. Farhi et al., arXiv:1411.4028; arXiv:1412.6062; arXiv:1602.07674). A level-ppp QAOA circuit consists of ppp steps; in each step a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The 2p2p2p times for which these two Hamiltonians are applied are the parameters of the algorithm, which are to be optimized classically for the best performance. As ppp increases, parameter optimization becomes inefficient due to the curse of dimensionality. The success of the QAOA approach will depend, in part, on finding effective parameter-setting strategies. Here we analytically and numerically study parameter setting for the QAOA applied to MaxCut. For the level-1 QAOA, we derive an analytical expression for a general graph. In principle, expressions for higher ppp could be derived, but the number of terms quickly becomes prohibitive. For a special case of MaxCut, the ``ring of disagrees,'' or the one-dimensional antiferromagnetic ring, we provide an analysis for an arbitrarily high level. Using a fermionic representation, the evolution of the system under the QAOA translates into quantum control of an ensemble of independent spins. This treatment enables us to obtain analytical expressions for the performance of the QAOA for any ppp. It also greatly simplifies the numerical search for the optimal values of the parameters. By exploring symmetries, we identify a lower-dimensional submanifold of interest; the search effort can be accordingly reduced. This analysis also explains an observed symmetry in the optimal parameter values. Further, we numerically investigate the parameter landscape and show that it is a simple one in the sense of having no local optima.
Quantum Approximate Optimization Algorithm (QAOA) provides a way to solve combinatorial optimization problems using quantum computers. QAOA circuits consist of time evolution operators by the cost Hamiltonian and of state mixing operators, and embedded variational parameter for each operator is tuned so that the expectation value of the cost function is minimized. The optimization of the variational parameters is taken place on classical devices while the cost function is measured in the sense of quantum. To facilitate the classical optimization, there are several previous works on making decision strategies for optimal/initial parameters and on extracting similarities among instances. In our current work, we consider simplified QAOA parameters that take linear forms along with the depth in the circuit. Such a simplification, which would be suggested from an analogy to quantum annealing, leads to a drastic reduction of the parameter space from 2p to 4 dimensions with the any number of QAOA layers p. In addition, cost landscapes in the reduced parameter space have some stability on differing instances. This fact suggests that an optimal parameter set for a given instance can be transferred to other instances. In this paper we present some numerical results that are obtained for instances of the random Ising model and of the max-cut problem. The transferability of linearized parameters is demonstrated for randomly generated source and destination instances, and its dependence on features of the instances are investigated.