Emergent problem-graph alignment in RL-discovered entanglement topologies for QAOA

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 are consistent with the hypothesis that, in the small-scale setting studied, the variational optimization landscape implicitly encodes structural information about the problem Hamiltonian.