On the dynamical Lie algebras of quantum approximate optimization algorithms

• URL: http://arxiv.org/abs/2407.12587v1
• Date: Wed, 17 Jul 2024 14:12:30 GMT
• Title: On the dynamical Lie algebras of quantum approximate optimization algorithms
• Authors: Jonathan Allcock, Miklos Santha, Pei Yuan, Shengyu Zhang,
• Abstract summary: Dynamical Lie algebras (DLAs) have emerged as a valuable tool in the study of parameterized quantum circuits. In this work, we investigate DLAs for the quantum approximate optimization algorithm (QAOA) We show that the dimension of the DLA is $O(n3)$ and give an explicit basis for the DLA.
• Score: 4.987686869768721
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dynamical Lie algebras (DLAs) have emerged as a valuable tool in the study of parameterized quantum circuits, helping to characterize both their expressiveness and trainability. In particular, the absence or presence of barren plateaus (BPs) -- flat regions in parameter space that prevent the efficient training of variational quantum algorithms -- has recently been shown to be intimately related to quantities derived from the associated DLA. In this work, we investigate DLAs for the quantum approximate optimization algorithm (QAOA), one of the most studied variational quantum algorithms for solving graph MaxCut and other combinatorial optimization problems. While DLAs for QAOA circuits have been studied before, existing results have either been based on numerical evidence, or else correspond to DLA generators specifically chosen to be universal for quantum computation on a subspace of states. We initiate an analytical study of barren plateaus and other statistics of QAOA algorithms, and give bounds on the dimensions of the corresponding DLAs and their centers for general graphs. We then focus on the $n$-vertex cycle and complete graphs. For the cycle graph we give an explicit basis, identify its decomposition into the direct sum of a $2$-dimensional center and a semisimple component isomorphic to $n-1$ copies of $su(2)$. We give an explicit basis for this isomorphism, and a closed-form expression for the variance of the cost function, proving the absence of BPs. For the complete graph we prove that the dimension of the DLA is $O(n^3)$ and give an explicit basis for the DLA.

Related papers

