Multi-Agent Framework for Generating QUBO Formulations from Natural Language

Summary

A multi-agent large language model (LLM) framework automatically translates natural language problem descriptions into QUBO formulations (binary variables, constraints, penalty terms). In the newly introduced QUBOBench benchmark of 100 problems, the system achieved 68% accuracy, outperforming the single-call baseline by a 22-point margin.

Why it matters

QUBO is the standard input format for quantum, hybrid, and quantum-inspired solvers. However, writing correct formulations requires deep domain expertise in defining variables, constraints, and penalty weights. Automating this step could significantly lower the barrier to accessing near-term quantum optimization hardware for researchers and industry users. The study also presents QUBOBench, a 100-problem dataset selected from 12 domains, which fills a gap in reproducible evaluation in this field.

Highlights

• 68% accuracy on QUBOBench; a 22-point advantage over the direct single-call LLM baseline
• Iterative self-repair was identified as the most effective component in the multi-agent pipeline
• QUBOBench: A set of 100 combinatorial problems spanning 12 domains, compiled from peer-reviewed literature, competitions, and standard NP-hard problems; code and data are shared as open source

Critical take

A 68% success rate implies that approximately one-third of the generated QUBO formulations are incorrect. Because incorrect penalty weights or silently omitted constraints can produce invalid yet plausible-looking solutions, the practical reliability gap may be larger than the headline figure suggests. Furthermore, this result comes from a workshop paper (ICML 2026 AI4Research) based on a 100-problem benchmark. Therefore, it remains untested whether the system can generalize to longer, noisier real-world specifications.