Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

1-2026

Abstract

Graph shrinking has recently emerged as a powerful preprocessing technique for hybrid classical–quantum optimization, enabling variable and constraint reduction before quantum solving. Conventional approaches rely on Semi-Definite Programming (SDP) relaxations to compute vertex correlations, but these methods suffer from high computational overhead, instance-specific tuning, and limited generalizability. In this work, we replace the handcrafted SDP correlation stage with a reinforcement learning (RL) based correlation estimator, trained to predict merge quality directly from graph structure. We reformulate the graph shrinking process as a Markov Decision Process (MDP), design a Graph Neural Network (GNN) policy to guide vertex merging, and integrate the learned correlations into a hybrid classical–quantum pipeline. Experiments on benchmark problems, including the Maximum Independent Set (MIS) and Multi-Dimensional Knapsack Problem (MDKP), demonstrate that our Learned Graph Shrinking (LGS) achieves comparable or superior solution quality to SDP-guided and random baselines, while reducing qubit requirements by up to 35%. These results highlight the potential of learning-based correlation estimation as a scalable and general alternative to classical relaxations for quantum optimization.

Keywords

Graph Shrinking, Hybrid Quantum-Classical Computing, Quantum Optimization, QUBO, Reinforcement Learning, Variational Quantum Eigensolver

Discipline

Numerical Analysis and Scientific Computing | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

Quantum Computing and Artificial Intelligence: 2nd International Workshop, QC+AI 2026, Singapore, January 27: Proceedings

Volume

2872

First Page

347

Last Page

49

ISBN

9783032176240

Identifier

10.1007/978-3-032-17625-7_3

Publisher

Springer

City or Country

Cham

Additional URL

https://doi.org/10.1007/978-3-032-17625-7_3

Download

Share

COinS