Automating QUBO Formulation Generation from Natural Language with a Multi-Agent Framework
Authors: Niloy Kumar Mondal, Md Rizwan Parvez
arXiv: 2609.10629 [cs.AI]
Submitted: 9 September 2026
Venue: Accepted at the ICML 2026 Workshop on AI as a Tool for Mathematics, Computer Science, and Machine Learning (AI4Research)
Abstract
Quadratic Unconstrained Binary Optimization (QUBO) is a central formulation for combinatorial optimization and has gained increasing attention due to its compatibility with quantum, hybrid quantum-classical, and quantum-inspired solvers. However, translating natural-language problem descriptions into correct QUBO formulations remains difficult: it requires identifying binary variables, constraints, objective functions, penalty terms, and suitable penalty weights. This process is time-consuming and often demands substantial domain expertise.
To address this challenge, we propose an end-to-end multi-agent framework that automatically generates QUBO formulations from natural-language problem descriptions, supported by structured or unstructured test cases. To evaluate its performance, we also introduce QUBOBench, a benchmark containing 100 combinatorial optimization problems across 12 application domains, curated from peer-reviewed literature, competitions, and canonical NP-hard problems. Experimental results show that our framework achieves 68% accuracy on QUBOBench, outperforming a direct single-call baseline by 22%. Further analysis identifies iterative self-repair as the most important component contributing to improved performance.
Data and code: https://quitttcat.github.io/QuantumQUBOAgent
Why This Matters in 2026
With quantum annealing and hybrid quantum-classical hardware now commercially accessible through major cloud providers, QUBO has become a standard interface between mathematical optimization and quantum hardware. Yet the bottleneck has shifted from solver performance to formulation: practitioners still need to manually encode real-world problems into QUBO form, deciding binary variable mappings, penalty structures, and weight scalings by hand. This work directly targets that bottleneck by automating the formulation step, positioning LLM-driven multi-agent pipelines as a bridge between natural-language problem statements and quantum-ready optimization models.
Key Contributions
- A multi-agent framework for end-to-end generation of QUBO formulations from natural-language problem descriptions.
- QUBOBench, a new benchmark of 100 combinatorial optimization problems spanning 12 application domains, drawn from peer-reviewed literature, competitions, and canonical NP-hard problems.
- Empirical validation demonstrating 68% accuracy and a 22% improvement over a direct single-call baseline, with ablation showing iterative self-repair as the dominant performance driver.
- Open-source release of data and code for reproducibility.
Metadata
| Field | Value |
| --- | --- |
| Primary Subject | Artificial Intelligence (cs.AI) |
| DOI | 10.48550/arXiv.2609.10629 |
| Version | arXiv:2609.10629v1 |
| Workshop | ICML 2026 AI4Research |
via ArXiv AI