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

Source: arXiv:2607.20225 · Published 2026-07-22 · By Seongmin Kim, Abhinav Rijal, Yuri Alexeev, Nora Bauer, Martin Roetteler, Mina Yoon et al.

TL;DR

This paper addresses the challenge of solving large-scale combinatorial optimization problems, which are critical in many scientific and engineering fields but difficult due to exponentially large discrete search spaces and complex objective landscapes. Variational quantum algorithms like QAOA show promise but face significant computational bottlenecks caused by repeated quantum circuit executions and classical parameter tuning, which scale poorly with problem size. To overcome these limitations, the authors propose DQAOA-GPT, a hybrid framework combining distributed quantum approximate optimization algorithm (DQAOA) for problem decomposition with a GPT-based generative model to directly synthesize high-quality quantum circuits for sub-problems, bypassing the iterative variational optimization loop.

DQAOA-GPT decomposes a large HUBO (Higher-order Unconstrained Binary Optimization) problem into smaller sub-problems, encodes structural information with FEATHER graph embeddings, and trains separate transformer models conditioned on sub-problem size to generate adaptive quantum circuits. The generated circuits are executed to produce candidate solutions, which are accepted only if they improve the global objective. Benchmarks on dense HUBO problems with 100 binary variables demonstrate that DQAOA-GPT maintains competitive solution quality relative to conventional DQAOA but achieves substantial runtime reductions, especially as sub-problem size grows. This effectively mitigates the accuracy-cost tradeoff inherent in iterative variational quantum algorithms. Moreover, the approach is naturally parallelizable on HPC infrastructures, providing a pathway for scaling quantum optimization to larger practical problem sizes.

Overall, the work highlights a novel synergy between AI-based generative modeling, distributed quantum optimization, and HPC resources to overcome computational bottlenecks in near-term quantum combinatorial optimization, representing a significant step toward practical quantum utility in complex real-world applications.

Key findings

• DQAOA-GPT maintains relative accuracy competitive with standard DQAOA across sub-problem sizes n = 4 to 12 on HUBO problems with N = 100 variables (Fig. 3a).
• Relative accuracy increases with sub-problem size, from approximately 0.36 (DQAOA-GPT, n=4) to 0.78 (n=12).
• Standard DQAOA runtime grows steeply with sub-problem size, from ~33.8 seconds at n=4 to ~684 seconds at n=12 due to iterative variational optimization (Fig. 3b).
• In contrast, DQAOA-GPT runtime remains approximately constant (~28 seconds) across sub-problem sizes by replacing optimization with a single GPT inference step.
• DQAOA-GPT reduces the quantum-classical feedback bottleneck of variational quantum algorithms by directly generating parameterized quantum circuits via a trained transformer.
• FEATHER graph embeddings effectively encode coarse structural information of sub-problems and condition GPT circuit generation without discarding higher-order interaction details.
• Sampling 10 candidate circuits per sub-problem with a temperature of 0.8 and selecting the lowest energy candidate yields high-quality local updates.
• The inference-time pipeline includes graph projection, embedding, GPT token generation, CUDA-Q simulation, and HUBO-energy evaluation, capturing end-to-end runtime.

Threat model

Not a security-focused paper; the adversary model is not applicable. The work addresses computational challenges in quantum optimization rather than adversarial threat scenarios.

Methodology — deep read

The authors propose DQAOA-GPT, a two-stage hybrid quantum-classical framework designed to solve large-scale combinatorial optimization problems represented as higher-order unconstrained binary optimization (HUBO) instances with up to 100 variables. The key methodological steps are:

1. Threat Model & Assumptions:

   • The adversary is not explicitly modeled; rather, the focus is on computational scalability and efficiency improvements for quantum combinatorial optimization. The quantum hardware is assumed capable of simulating parameterized circuits and the classical HPC system supports distributed computation.

2. Data:

   • Sub-problems are generated by random sampling of subsets of variables from the global HUBO tensor T ∈ R^N×N×N, with sub-problem sizes n chosen from {4,6,8,10,12}.
   • Each sub-problem is mapped to an Ising Hamiltonian via a transformation of binary variables, preserving linear, quadratic, and cubic interactions.
   • Ground-truth reference circuits for each sub-problem are generated using ADAPT-QAOA, which constructs adaptive ansätze via gradient-driven operator pool selection and parameter re-optimization.
   • Only sub-problem instances with reference circuits meeting a target approximation ratio threshold are retained for GPT model training.

3. Architecture / Algorithm:

   • The GPT model is a decoder-only transformer trained to autoregressively generate token sequences representing adaptive quantum circuits.
   • Input sequences encode the sub-problem structure explicitly using tokens for linear (i), quadratic (i,j), and cubic (i,j,k) interaction indices and their quantized coefficients.
   • Circuit tokens represent operators selected from the ADAPT-QAOA operator pool and associated variational parameters (β, γ) discretized on a numerical grid.
   • FEATHER graph embeddings of the projected sub-problem interaction graph (mapping cubic terms approximately to edge weights) provide a fixed-length conditioning vector injected as an additive embedding at every token position.

4. Training Regime:

   • Separate GPT models are trained independently for each sub-problem size n.
   • The loss is standard cross-entropy next-token prediction.
   • Training data pairs sub-problem token sequences with corresponding adaptive quantum circuits.
   • Hyperparameters (e.g., number of layers, embedding dimension) are not specified in detail in the source.

