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

自动化实现：从自然语言生成二次无约束二值优化 (QUBO) 公式

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. 摘要： 二次无约束二值优化 (QUBO) 是组合优化的核心公式，由于其与量子求解器、混合量子-经典求解器以及量子启发式求解器的兼容性，正受到越来越多的关注。

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. 然而，将自然语言的问题描述转化为正确的 QUBO 公式仍然十分困难，这需要识别二值变量、约束条件、目标函数、惩罚项以及合适的惩罚权重。这一过程非常耗时，且通常需要深厚的领域专业知识。

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. 为了应对这一挑战，我们提出了一个端到端的智能体（multi-agent）框架，该框架在结构化或非结构化测试用例的支持下，能够从自然语言问题描述中自动生成 QUBO 公式。

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. 为了评估其性能，我们还引入了 QUBOBench，这是一个包含 100 个组合优化问题的基准测试集，涵盖 12 个应用领域，这些问题均精选自同行评审文献、竞赛以及经典的 NP-hard 问题。

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 this https URL. 实验结果表明，我们的框架在 QUBOBench 上达到了 68% 的准确率，比直接单次调用的基准方法高出 22%。进一步分析发现，迭代自修复（iterative self-repair）是提升性能的最关键组件。相关数据和代码已在指定链接开源。