Provable avoidance of barren plateaus for the Quantum Approximate Optimization Algorithm with Grover mixers

• URL: http://arxiv.org/abs/2509.10424v2
• Date: Fri, 10 Oct 2025 00:40:21 GMT
• Title: Provable avoidance of barren plateaus for the Quantum Approximate Optimization Algorithm with Grover mixers
• Authors: Boris Tsvelikhovskiy, Matthew Nuyten, Bojko N. Bakalov,
• Abstract summary: We analyze the Lie algebras associated with the Grover-mixer variant of the Quantum Approximate Optimization Algorithm (GM-QAOA)<n>We prove that the DLA of GM-QAOA has the largest possible commutant among all QAOA variants with the same state, corresponding physically to the maximal set of conserved quantities.
• Score: 0.764671395172401
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We analyze the dynamical Lie algebras (DLAs) associated with the Grover-mixer variant of the Quantum Approximate Optimization Algorithm (GM-QAOA). When the initial state is the uniform superposition of computational basis states, we show that the corresponding DLA is isomorphic to $\mathfrak{su}(d) \oplus \mathfrak{u}(1)\oplus \mathfrak{u}(1)$, where $d$ denotes the number of distinct values of the objective function. We also establish an analogous result for other choices of initial states and Grover-type mixers. Furthermore, we prove that the DLA of GM-QAOA has the largest possible commutant among all QAOA variants initialized with the same state, corresponding physically to the maximal set of conserved quantities. We derive an explicit formula for the variance of the GM-QAOA loss function in terms of the objective function values, and we show that for a broad class of optimization problems, GM-QAOA with sufficiently many layers avoids barren plateaus.

Related papers

• Applying Grover-mixer Quantum Alternating Operator Ansatz Algorithm to High-order Unconstrained Binary Optimization Problems [0.21847754147782883]
  Grover-mixer variant (GM-QAOA) offers compelling alternative due to its global search capabilities.<n>We present a numerical study demonstrating that GM-QAOA, unlike XM-QAOA, exhibits monotonic performance improvement with circuit depth.
  arXiv  Detail & Related papers  (2025-12-28T18:01:20Z)
• A Fresh Look at Generalized Category Discovery through Non-negative Matrix Factorization [83.12938977698988]
  Generalized Category Discovery (GCD) aims to classify both base and novel images using labeled base data. Current approaches inadequately address the intrinsic optimization of the co-occurrence matrix $barA$ based on cosine similarity. We propose a Non-Negative Generalized Category Discovery (NN-GCD) framework to address these deficiencies.
  arXiv  Detail & Related papers  (2024-10-29T07:24:11Z)
• Performance Upper Bound of Grover-Mixer Quantum Alternating Operator Ansatz [3.5023108034606256]
  The Quantum Alternating Operator Ansatz (QAOA) represents a branch of quantum algorithms for solving optimization problems. A specific variant, the Grover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA), ensures uniform amplitude across states that share equivalent objective values. We show that the GM-QAOA provides a quadratic enhancement in sampling probability and requires circuit depth that scales exponentially with problem size to maintain consistent performance.
  arXiv  Detail & Related papers  (2024-05-06T05:47:27Z)
• Dynamical System Identification, Model Selection and Model Uncertainty Quantification by Bayesian Inference [0.8388591755871735]
  This study presents a Bayesian maximum textitaposteriori (MAP) framework for dynamical system identification from time-series data.
  arXiv  Detail & Related papers  (2024-01-30T12:16:52Z)