• Reductions of QAOA Induced by Classical Symmetries: Theoretical Insights and Practical Implications [0.35398689122254773]
  We show that classical symmetries can be systematically exploited as a design principle for QAOA.<n>We show that the structure of the Lie algebra can change dramatically depending on which variable is held fixed.<n>Results establish symmetry-aware reduction as a principled tool for designing expressive and potentially trainable QAOA circuits.
  arXiv  Detail & Related papers  (2026-02-18T02:20:42Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• QAOA-MaxCut has barren plateaus for almost all graphs [12.977235450329466]
  A key indicator of the expressivity and trainability of VQAs remains poorly understood beyond highly symmetric instances.<n>An exponentially scaling DLA dimension is associated with the presence of so-called barren plateaus.<n>In this work, we investigate the DLA of QAOA applied to the canonical MaxCut, for both weighted and unweighted graphs.
  arXiv  Detail & Related papers  (2025-12-31T03:02:02Z)
• Expressivity Limits in Quantum Walk-based Optimization [0.0]
  Quantum walk optimization algorithm (QWOA) is one such variational approach that has recently gained attention.<n>A key method to study this aspect involves analyzing the dimension of the dynamic Lie algebra (DLA)<n>We show that the DLA dimension dimension scales at most quadratically with a number of distinct eigenvalues of the problem Hamiltonian.
  arXiv  Detail & Related papers  (2025-08-07T18:04:20Z)
• Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions [0.6144680854063939]
  We propose an explicit, oracle-free quantum framework for numerically simulating general linear partial differential equations (PDEs)<n>Our approach begins with a general finite-difference discretization and applies the Schrodingerisation technique to transform the resulting system into one that admits unitary quantum evolution.
  arXiv  Detail & Related papers  (2025-06-25T14:23:38Z)
• The Lie Algebra of XY-mixer Topologies and Warm Starting QAOA for Constrained Optimization [0.9208007322096533]
  The XY-mixer has widespread utilization in modern quantum computing, including in variational quantum algorithms.<n>We give explicit decompositions of the dynamical Lie algebras associated with a variety of $XY$-mixer topologies.<n>We provide numerical simulations showcasing these concepts on Portfolio Optimization, Sparsest $k$-Subgraph, and Graphing problems.
  arXiv  Detail & Related papers  (2025-05-23T22:00:22Z)
• A graph-theoretic approach to chaos and complexity in quantum systems [0.4934360430803066]
  We explore, via the commutator graph, average notions of scrambling, chaos and complexity over ensembles of systems with Lie algebras. We link graph-theoretic properties of the commutator graph to the out-of-time-orderor (OTOC), the frame potential, the frustration graph of the Hamiltonian of the system, and the Krylov complexity of operators evolving under the dynamics.
  arXiv  Detail & Related papers  (2025-02-23T02:03:03Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• The Adjoint Is All You Need: Characterizing Barren Plateaus in Quantum Ans\"atze [3.2773906224402802]
  We formulate a theory of Barren Plateaus for parameterized quantum circuits whose observables lie in their Lie algebra (DLA) For the first time, our theory provides, for the first time, the ability to compute the variance of the variance of the gradient cost function of the quantum compound ansatz.
  arXiv  Detail & Related papers  (2023-09-14T17:50:04Z)
• GRAPE optimization for open quantum systems with time-dependent decoherence rates driven by coherent and incoherent controls [77.34726150561087]
  The GRadient Ascent Pulse Engineering (GRAPE) method is widely used for optimization in quantum control. We adopt GRAPE method for optimizing objective functionals for open quantum systems driven by both coherent and incoherent controls. The efficiency of the algorithm is demonstrated through numerical simulations for the state-to-state transition problem.
  arXiv  Detail & Related papers  (2023-07-17T13:37:18Z)
• Fast quantum algorithm for differential equations [0.5895819801677125]
  We present a quantum algorithm with numerical complexity that is polylogarithmic in $N$ but is independent of $kappa$ for a large class of PDEs. Our algorithm generates a quantum state that enables extracting features of the solution.
  arXiv  Detail & Related papers  (2023-06-20T18:01:07Z)
• Global optimization of MPS in quantum-inspired numerical analysis [0.0]
  The study focuses on the search for the lowest eigenstates of a Hamiltonian equation. Five algorithms are introduced: imaginary-time evolution, steepest gradient descent, an improved descent, an implicitly restarted Arnoldi method, and density matrix renormalization group (DMRG) optimization.
  arXiv  Detail & Related papers  (2023-03-16T16:03:51Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• 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)
• Experimental analysis of quantum annealers and hybrid solvers using benchmark optimization problems [0.0]
  This paper studies the Hamiltonian Cycle Problem (HCP) and the Traveling Salesman Problem (TSP) on D-Wave's quantum systems.
  arXiv  Detail & Related papers  (2022-02-17T23:46:27Z)
• 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)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning [59.71676469100807]
  This work sharpens the sample complexity of synchronous Q-learning to an order of $frac|mathcalS|| (1-gamma)4varepsilon2$ for any $0varepsilon 1$. Our finding unveils the effectiveness of vanilla Q-learning, which matches that of speedy Q-learning without requiring extra computation and storage.
  arXiv  Detail & Related papers  (2021-02-12T14:22:05Z)
• Power Normalizations in Fine-grained Image, Few-shot Image and Graph Classification [38.84294567166725]
  We study Power Normalizations (PN) in the deep learning setup via a novel PN layer pooling feature maps. We investigate the role and meaning of MaxExp and Gamma, two popular PN functions. We show that SPN on the autocorrelation/covariance matrix and the Heat Diffusion Process (HDP) on a graph Laplacian matrix are closely related.
  arXiv  Detail & Related papers  (2020-12-27T17:06:06Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)

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.