Beyond QAOA: A Review of AI and Quantum Computing for Adaptive Combinatorial Optimization

Hoong Chuin LAU

quant-phOct 8, 2026

Beyond QAOA: A Review of AI and Quantum Computing for Adaptive Combinatorial Optimization

Authors: Hoong Chuin LAU

Organizations: School of Computing and Information Systems, Singapore Management University, Singapore

Abstract

Near-term quantum approaches to combinatorial optimization are limited by qubit counts, circuit fidelity, sampling cost, and the difficulty of encoding constraints, while machine learning is increasingly used to configure and control quantum optimization workflows. We call such workflows adaptive: decisions conventionally fixed in advance, from formulation and penalties to shot budgets, backends, and whether to invoke a quantum processor at all, are made by learned policies that respond to the instance, the progress of the solve, or the hardware. This review examines three paradigms, AI for quantum optimization, quantum for AI-driven optimization, and AI-quantum co-optimization, and organizes the literature by the decision being learned rather than by application. A structured review of 119 papers, 67 coded in detail, shows that the evidence is considerably stronger for AI-assisted quantum optimization than for the reverse direction: learning already reduces quantum evaluations, improves initialization, supports decomposition and penalty control, and mitigates noise, whereas evidence that quantum computation improves learned optimizers remains largely confined to small-scale simulation. Experimental controls are thin: 25 of 57 studies include no classical baseline, the quantum contribution is fully isolated in 10 of 24 studies where an ablation applies, and the median experiment uses 17 qubits. We introduce an M0-M5 evidence hierarchy, from simulation to matched-resource practical advantage, and find no broadly convincing result at the highest level. We argue that scaling is increasingly a systems problem: the question is not only whether a problem fits on a quantum processor, but how classical and quantum resources should be allocated across the optimization process. The review is aimed at researchers in quantum computing, machine learning, and operations research.

Figures & tables

Panel of Figure 1 — Figure 1: Increasing scope of learned decisions in quantum combinatorial optimization. Each stage widens what is learned (labels below each box), from a fixed quantum algorithm to policies that allocate work across heterogeneous classical and quantum resources.

Panel of Figure 2 — Figure 2: The hybrid variational loop used by QAOA and other variational quantum algorithms. The quantum processor acts as a parameterized sampler; all optimization of the parameters happens classically, using objective estimates obtained from $S$ shots.

Term	Meaning in this review	Classical analogy
Qubit	Quantum bit; one per binary decision variable in a standard QUBO mapping	Binary variable
QUBO / Ising	Unconstrained quadratic objective over binary or $\pm 1$ variables ( Equations 1 and 2 )	Quadratic 0–1 program
Hamiltonian	Operator whose energy encodes an objective; $H_{C}$ encodes the cost	Objective function
Shot	One preparation and measurement, returning one bitstring	One random sample
Circuit depth	Number of sequential gate layers	Sequential steps
Two-qubit gate	Interaction between two qubits; main error source	Costly, error-prone operation

Table 1: Glossary of quantum-computing terms used in this review, with the closest classical analogy.

Review	Primary scope	AI interventions	Q-for-AI	Workflow / evidence synthesis
Abbas et al. [ 7 ]	Quantum optimization broadly	Limited / distributed	No	Complexity, algorithms, benchmarking
Blekos et al. [ 8 ]	QAOA and variants	Parameter / variant coverage	No	Algorithm-centric
Gemeinhardt et al. [ 19 ]	NISQ combinatorial optimization	Incidental	No	Systematic mapping by problems and methods
Alexeev et al. [ 21 ]	AI across the quantum stack	Broad AI-for-quantum	Limited	Quantum-stack-centric
Martyniuk et al. [ 22 ]	Quantum architecture search	Circuit architecture	No	Search-space / strategy taxonomy
This review	AI $\times$ Quantum for combinatorial optimization	Parameters through solver policies	Yes	Pipeline taxonomy + M0–M5 evidence hierarchy

Table 2: Positioning relative to the closest review literature.