• Analytical results for the Quantum Alternating Operator Ansatz with Grover Mixer [0.0]
  We introduce a statistical approach to analyze GM-QAOA that results in an analytical expression for the expectation value depending on the probability distribution associated with the problem Hamiltonian spectrum. We extend the analysis to a more general context of QAOA with Grover mixer, which we called Grover-based QAOA.
  arXiv  Detail & Related papers  (2024-01-19T23:17:08Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  We propose IAC (Instance-Adaptive Clustering), the first algorithm whose performance matches the instance-specific lower bounds both in expectation and with high probability.<n>IAC maintains an overall computational complexity of $ mathcalO(n, textpolylog(n) $, making it scalable and practical for large-scale problems.
  arXiv  Detail & Related papers  (2023-06-18T08:46:06Z)
• Optimal Extragradient-Based Bilinearly-Coupled Saddle-Point Optimization [116.89941263390769]
  We consider the smooth convex-concave bilinearly-coupled saddle-point problem, $min_mathbfxmax_mathbfyF(mathbfx) + H(mathbfx,mathbfy)$, where one has access to first-order oracles for $F$, $G$ as well as the bilinear coupling function $H$. We present a emphaccelerated gradient-extragradient (AG-EG) descent-ascent algorithm that combines extragrad
  arXiv  Detail & Related papers  (2022-06-17T06:10:20Z)
• General Hamiltonian Representation of ML Detection Relying on the Quantum Approximate Optimization Algorithm [74.6114458993128]
  The quantum approximate optimization algorithm (QAOA) conceived for solving optimization problems can be run on the existing noisy intermediate-scale quantum (NISQ) devices. We solve the maximum likelihood (ML) detection problem for general constellations by appropriately adapting the QAOA. In particular, for an M-ary Gray-mapped quadrature amplitude modulation (MQAM) constellation, we show that the specific qubits encoding the in-phase components and those encoding the quadrature components are independent in the quantum system of interest.
  arXiv  Detail & Related papers  (2022-04-11T14:11:24Z)
• Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization [50.83356836818667]
  gradient Langevin Dynamics is one of the most fundamental algorithms to solve non-eps optimization problems. In this paper, we show two variants of this kind, namely the Variance Reduced Langevin Dynamics and the Recursive Gradient Langevin Dynamics.
  arXiv  Detail & Related papers  (2022-03-30T11:39:00Z)
• A Variational Inference Approach to Inverse Problems with Gamma Hyperpriors [60.489902135153415]
  This paper introduces a variational iterative alternating scheme for hierarchical inverse problems with gamma hyperpriors. The proposed variational inference approach yields accurate reconstruction, provides meaningful uncertainty quantification, and is easy to implement.
  arXiv  Detail & Related papers  (2021-11-26T06:33:29Z)
• Threshold-Based Quantum Optimization [0.0]
  Th-QAOA (pronounced Threshold QAOA) is a variation of the Quantum Alternating Operator Ansatz (QAOA) We focus on a combination with the Grover Mixer operator; the resulting GM-Th-QAOA can be viewed as a generalization of Grover's quantum search algorithm.
  arXiv  Detail & Related papers  (2021-06-25T19:36:49Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Cauchy-Schwarz Regularized Autoencoder [68.80569889599434]
  Variational autoencoders (VAE) are a powerful and widely-used class of generative models. We introduce a new constrained objective based on the Cauchy-Schwarz divergence, which can be computed analytically for GMMs. Our objective improves upon variational auto-encoding models in density estimation, unsupervised clustering, semi-supervised learning, and face analysis.
  arXiv  Detail & Related papers  (2021-01-06T17:36:26Z)
• High-Dimensional Quadratic Discriminant Analysis under Spiked Covariance Model [101.74172837046382]
  We propose a novel quadratic classification technique, the parameters of which are chosen such that the fisher-discriminant ratio is maximized. Numerical simulations show that the proposed classifier not only outperforms the classical R-QDA for both synthetic and real data but also requires lower computational complexity.
  arXiv  Detail & Related papers  (2020-06-25T12:00:26Z)
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation [0.0]
  We propose a variation of the Quantum Alternating Operator Ansatz (QAOA) that uses Grover-like selective phase shift mixing operators. GM-QAOA works on any NP optimization problem for which it is possible to efficiently prepare an equal superposition of all feasible solutions.
  arXiv  Detail & Related papers  (2020-05-30T20:24:53Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.