Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs

• URL: http://arxiv.org/abs/2609.03317v1
• Date: Thu, 03 Sep 2026 03:12:50 GMT
• Title: Efficient Estimation of Reduced QAOA Expressibility on Acyclic Graphs
• Abstract summary: We show how classical graph structure can be used to diagnose and potentially guide the quantum dynamics of variational algorithms.<n>Our results show how classical graph structure can be used to diagnose and potentially guide the quantum dynamics of variational algorithms before running them on quantum hardware.
• Score: 0.35398689122254773
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Classically equivalent formulations of an optimization problem need not lead to equivalent quantum algorithms. For MaxCut, fixing the value of a single vertex removes a simple global symmetry without changing the underlying optimization problem, yet it can substantially alter the quantum dynamics generated by the Quantum Approximate Optimization Algorithm (QAOA). These dynamics are captured by the circuit's dynamical Lie algebra (DLA), whose direct construction can become exponentially expensive. Here we show that, for symmetry-reduced QAOA on trees, substantial information about the reduced DLA can instead be obtained efficiently from the graph alone. We introduce a polynomial classical algorithm that recursively distinguishes vertices using shortest path structure and degree parity. When all vertices are resolved individually, the method determines the complete reduced DLA and, under the corresponding graph conditions, certifies maximal expressibility of the reduced QAOA ansatz. Even when full resolution is not achieved, the algorithm identifies embedded subalgebras, provides rigorous lower bounds on DLA dimension, and certifies controllable subsystems. Our theoretical and experimental results show how classical graph structure can be used to diagnose and potentially guide the quantum dynamics of variational algorithms before running them on quantum hardware.

Related papers

• Emergent Problem-Graph Alignment in RL-Discovered Entanglement Topologies for QAOA [3.03715087930992]
  We investigate whether a reinforcement learning agent can discover more effective entanglement topologies for QAOA-based MaxCut optimization without direct access to the problem graph.<n>Our results reveal a trainability--express trade-off governed by topology density and suggest that the variational optimization landscape implicitly encodes structural information about the problem Hamiltonian.
  arXiv  Detail & Related papers  (2026-08-07T18:17:08Z)
• Multivariate Decoded Quantum Interferometry for Weighted Optimization [6.4675604105664]
  Quantum Interferometry (DQI) reduces discrete optimization to decoding with potential advantages over the best-known analogue-time classical algorithms for certain Max-LINSAT problems.<n>In its original formulation, DQI treats all constraints uniformly and cannot exploit the weight structure present in most optimization problems of interest.
  arXiv  Detail & Related papers  (2026-05-11T14:45:46Z)
• 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)
• Scalable Quantum Walk-Based Heuristics for the Minimum Vertex Cover Problem [0.0]
  We propose a novel quantum algorithm for the Minimum Vertex Cover (MVC) problem based on continuous-time quantum walks (CTQWs)<n>In this framework, the coherent propagation of a quantum walker over a graph encodes its structural properties into state amplitudes.<n>We show that the CTQW-based algorithm consistently achieves superior approximation ratios and exhibits remarkable robustness with respect to network topology.
  arXiv  Detail & Related papers  (2025-12-02T17:04:57Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles.<n>On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach.<n>On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  We introduce the concept of textitsemi-symmetries in QUBO matrices.<n>We show that our algorithm reduces the number of couplings and circuit depth by up to $45%.
  arXiv  Detail & Related papers  (2024-12-18T12:05:18Z)
• Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
  Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid algorithm proposed with the goal of approximately solving optimization problems such as the MAX-CUT problem. We first analytically prove the performance limitations of level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. Second, we demonstrate that Recursive QAOA (RQAOA), which reduces graph size using QAOA as a subroutine, outperforms the level-1 QAOA. Finally, we show that RQAOA with a restricted parameter regime can fully address these limitations.
  arXiv  Detail & Related papers  (2024-08-23T16:35:47Z)
• On the dynamical Lie algebras of quantum approximate optimization algorithms [4.987686869768721]
  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.
  arXiv  Detail & Related papers  (2024-07-17T14:12:30Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations [59.84561168501493]
  We introduce new generalized data reduction and transformation rules for the maximum weight independent set problem. Surprisingly, these so-called increasing transformations can simplify the problem and also open up the reduction space to yield even smaller irreducible graphs later in the algorithm. Our algorithm computes significantly smaller irreducible graphs on all except one instance, solves more instances to optimality than previously possible, is up to two orders of magnitude faster than the best state-of-the-art solver, and finds higher-quality solutions than solvers DynWVC and HILS.
  arXiv  Detail & Related papers  (2020-08-12T08:52:50Z)

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.