Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language

A multi-agent framework that automatically generates Quadratic Unconstrained Binary Optimization (QUBO) formulations from natural-language problem descriptions achieved 68% accuracy on QUBOBench, a new benchmark of 100 combinatorial optimization problems spanning 12 application domains, according to the arXiv paper 2609.10629v1. The framework outperformed a direct single-call baseline by 22%, and the authors identified iterative self-repair as the most important component behind the performance gain. The data and code are open-sourced at the project's GitHub Pages site.

arXiv:2609.10629v1 Announce Type: new 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, requiring the identification of 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. The data and code are open-sourced at https://quitttcat.github.io/QuantumQUBOAgent.