Multi-Agent Framework Automates QUBO Formulation from Natural Language

Summary

Quadratic Unconstrained Binary Optimization (QUBO) is used by quantum, hybrid quantum-classical, and quantum-inspired solvers, but creating a correct formulation from natural-language requirements requires identifying variables, constraints, objectives, penalty terms, and penalty weights. This paper presents an end-to-end multi-agent framework that generates QUBO formulations from natural-language problem descriptions, including structured and unstructured test cases. The authors also introduce QUBOBench, a benchmark of 100 combinatorial optimization problems spanning 12 application domains and drawn from peer-reviewed literature, competitions, and canonical NP-hard problems. On this benchmark, the framework achieves 68% accuracy, 22 percentage points higher than a direct single-call baseline. An analysis of the system components identifies iterative self-repair as the most important contributor to the performance improvement. The authors release the benchmark data and code through the QuantumQUBOAgent project.