Panel of Figure 3 — Figure 3: Pipeline view of AI intervention points and execution feedback. Each stage carries the decision that is learned and the AI methods typically used ( Table 3 ). Component-level methods (AI-for-QO) act on a single stage; co-optimization methods learn a policy that coordinates several stages, conditioned on execution feedback.

Pipeline stage	Decision learned	Typical AI methods	Quantum component	Primary metric
Parameter initialization	QAOA/VQA angles	GNNs, meta-learning, clustering, diffusion	QAOA/VQA	calls, convergence, quality
Query control	next parameter point	Bayesian optimization, online surrogates	QAOA/VQA	evaluations, shots
Circuit / ansatz design	operators, gates, depth, topology	RL, differentiable NAS, transformers/LLMs	QAOA/VQA	depth, calls, quality
Formulation / penalties	QUBO coefficients, constraints	RL, learned surrogates, GNNs	QUBO for VQE, QAOA, annealing	feasibility, qubits, gap
Reduction / decomposition	subgraphs, variables, subproblems	GNNs, multilevel learning, RL	local quantum subproblems	scale, gap, width
Sampling / measurement	shots, CVaR level, recursion budget	RL, adaptive control	measurement loop	shots, confidence

Table 3: Pipeline taxonomy: the decision learned at each stage, typical AI methods, the quantum component affected, and the primary evaluation metric.

Problem family	Why it matters	Dominant AI–quantum approaches	Main bottleneck	Research opportunity
MaxCut	clean benchmark; extensive QAOA literature	parameter transfer, BO, QAS, error mitigation	benchmark saturation; no hard constraints	cross-topology and hardware transfer
MIS / clique	constraint-sensitive graph structure	recursive policies, QAOA/QRAO, learned graph models	feasibility–compression trade-offs	adaptive encoding and resource allocation
TSP	canonical sequential CO	equivariant QRL, quantum attention	all-to-all interactions; shot sensitivity	hardware-aware learned routing policies
CVRP / VRP	realistic constrained routing	decomposition, RL control, quantum local repair	$O(n^{2})$ formulations; capacity and time windows	selective quantum subproblems and repair
Knapsack / MDKP	compact but constraint-rich	QRAO, slack-free penalties, Hamiltonian QRL	inequality encoding; feasible sampling	adaptive penalty and compression selection
QAP / assignment	bridge between QUBO and learned prediction	QNNs, end-to-end quantum learning	dense coupling; sparse feasible states	amortized prediction vs. per-instance solve

Table 4: Problem-centered synthesis of AI–quantum approaches by problem family.

Level	Evidence requirement	Establishes	Does not establish
M0	conceptual mechanism or architecture	plausibility	empirical effectiveness
M1	ideal statevector or exact simulation	proof of concept	noise robustness or scaling
M2	held-out, cross-size, cross-topology, or cross-problem tests	some generalization	hardware viability
M3	realistic noise or physical-QPU validation of a material component	hardware relevance of that component	end-to-end system benefit
M4	complete hybrid workflow with physical quantum execution	operational hardware integration	practical superiority
M5	matched-resource comparison against strong classical and static-hybrid alternatives	practical system advantage in the tested regime	asymptotic quantum advantage, unless separately proven

Table 5: The M0–M5 evidence-maturity hierarchy. Each level records what a study demonstrates, not its scientific quality.

Panel of Figure 4 — Figure 4: Degree of AI autonomy versus the strongest quantum evidence reported by representative studies. Vertical positions are the maturity levels coded in the evidence matrix ( Appendix A ); translucent bars mark studies coded as a range (e.g., M3–M4), with the marker at the midpoint. Horizontal positions are qualitative. Marker shape and colour indicate the paradigm.

Panel of Figure 5 — Figure 5: Distribution of evidence maturity within each paradigm for the evidence core, using the coding described in Appendix A . Bar segments show the share of studies at each level; numbers inside segments are study counts. Background reviews (10), structural precursors (4), and one benchmark study are omitted. No study is coded at M0, M4, or M5.