5. Evaluation Protocol:

   • At inference, from an initial global binary solution vector, m sub-problems per iteration are randomly sampled.
   • Generated circuits from the GPT model for each sub-problem are simulated using CUDA-Q on GPU hardware to obtain candidate bitstrings.
   • For each sub-problem, 10 candidate circuits are sampled with temperature 0.8; the candidate producing minimal energy on the original problem Hamiltonian is selected.
   • Candidate solutions are accepted only if they improve the global energy, ensuring monotonic descent.
   • Comparisons between DQAOA and DQAOA-GPT are performed with fixed sub-problem sizes and iteration budgets.
   • Metrics measured include relative accuracy (compared to best known solutions from prior works) and runtime per iteration.

6. Reproducibility:

   • Code and models are not publicly released according to the source.
   • The experiments leverage the Oak Ridge Leadership Computing Facility using NVIDIA H200 GPUs and CUDA-Q simulation environment.

Example pipeline end-to-end:

• A 12-variable sub-problem is randomly selected from the 100-variable HUBO.
• The sub-problem tensor is projected onto a weighted graph; a FEATHER embedding is computed.
• The sub-problem and coefficients are tokenized; input and embedding combined to condition the GPT model.
• GPT generates candidate adaptive QAOA circuits autoregressively in a single forward pass.
• Candidate circuits are simulated on GPU-based CUDA-Q; measurement outcomes generate candidate bitstrings.
• The lowest energy bitstring corresponding to an accepted candidate update replaces variables in the global vector if energy improves.

This process iterates for T iterations until convergence or budget exhaustion.

Technical innovations

• Integration of distributed quantum approximate optimization (DQAOA) with a GPT-based generative model to eliminate iterative variational quantum circuit optimization.
• Use of FEATHER graph embeddings to condition transformer-based circuit generation with coarse structural summaries while preserving higher-order HUBO interaction fidelity.
• Extension of QAOA-GPT representation to third-order combinatorial optimization by encoding linear, quadratic, and cubic interaction terms as explicit tokens paired with quantized coefficients.
• Replacement of the quantum-classical optimization feedback loop with single-pass generative inference enabling near-constant runtime across increasing sub-problem sizes.

Datasets

• Randomly sampled sub-problems from synthetic 100-variable HUBO instances representing dense higher-order combinatorial optimization problems used for training and evaluation.

Baselines vs proposed

• Standard DQAOA: runtime at n=12 = ~683.99 seconds vs DQAOA-GPT: runtime = ~28 seconds, with similar relative accuracy (~0.78) on HUBO N=100 benchmarks.
• At n=4, standard DQAOA achieves relative accuracy ~0.38; DQAOA-GPT achieves ~0.36, demonstrating comparable solution quality even at small sub-problem sizes.

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.20225.

Fig 1: Schematic illustration of the QAOA-GPT workflow.

Fig 2: Schematic illustration of the DQAOA-GPT workflow. Inspired by Refs. [13], [17]

Fig 3: DQAOA-GPT performance for different sub-problem sizes n. (a)

Limitations

• Experiments performed on simulated quantum circuits rather than on physical quantum hardware; hardware noise effects not evaluated.
• Training and inference performed with a single GPU and m=1 sub-problems concurrently, not demonstrating full parallel scalability potential.
• No detailed hyperparameter sensitivity analysis or ablations reported for GPT model size, token vocabularies, or temperature sampling effects.
• The approach relies on the availability of high-quality ADAPT-QAOA reference circuits for supervised training, which may be expensive to generate for larger sub-problems.
• Generalization performance to problem instances with significantly different structure or distributions than the training set is not evaluated.
• The projection of cubic HUBO terms onto weighted graphs for FEATHER embeddings is approximate, potentially losing some structural detail.

Open questions / follow-ons

• How well does DQAOA-GPT generalize to different classes of combinatorial optimization problems beyond dense HUBO instances?
• What is the robustness of GPT-generated circuits to hardware noise and imperfections on real quantum devices?
• How does scaling the number of sub-problems solved in parallel (m > 1) affect overall runtime and solution quality in large HPC-QC systems?
• Can the GPT model be extended to support adaptive or iterative refinement of generated circuits to further improve solution accuracy?

Why it matters for bot defense

For bot-defense or CAPTCHA practitioners, this paper offers insights into using hybrid classical-quantum approaches accelerated by AI to tackle combinatorial optimization tasks. The elimination of iterative variational quantum circuit optimization via generative models significantly reduces computational overhead, enabling scalable quantum-classical optimization hybrids that can be deployed in high-performance computing environments. Although the work targets quantum solutions rather than classical bot detection directly, the core principle of combining problem decomposition, efficient generative modeling, and parallelism can inspire similar strategies for large-scale challenge generation or response optimization in adversarial settings. The incorporation of structure-aware embeddings (FEATHER) to condition generation may also inform design of robust, adaptive verification challenges balancing complexity and computational feasibility.

Cite

@article{arxiv2607_20225,
  title={ DQAOA-GPT: AI-Accelerated Distributed Quantum Optimization for Combinatorial Problems },
  author={ Seongmin Kim and Abhinav Rijal and Yuri Alexeev and Nora Bauer and Martin Roetteler and Mina Yoon and George Siopsis and In-Saeng Suh },
  journal={arXiv preprint arXiv:2607.20225},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.20225}
}

Read the full paper

• arXiv:2607.20225 (abstract)
• arXiv:2607.20225 (PDF)