Emergent Problem-Graph Alignment in RL-Discovered Entanglement Topologies for QAOA

• URL: http://arxiv.org/abs/2608.07686v1
• Date: Fri, 07 Aug 2026 18:17:08 GMT
• Title: Emergent Problem-Graph Alignment in RL-Discovered Entanglement Topologies for QAOA
• Abstract summary: 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.
• Score: 3.03715087930992
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the Quantum Approximate Optimization Algorithm (QAOA), the entanglement topology, where qubit pairs are connected by two-qubit gates, is conventionally set equal to the edge set of the problem graph. This coupling ties circuit design to explicit problem knowledge and may not yield the most trainable circuit under limited optimization budgets. We investigate whether a reinforcement learning (RL) agent can discover more effective entanglement topologies for QAOA-based MaxCut optimization without direct access to the problem graph. A Masked Proximal Policy Optimization agent sequentially places IsingZZ gates to construct a circuit topology, while a variational inner loop optimizes the resulting QAOA parameters and returns the approximation ratio as a sparse terminal reward. The agent's observation contains only the edges placed so far and the current approximation ratio; graph structure can only be inferred indirectly through the optimization reward. On Erdős--Rényi instances with up to $10$~qubits, the agent consistently converges to topologies that are strict subsets of the problem graph, achieving overlap ratios approaching $1.0$, despite receiving no explicit information about the graph structure in its observations. These sparse, problem-aligned topologies outperform the full graph topology and several structural baselines when the optimization budget is limited ($50$~gradient steps), but are overtaken by denser topologies given sufficient optimization budget. Our results reveal a trainability--expressibility trade-off governed by topology density and suggest that the variational optimization landscape implicitly encodes structural information about the problem Hamiltonian.

Related papers

• Neural QAOA$^{2}$: Differentiable Joint Graph Partitioning and Parameter Initialization for Quantum Combinatorial Optimization [3.7086487199744127]
  We propose Neural QAOA$2$, an end-to-end differentiable framework that jointly generates graph partitions and initial parameters.<n>By integrating a generative evaluative network (GEN), our method utilizes a differentiable quantum evaluator as a high-fidelity performance surrogate.<n>Experiments on 183 QUBO, Ising, and MaxCut instances (21 to 1000 variables) demonstrate that our gradient-driven approach broadly outperforms baselines.
  arXiv  Detail & Related papers  (2026-05-13T06:43:10Z)
• On the Complexity of Optimal Graph Rewiring for Oversmoothing and Oversquashing in Graph Neural Networks [2.8427946758947304]
  Graph Neural Networks (GNNs) face two fundamental challenges when scaled to deep architectures.<n>Oversmoothing and oversquashing are intimately tied to the underlying graph structure.<n>This paper provides a theoretical investigation of the computational complexity of such graph structure optimization.
  arXiv  Detail & Related papers  (2026-03-27T07:50:42Z)
• Stability and Generalization of Push-Sum Based Decentralized Optimization over Directed Graphs [55.77845440440496]
  Push-based decentralized communication enables optimization over communication networks, where information exchange may be asymmetric.<n>We develop a unified uniform-stability framework for the Gradient Push (SGP) algorithm.<n>A key technical ingredient is an imbalance-aware generalization bound through two quantities.
  arXiv  Detail & Related papers  (2026-02-24T05:32:03Z)
• Extending QAOA-GPT to Higher-Order Quantum Optimization Problems [0.0]
  We extend QAOA-GPT to Higher-Order Unconstrained Binary Optimization problems.<n>We train the model on graph-circuit pairs generated via ADAPT-QAOA and evaluate its performance on 8- and 16-qubit instances embedded on heavy-hex lattices.<n>Results demonstrate that QAOA-GPT generalizes effectively to higher-order cost Hamiltonians and complex energy landscapes.
  arXiv  Detail & Related papers  (2025-11-10T18:46:38Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration [72.15369769265398]
  Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73%.
  arXiv  Detail & Related papers  (2022-05-27T17:13:10Z)
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
  We propose a strategy to give high approximation ratio on average, even at large circuit depths, by initializing QAOA with the optimal parameters obtained from the previous depths. We test our strategy on the Max-cut problem of certain classes of graphs such as the 3-regular graphs and the Erd"os-R'enyi graphs.
  arXiv  Detail & Related papers  (2021-08-11T15:44:16Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59: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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.