Dimension	Minimum reporting expectation
Solution quality	gap or approximation ratio; best-case and distributional performance
Feasibility	feasible-sample rate; constraint violation; repair
Quantum resources	qubits; two-qubit gates; depth
Sampling	shots per call; total shots; allocation policy
Invocation cost	QPU calls or annealer submissions
Time	training; classical compute; QPU execution; queue time where material

Table 6: Minimum reporting checklist for AI

\times

Quantum optimization experiments.

Explore similar work

May 13, 2026quant-ph

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.

Zubin Zheng, Jiahao Wu, Shengcai Liu

Guangdong Provincial Key Labora- tory of Brain-Inspired Intelligent Computation, Department of CSE, SUSTech.

Quadratic Unconstrained Binary Optimization Differentiable Optimization Quantum Approximate Optimization Algorithm

Ask PDF

May 8, 2026quant-ph

Optimal FALQON for Quantum Approximate Optimization via Layer-wise Parameter Tuning

Feedback-based adaptive quantum optimization (FALQON) is a promising approach for solving combinatorial problems on noisy intermediate-scale quantum (NISQ) devices, requiring only single circuit evaluations per layer. However, standard FALQON relies on fixed hyperparameters that severely limit convergence speed, requiring hundreds to thousands of layers for acceptable solutions. This paper proposes Optimal FALQON, an optimization-based formulation that treats the per-layer time step (

δ_k

) and scaling factor (

M_k

) as decision variables optimized via classical methods. We present a comprehensive empirical study on all 94 non-isomorphic 3-regular graphs with 12 vertices, comparing Optimal FALQON with standard FALQON and multiple QAOA variants. Results demonstrate statistically significant improvements in success probability, evaluation efficiency, and depth-normalized cost across the evaluated benchmarks. Furthermore, initializing QAOA with parameters from Optimal FALQON yields superior warm-start performance compared to fixed initialization.

Michael Mancini, Shabnam Sodagari

Computer Engineering & Computer Science, California State University, Long Beach, CA 90840

Quantum Approximate Optimization Algorithm

Ask PDF

Jul 22, 2026quant-ph

DQAOA-GPT: AI-Accelerated Distributed Quantum Optimization for Combinatorial Problems

While combinatorial optimization problems are central to many scientific and engineering applications, their solution remains challenging due to exponentially large search spaces. Variational quantum algorithms offer a promising route for tackling such problems, yet their practical performance is limited by repeated quantum circuit evaluations and classical parameter updates. In this work, we introduce DQAOA-GPT, a hybrid framework that integrates the distributed quantum approximate optimization algorithm (DQAOA), which decomposes a large optimization problem into smaller sub-problems, with GPT-based quantum circuit generation for solving those sub-problems. Rather than relying on iterative variational optimization, the proposed approach uses a trained generative model to directly generate high-quality quantum circuits for the decomposed sub-problems. As a benchmark, we evaluate DQAOA-GPT against conventional DQAOA on dense HUBO optimization problems with up to 100 decision variables. The results demonstrate that DQAOA-GPT significantly reduces computational cost while maintaining competitive solution quality, with larger acceleration observed for larger sub-problem sizes. Although this work focuses on benchmark-scale validation, the framework provides a promising foundation for larger-scale combinatorial optimization in hybrid HPC-QC environments through increased GPU resources and parallel computing capability.

Seongmin Kim, Abhinav Rijal, Yuri Alexeev +5

National Center for Computational Sciences, Oak Ridge National Laboratory, Oak Ridge, TN, USA · Department of Physics & Astronomy, University of Tennessee, Knoxville, TN, USA · NVIDIA Corporation, Santa Clara, CA, USA +3

Distributed Optimization Combinatorial Optimization Quantum Approximate Optimization Algorithm

Ask PDF

Abstract

Explore similar work

Neural QAOA2^{2}2: Differentiable Joint Graph Partitioning and Parameter Initialization for Quantum Combinatorial Optimization

Optimal FALQON for Quantum Approximate Optimization via Layer-wise Parameter Tuning

DQAOA-GPT: AI-Accelerated Distributed Quantum Optimization for Combinatorial Problems

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