Neural QAOA$^2$: Differentiable Joint Graph Partitioning and Parameter Initialization for Quantum Combinatorial Optimization

The quantum approximate optimization algorithm (QAOA) holds promise for combinatorial optimization but is constrained by limited qubits. While divide-and-conquer frameworks like QAOA$^2$ address scalability by partitioning graphs into subgraphs, existing methods suffer from two fundamental limitations: i) misalignment between heuristic partitioning metrics and quantum optimization goals, and ii) topology-blind parameter initialization that leads to optimization cold starts. To bridge these gaps, we propose **Neural QAOA$^2$**, an end-to-end differentiable framework that jointly generates graph partitions and initial parameters. By integrating a generative evaluative network (GEN), our method utilizes a differentiable quantum evaluator as a high-fidelity performance surrogate to provide direct gradient guidance, enabling the joint generator to learn the intrinsic mapping from graph topology to high-quality partition and parameter configurations. Extensive experiments on 183 QUBO, Ising, and MaxCut instances (21 to 1000 variables) demonstrate that our gradient-driven approach broadly outperforms heuristic baselines, ranking first on 101 instances. It exhibits zero-shot generalization across out-of-distribution graph topologies and scales.

Combinatorial optimization problems are everywhere in science and industry, but they are too large for today’s quantum computers to solve directly. A promising quantum method called the quantum approximate optimization algorithm (QAOA) can tackle them, but its performance is limited by the small number of available qubits. To overcome this limitation, researchers often split a large problem into smaller pieces and solve them separately. However, existing approaches rely on hand-designed rules that may not align well with quantum optimization goals. They also struggle to choose good starting parameters, which can slow down optimization and reduce solution quality. We propose **Neural QAOA$^2$**, a learning-based framework that automatically learns both how to divide problems and how to initialize quantum optimization parameters. Our method includes a trainable scoring module that predicts which problem splits and parameter choices are likely to work well before running the full quantum optimization. Across 183 benchmark problems with up to 1000 variables, our approach broadly outperforms existing hand-designed methods and achieves the best results on most instances. It also generalizes well to previously unseen graph types and larger problem sizes without retraining.