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

# QuantumQUBO Agent: Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language
Source: [https://arxiv.org/html/2609.10629](https://arxiv.org/html/2609.10629)
Niloy Kumar MondalAffiliation:Bangladesh University of Engineering and TechnologyCorrespondence to:[nkm2105044@gmail\.com](mailto:[email protected])Md Rizwan ParvezAffiliation:Qatar Computing Research Institute, HBKU, Doha, QatarCorrespondence to:[mparvez@hbku\.edu\.qa](mailto:[email protected])

###### 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/](https://quitttcat.github.io/QuantumQUBOAgent/)\.

###### Keywords:

Machine Learning, ICML

## 1Introduction

The Quadratic Unconstrained Binary Optimization \(QUBO\) problem is a combinatorial optimization problem classified as NP\-hard, meaning no efficient algorithm is known to solve it optimally in polynomial time\. It has a variety of application areas such as Computer Science, Finance, Physics, Engineering, Medicine, VLSI design, Quantum Computing, Traffic Management, Machine Scheduling, and many more\([Punnen, 2022](https://arxiv.org/html/2609.10629#bib.bib2)\)\. With advances in quantum computing\([Preskill, 2018](https://arxiv.org/html/2609.10629#bib.bib3)\), QUBO problems have become increasingly important because they can be addressed by quantum, hybrid quantum\-classical, and quantum\-inspired methods such as quantum annealing\([Rajak et al\., 2023](https://arxiv.org/html/2609.10629#bib.bib4)\)and the Quantum Approximate Optimization Algorithm \(QAOA\)\([Farhi and Harrow, 2016](https://arxiv.org/html/2609.10629#bib.bib5)\)\. Quantum annealing is a powerful heuristic for solving optimization problems\([Somma et al\., 2012](https://arxiv.org/html/2609.10629#bib.bib31)\)\.

Researchers across many domains are exploring quantum optimization algorithms with the goal of potential speedups and improved accuracy\. These algorithms have been applied to machine learning tasks such as feature selection\([Mücke et al\., 2023](https://arxiv.org/html/2609.10629#bib.bib16);[Samanta et al\., 2025](https://arxiv.org/html/2609.10629#bib.bib23);[Pathak et al\., 2025](https://arxiv.org/html/2609.10629#bib.bib21)\)and Bayesian network structure learning\([Shikuri, 2025](https://arxiv.org/html/2609.10629#bib.bib14)\), computer vision problems including image segmentation and denoising\([Heidari et al\., 2024](https://arxiv.org/html/2609.10629#bib.bib24);[Kerger and Miyazaki, 2023](https://arxiv.org/html/2609.10629#bib.bib25);[Venkatesh et al\., 2024](https://arxiv.org/html/2609.10629#bib.bib26)\), supply chain\([Moncayo\-Martínez and He, 2025](https://arxiv.org/html/2609.10629#bib.bib15);[Ciacco et al\., 2026](https://arxiv.org/html/2609.10629#bib.bib18)\), drug discovery\([Yang, 2025](https://arxiv.org/html/2609.10629#bib.bib28)\), RNA folding\([Fox et al\., 2022](https://arxiv.org/html/2609.10629#bib.bib30)\), satellite observation\([Ferrari et al\., 2025](https://arxiv.org/html/2609.10629#bib.bib29)\), scheduling problems\([Zhou et al\., 2025](https://arxiv.org/html/2609.10629#bib.bib17);[Gebler et al\., 2024](https://arxiv.org/html/2609.10629#bib.bib19)\), cybersecurity\([Marini and Arpe, 2025](https://arxiv.org/html/2609.10629#bib.bib20)\), IoT\([Zhang et al\., 2025b](https://arxiv.org/html/2609.10629#bib.bib27)\), and computational chemistry\([Negre et al\., 2022](https://arxiv.org/html/2609.10629#bib.bib22)\)\.

To apply quantum algorithms across domains, optimization problems must first be reformulated as QUBO and often as Ising formulations\([Lucas, 2014](https://arxiv.org/html/2609.10629#bib.bib6)\)\. In general, given a natural\-language description of a combinatorial optimization problem, the task is to find the values of binary decision variablesx∈\{0,1\}nx\\in\\\{0,1\\\}^\{n\}that minimize a cost function of the form

minx∈\{0,1\}n⁡E⁡\(x\)=x⊤​Q​x\+c,\\min\_\{x\\in\\\{0,1\\\}^\{n\}\}\\;E\(x\)\\;=\\;x^\{\\top\}Q\\,x\\;\+\\;c,\(1\)whereQQis a matrix of coefficients andccis a constant offset\([Glover et al\., 2019](https://arxiv.org/html/2609.10629#bib.bib1)\)\. The solution space contains2n2^\{n\}candidate bitstrings, and finding the optimum is NP\-hard in general\.

The cognitive task therefore involves identifying the binary decision variables, extracting the implicit and explicit constraints, designing the cost function and penalty terms for constraint violations, selecting appropriate penalty weights, and finally solving the resulting QUBO using classical heuristics or state\-of\-the\-art quantum solvers\. These steps are extremely challenging and time\-consuming, as such a complex task often requires domain expertise, mathematical rigor, and experimental feedback\.

To address this cognitive bottleneck, we propose an end\-to\-end multi\-agent framework that generates the QUBO formulation from natural language problem description, together with either structured or unstructured test cases\.To evaluate our framework, we introduce QUBOBench, a 100 combinatorial optimization problems 12 application domains, curated from peer\-reviewed venues, competitions, and canonical NP\-hard problems\. Our framework achieves 68% accuracy on QUBOBench, outperforming the direct single\-call baseline \(46%\) by a 22 percentage margin, with iterative self repair identified as the most critical component driving performance\.

## 2Related Work

Recent work has studied how large language models can translate natural language problem descriptions into formal optimization models\. The NL4Opt competition established this direction by asking systems to formulate optimization problems from descriptions in natural language\([Ramamonjison et al\., 2023](https://arxiv.org/html/2609.10629#bib.bib7)\)\. Subsequent systems expand this idea with more structured reasoning and agentic workflows\. Chain\-of\-Experts decomposes complex operations\-research problems across multiple expert\-style LLMs agents\([Xiao et al\., 2024](https://arxiv.org/html/2609.10629#bib.bib8)\), while Optimus uses LLMs to generate scalable mixed\-integer and linear programming models for downstream solvers\([AhmadiTeshnizi et al\., 2024](https://arxiv.org/html/2609.10629#bib.bib9)\)\. OptimAI and LLMOPT further explore LLM\-powered agents that define, model, and solve general optimization problems from natural language\([Thind et al\., 2025](https://arxiv.org/html/2609.10629#bib.bib10);[Shu et al\., 2025](https://arxiv.org/html/2609.10629#bib.bib11)\)\.

Prior LLM\-based approaches to optimization modeling primarily focus on LP\(Linear Programming\), MILP \(Mixed\-Integer Linear Programming\), or general solver\-ready formulations, whereas the QUBO setting remains comparatively less explored despite its central role in quantum and quantum\-inspired optimization\. However, AutoQUBO automates QUBO generation from formal programmatic inputs, but still assumes that the user can provide a precise computational description of the problem and does not address formulation from natural\-language research descriptions\([Moraglio et al\., 2022](https://arxiv.org/html/2609.10629#bib.bib12)\)\.

LLM\-QUBO is the most closely related work which studies the automatic conversion of natural\-language optimization descriptions into QUBO formulation\. However, its experiments focus mainly on MILP to QUBO conversion and validate correctness through structural checks such as input\-format adherence, binarization, slack\-variable introduction, and penalty\-term validity\([Zhang et al\., 2025a](https://arxiv.org/html/2609.10629#bib.bib13)\)\. Thus, it provides limited support for end\-to\-end validation of the generated formulation as an executable research artifact\. Besides, it does not systematically verify that the natural\-language specification, structured formulation, generated implementation, and small\-instance optima are mutually consistent, nor does it provide a feedback\-driven reformulation process when errors occur\. In addition, the empirical evaluation is confined to a small number of canonical textbook problems and does not assess performance across diverse, domain\-specific optimization tasks\.

## 3Methodology

Figure 1:Workflow and Architecture of QuantumQUBO AgentGenerating a QUBO formulation from a natural\-language problem statement involves several distinct steps: understanding the problem, choosing binary encoding variables and constraints, defining penalty terms, deriving the cost function, generating runnable code, and verifying correctness\. Rather than asking a single LLM to handle all of these steps at once, we decompose the task across specialized agents, each responsible for one step\. The overall architecture is illustrated in Figure[1](https://arxiv.org/html/2609.10629#S3.F1)\. The role of each agent and the end\-to\-end workflow are described in the following subsections\.

### 3\.1Multi\-Agent Architecture

Our framework consists of six LLM agents: Planner Agent, Formulizer Agent, Coder Agent, Debugger Agent, Writer Agent and a Judge Agent\.

#### 3\.1\.1The Planner Agent

Our first agent is the Planner Agent\. It is an LLM agent that reads the natural\-language problem description provided by the user and extracts the decision variables, the optimization direction, and every implicit or explicit constraint together with its type \(equality,≤\\leq, or≥\\geq\) and hardness\. It then returns a structured JSON representation of the problem, which is passed to the Judge Agent for consistency checking against the original description\. If the Judge identifies any inconsistency, it returns a list of issues to the Planner, forming a feedback loop\. The Planner then performs another round of parsing and planning from the original description guided by the issue list\.

#### 3\.1\.2The Formulizer Agent

Our second agent is the Formulizer Agent\. The Formulizer Agent is an LLM agent that takes the structured JSON representation from the Planner and derives the corresponding QUBO cost function from the decision variables, constraints, and the type of optimization, and simplifies the cost function\. The returned formulation, in structured JSON containing the variable mapping, objective and penalty terms, penalty\-weight justification, and constant offset, is then passed to the Judge Agent; if rejected, the Formulizer regenerates the formulation guided by the reported issues\. The Formulizer takes feedback from the Judge Agent as well as from failed test cases at the end of the pipeline, and tries to improve the formulation\.

#### 3\.1\.3The Judge Agent

Our next agent is the Judge Agent\. It is an LLM agent invoked at two checkpoints: it first checks the Planner’s structured specification for consistency with the original description, and later checks the Formulizer’s QUBO cost for consistency with the specification judging correctness constraint encodings, penalty forms, and objective sign\. In both roles it returns a pass/fail verdict with a list of specific issues, which are looped back to the originating agent as feedback for a targeted retry\.

#### 3\.1\.4The Debugger Agent

Our next agent is the Debugger Agent\. It is an LLM agent that is essentially a parser\. It converts the user supplied test cases and ground truth from natural language into structured JSON records suitable for automated verification\. It uses the variable mapping passed from the structured JSON formulation to encode the ground optimal selections as bitstrings\. The Debugger never sees the Coder’s output or the generated cost encoding matrix, which ensures optima from the generated formula is never stored as ground truth\.Besides, the coder never sees the ground truth as well\.

#### 3\.1\.5The Coder Agent

The Coder Agent is an LLM agent that translates the QUBO formulation into executable Python code\. It is given the structured specification,formulation, and the parameters of a single sample instance but not the ground\-truth bitstrings which prevents information leak\. The generated function is then handed to the Test Runner for empirical verification, and any failure message is returned to the Coder as feedback for the next attempt\.

#### 3\.1\.6The Test Runner

The Test Runner is a deterministic component \(not an LLM agent\) that validates the Coder’s output against the ground truth on each test case\. It classifies any failure as either a*coding error*\(an exception or a malformed function\) or a*formulation error*\(a valid output whose optimum disagrees with the ground truth\)\. Coding errors are routed back to the Coder Agent, while formulation errors are routed back to the Formulizer Agent for a fresh derivation guided by the reported issues\.

#### 3\.1\.7The Writer Agent

Our final agent is the writer agent that produces a visual representation and summary of the output\.

## 4QUBOBench

To evaluate our framework on domain specific problems, we introduce QUBOBench, a benchmark comprising 100 combinatorial optimization problems and 200 small instance test cases spanning 12 application domains\. The problem instances are curated from three complementary sources: 76 drawn from peer\-reviewed venues, 5 from competitions and hackathons, and 19 canonical NP\-hard problems primarily adapted from Lucas\([Lucas, 2014](https://arxiv.org/html/2609.10629#bib.bib6)\)\. A data sample consists of hand curated problem description and sample small instance test cases both in natural language\. For more details, refer to Appendix[B](https://arxiv.org/html/2609.10629#A2)\.

## 5Experimental Setup

### 5\.1Evaluation Protocal

We evaluate QuantumQUBO Agent on the QUBOBench dataset\. Performance is measured across two metrics:accuracy, defined as the fraction of benchmarks for which the pipeline produces a QUBO formulation and matches all ground\-truth optimal solutions; andtotal token consumption\.

### 5\.2Baseline Metric

As a lower\-bound baseline, we conduct a direct evaluation in which the natural\-language problem description is presented directly to the LLM with a single prompt\. To ensure fair and fully automated evaluation, we provide the model with structured instance dictionaries previously generated by the Debugger agent, constraining the output to a fixed function signature\. This eliminates the possibility of format\-induced false negatives in automated scoring\. Ground\-truth optimal solutions are never exposed to the model at any stage\.

### 5\.3Model Selection

All reasoning agents \(Planner, Judge, Formulizer, Debugger\) useqwen/qwen3\-235b\-a22b, while the Coder agent usesqwen/qwen3\-coder\-next\. We believe our pipeline is LLM\-agnostic\. For the direct evaluation we usedqwen/qwen3\-coder\-next\.

### 5\.4Ablation Study

We conduct two ablation studies: removing the iterative feedback once and removing the judge together with feedback, to isolate the contribution\.

## 6Results and Discussions

PlannerJudgeFormulizerCoderIter\. FeedbackAcc\. \(%\)Tokens \(k\)✓\\checkmark✓\\checkmark✓\\checkmark✓\\checkmark✓\\checkmark6848\.1✓\\checkmark✓\\checkmark✓\\checkmark✓\\checkmark×\\times3524\.7✓\\checkmark×\\times✓\\checkmark✓\\checkmark×\\times3622\.1×\\times×\\times×\\times×\\times×\\times463\.2

Table 1:Ablation results on QUBOBench\. Rows from top: QuantumQUBO Agent, without iterative feedback, without Judge and iterative feedback, Direct Method\.Table[1](https://arxiv.org/html/2609.10629#S6.T1)shows that the full pipeline achieves 68% accuracy, outperforming all ablated variants\. Removing iterative feedback causes the largest drop to 35%, confirming that self\-repair is the most critical component\. Removing the Judge while keeping all other components fixed yields 36%, nearly identical to the no\-retry setting, indicating that the Judge provides value only when paired with a sufficient retry budget to act on its feedback\.

### 6\.1Failure mode analysis

Aformulation erroroccurs when the agent produces an incorrect QUBO objective, wrong penalty terms, incorrect variable mapping, or an energy landscape that does not encode the problem correctly\. Acoding erroroccurs when the QUBO mathematics is correct but thebuild\_quboimplementation fails due to index bugs, wrong array shapes, or incorrect NumPy operations\.

Table 2:Error type distribution on QUBOBench\. Percentages are of total errors by QuantumQUBO Agent vs direct method\.In the QuantumQUBO Agent, 79\.3% of all errors originate from the Coder agent, while only 15\.5% from formulation failures, indicating that the Planner\-Formulizer\-Judge chain successfully resolves most mathematical ambiguities\. In contrast, the direct method shows the inverse pattern: 66\.0% of failures are formulation errors, confirming that without structured reasoning, a single LLM call struggles primarily with deriving correct QUBO mathematics rather than implementing it\.

## 7Future Work

Future work includes fine\-tuning separate agents for specific tasks, adding Ising Formulator incorporated with quantum hardware feedback\.

## References

- A\. AhmadiTeshnizi, W\. Gao, and M\. UdellOptimus: scalable optimization modeling with \(mi\) lp solvers and large language models\.arXiv preprint arXiv:2402\.10172\.Cited by:[§2](https://arxiv.org/html/2609.10629#S2.p1.1)\.
- Ciaccoet al\.\(2026\)A\. Ciacco, F\. Guerriero, and F\. P\. SaccomannoQuantum annealing for the two\-level facility location problem\.Future Generation Computer Systems174,pp\. 107961\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Farhi and Harrow \(2016\)E\. Farhi and A\. W\. HarrowQuantum supremacy through the quantum approximate optimization algorithm\.arXiv preprint arXiv:1602\.07674\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p1.1)\.
- Ferrariet al\.\(2025\)B\. Ferrari, G\. Ganzerli, M\. Iori, and R\. OroseiA qubo formulation for scheduling satellite observations of mars\.In2025 IEEE International Conference on Quantum Artificial Intelligence \(QAI\),pp\. 228–233\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Foxet al\.\(2022\)D\. M\. Fox, C\. M\. MacDermaid, A\. M\. Schreij, M\. Zwierzyna, and R\. C\. WalkerRNA folding using quantum computers\.PLOS Computational Biology18\(4\),pp\. e1010032\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Gebleret al\.\(2024\)C\. Gebler, J\. Rethmann, and P\. UeberholzQUBO models for the fifo stack\-up problem and experimental evaluation on a quantum annealer\.SN Computer Science5\(7\),pp\. 818\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Gloveret al\.\(2019\)F\. Glover, G\. Kochenberger, and Y\. DuQuantum bridge analytics i: a tutorial on formulating and using qubo models\.4or17\(4\),pp\. 335–371\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p3.2)\.
- Heidariet al\.\(2024\)S\. Heidari, M\. J\. Dinneen, and P\. DelmasQuantum annealing for computer vision minimization problems\.Future Generation Computer Systems160,pp\. 54–64\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Kerger and Miyazaki \(2023\)P\. Kerger and R\. MiyazakiQuantum image denoising: a framework via boltzmann machines\.QUBO, and Quantum annealing\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Lucas \(2014\)A\. LucasIsing formulations of many np problems\.Frontiers in physics2,pp\. 74887\.Cited by:[§B\.3](https://arxiv.org/html/2609.10629#A2.SS3.SSS0.Px3.p1.1),[§1](https://arxiv.org/html/2609.10629#S1.p3.1),[§4](https://arxiv.org/html/2609.10629#S4.p1.1)\.
- Marini and Arpe \(2025\)R\. Marini and R\. ArpeCyber risk scoring with qubo: a quantum and hybrid benchmark study\.arXiv preprint arXiv:2512\.18305\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Moncayo\-Martínez and He \(2025\)L\. A\. Moncayo\-Martínez and N\. HeQuantum optimisation for supply chain: qubo formulations and qaoa solutions for facility location and load balancing\.Results in Engineering,pp\. 108373\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Moraglioet al\.\(2022\)A\. Moraglio, S\. Georgescu, and P\. SadowskiAutoQubo: data\-driven automatic qubo generation\.InProceedings of the Genetic and Evolutionary Computation Conference Companion,pp\. 2232–2239\.Cited by:[§2](https://arxiv.org/html/2609.10629#S2.p2.1)\.
- Mückeet al\.\(2023\)S\. Mücke, R\. Heese, S\. Müller, M\. Wolter, and N\. PiatkowskiFeature selection on quantum computers\.Quantum Machine Intelligence5\(1\),pp\. 11\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Negreet al\.\(2022\)C\. F\. Negre, A\. Lopez\-Bezanilla, Y\. Zhang, P\. D\. Akrobotu, S\. M\. Mniszewski, S\. Tretiak, and P\. A\. DubToward a qubo\-based density matrix electronic structure method\.Journal of chemical theory and computation18\(7\),pp\. 4177–4185\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Pathaket al\.\(2025\)I\. P\. Pathak, T\. Kim, N\. Yilmazer, and D\. RoachFeature selection for imbalanced network intrusion detection systems dataset using quantum annealer\.In2025 IEEE International Conference on Electro Information Technology \(eIT\),pp\. 1–6\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Preskill \(2018\)J\. PreskillQuantum Computing in the NISQ era and beyond\.Quantum2,pp\. 79\.External Links:[Document](https://dx.doi.org/10.22331/q-2018-08-06-79),[Link](https://doi.org/10.22331/q-2018-08-06-79),ISSN 2521\-327XCited by:[§1](https://arxiv.org/html/2609.10629#S1.p1.1)\.
- Punnen \(2022\)A\. P\. PunnenThe quadratic unconstrained binary optimization problem\.Springer International Publishing10,pp\. 978–3\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p1.1)\.
- Rajaket al\.\(2023\)A\. Rajak, S\. Suzuki, A\. Dutta, and B\. K\. ChakrabartiQuantum annealing: an overview\.Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences381\(2241\)\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p1.1)\.
- Ramamonjisonet al\.\(2023\)R\. Ramamonjison, T\. Yu, R\. Li, H\. Li, G\. Carenini, B\. Ghaddar, S\. He, M\. Mostajabdaveh, A\. Banitalebi\-Dehkordi, Z\. Zhou,et al\.Nl4opt competition: formulating optimization problems based on their natural language descriptions\.InNeurIPS 2022 competition track,pp\. 189–203\.Cited by:[§2](https://arxiv.org/html/2609.10629#S2.p1.1)\.
- Samantaet al\.\(2025\)S\. Samanta, D\. Wang, T\. Hodges, and A\. FerencziParametric quantum feature selection methods for fraud and default detection\.InProceedings of the AAAI Symposium Series,Vol\.7,pp\. 390–397\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Shikuri \(2025\)Y\. ShikuriDecomposed quadratization: efficient qubo formulation for learning bayesian network\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.39,pp\. 11345–11352\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Shuet al\.\(2025\)X\. Shu, H\. Qian, X\. Lu, J\. ZHOU, A\. Zhou, Y\. Yu,et al\.LLMOPT: learning to define and solve general optimization problems from scratch\.InInternational Conference on Learning Representations,Vol\.2025,pp\. 101580–101606\.Cited by:[§2](https://arxiv.org/html/2609.10629#S2.p1.1)\.
- Sommaet al\.\(2012\)R\. D\. Somma, D\. Nagaj, and M\. KieferováQuantum speedup by quantum annealing\.Physical review letters109\(5\),pp\. 050501\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p1.1)\.
- Thindet al\.\(2025\)R\. Thind, Y\. Sun, L\. Liang, and H\. YangOptimai: optimization from natural language using llm\-powered ai agents\.arXiv preprint arXiv:2504\.16918\.Cited by:[§2](https://arxiv.org/html/2609.10629#S2.p1.1)\.
- Venkateshet al\.\(2024\)S\. M\. Venkatesh, A\. Macaluso, M\. Nuske, M\. Klusch, and A\. DengelQ\-seg: quantum annealing\-based unsupervised image segmentation\.IEEE Computer Graphics and Applications44\(5\),pp\. 27–39\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Xiaoet al\.\(2024\)Z\. Xiao, D\. Zhang, Y\. Wu, L\. Xu, Y\. Wang, X\. Han, X\. Fu, T\. Zhong, J\. Zeng, M\. Song,et al\.Chain\-of\-experts: when llms meet complex operations research problems\.InInternational Conference on Learning Representations,Vol\.2024,pp\. 48519–48537\.Cited by:[§2](https://arxiv.org/html/2609.10629#S2.p1.1)\.
- Yang \(2025\)P\. YangLigand pose generation via qubo\-based hotspot sampling and geometric triplet matching\.arXiv preprint arXiv:2507\.20304\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Zhanget al\.\(2025a\)H\. Zhang, M\. Emu, and S\. ChoudhuryLLM\-qubo: an end\-to\-end framework for automated qubo transformation from natural language problem descriptions\.InProceedings of the AAAI Symposium Series,Vol\.7,pp\. 411–418\.Cited by:[§2](https://arxiv.org/html/2609.10629#S2.p3.1)\.
- Zhanget al\.\(2025b\)W\. Zhang, C\. Zhou, W\. Liu, T\. Han, and N\. AnsariHybrid quantum\-inspired optimization for aigc\-driven iot task offloading in mec networks\.IEEE Internet of Things Journal\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.
- Zhouet al\.\(2025\)Z\. Zhou, Q\. Chen, C\. Zhang, M\. Tan, and S\. LiHybrid quantum annealing for large\-scale exam scheduling: validation in real\-world educational scenarios\.Applied Soft Computing,pp\. 113756\.Cited by:[§1](https://arxiv.org/html/2609.10629#S1.p2.1)\.

## Appendix AAlgorithm of QuantumQUBO Agent

Input:A natural\-language problem descriptionPP, a set of test cases𝒯\\mathcal\{T\}, retry budgetsRplanner,Rformulizer,RcoderR\_\{\\text\{planner\}\},R\_\{\\text\{formulizer\}\},R\_\{\\text\{coder\}\}controlling the maximum number of repair attempts at each stage, and a pass thresholdτ∈\(0,1\]\\tau\\in\(0,1\]defining the minimum fraction of test cases that must pass for a solution to be accepted\.

Output:A verified QUBO formulationℱ\\mathcal\{F\}, a correctness\-verified builder functionffthat constructs the QUBO matrix for any problem instance, a worked example, and aLaTeXwrite\-up with compiled PDF deliverable\.

Algorithm 1QuantumQUBO Agent Pipeline1:

Rplanner,Rformulizer,Rcoder←R\_\{\\text\{planner\}\},R\_\{\\text\{formulizer\}\},R\_\{\\text\{coder\}\}\\leftarrownumber of maximum retry for each stage

2:

τ←\\tau\\leftarrowminimum pass rate to accept a solution

3:

4:

𝑠𝑝𝑒𝑐←PlannerAgent​\(P\)\\mathit\{spec\}\\leftarrow\\text\{PlannerAgent\}\(P\)
5:

𝑐ℎ𝑒𝑐𝑘←JudgeAgent​\(P,𝑠𝑝𝑒𝑐\)\\mathit\{check\}\\leftarrow\\text\{JudgeAgent\}\(P,\\ \\mathit\{spec\}\)
6:for

i←1i\\leftarrow 1to

RplannerR\_\{\\text\{planner\}\}do

7:ifnot

𝑐ℎ𝑒𝑐𝑘\.𝑝𝑎𝑠𝑠𝑒𝑑\\mathit\{check\}\.\\mathit\{passed\}then

8:

𝑠𝑝𝑒𝑐←PlannerAgent\(P,𝑐ℎ𝑒𝑐𝑘\.𝑖𝑠𝑠𝑢𝑒𝑠\)\\mathit\{spec\}\\leftarrow\\text\{PlannerAgent\}\(P,\\ \\mathit\{check\}\.\\mathit\{issues\}\)
9:

𝑐ℎ𝑒𝑐𝑘←JudgeAgent​\(P,𝑠𝑝𝑒𝑐\)\\mathit\{check\}\\leftarrow\\text\{JudgeAgent\}\(P,\\ \\mathit\{spec\}\)
10:endif

11:endfor

12:ifnot

𝑐ℎ𝑒𝑐𝑘\.𝑝𝑎𝑠𝑠𝑒𝑑\\mathit\{check\}\.\\mathit\{passed\}then

13:returnFail

14:endif

15:

16:

𝑓𝑜𝑟𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛←FormulizationAgent​\(𝑠𝑝𝑒𝑐\)\\mathit\{formulation\}\\leftarrow\\text\{FormulizationAgent\}\(\\mathit\{spec\}\)
17:

𝑐ℎ𝑒𝑐𝑘←JudgeAgent​\(𝑠𝑝𝑒𝑐,𝑓𝑜𝑟𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛\)\\mathit\{check\}\\leftarrow\\text\{JudgeAgent\}\(\\mathit\{spec\},\\ \\mathit\{formulation\}\)
18:for

i←1i\\leftarrow 1to

RformulizerR\_\{\\text\{formulizer\}\}do

19:ifnot

𝑐ℎ𝑒𝑐𝑘\.𝑝𝑎𝑠𝑠𝑒𝑑\\mathit\{check\}\.\\mathit\{passed\}then

20:

𝑓𝑜𝑟𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛←FormulizationAgent\(𝑠𝑝𝑒𝑐,𝑐ℎ𝑒𝑐𝑘\.𝑖𝑠𝑠𝑢𝑒𝑠\)\\mathit\{formulation\}\\leftarrow\\text\{FormulizationAgent\}\(\\mathit\{spec\},\\ \\mathit\{check\}\.\\mathit\{issues\}\)
21:

𝑐ℎ𝑒𝑐𝑘←JudgeAgent​\(𝑠𝑝𝑒𝑐,𝑓𝑜𝑟𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛\)\\mathit\{check\}\\leftarrow\\text\{JudgeAgent\}\(\\mathit\{spec\},\\ \\mathit\{formulation\}\)
22:endif

23:endfor

24:ifnot

𝑐ℎ𝑒𝑐𝑘\.𝑝𝑎𝑠𝑠𝑒𝑑\\mathit\{check\}\.\\mathit\{passed\}then

25:returnFail

26:endif

27:

28:

𝑡𝑒𝑠𝑡​\_​𝑐𝑎𝑠𝑒𝑠←DebuggerAgent​\(𝑠𝑝𝑒𝑐,𝑚𝑎𝑝𝑝𝑖𝑛𝑔⁡\(𝑓𝑜𝑟𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛\),𝑠𝑎𝑚𝑝𝑙𝑒​\_​𝑖𝑛𝑝𝑢𝑡\)\\mathit\{test\\\_cases\}\\leftarrow\\text\{DebuggerAgent\}\(\\mathit\{spec\},\\ \\mathit\{mapping\(formulation\)\},\\ \\mathit\{sample\\\_input\}\)
29:

30:for

i←1i\\leftarrow 1to

RcoderR\_\{\\text\{coder\}\}do

31:

𝑐𝑜𝑑𝑒←CoderAgent​\(𝑠𝑝𝑒𝑐,𝑓𝑜𝑟𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛,𝑒𝑟𝑟𝑜𝑟\)\\mathit\{code\}\\leftarrow\\text\{CoderAgent\}\(\\mathit\{spec\},\\ \\mathit\{formulation\},\\ \\mathit\{error\}\)
32:

𝑟𝑒𝑠𝑢𝑙𝑡𝑠,𝑐𝑙𝑎𝑠𝑠←TestRunner​\(𝑐𝑜𝑑𝑒,𝑡𝑒𝑠𝑡​\_​𝑐𝑎𝑠𝑒𝑠\)\\mathit\{results\},\\ \\mathit\{class\}\\leftarrow\\text\{TestRunner\}\(\\mathit\{code\},\\ \\mathit\{test\\\_cases\}\)
33:

𝑝𝑎𝑠𝑠​\_​𝑟𝑎𝑡𝑒←𝑟𝑒𝑠𝑢𝑙𝑡𝑠\.𝑝𝑎𝑠𝑠𝑒𝑑/\|𝑡𝑒𝑠𝑡​\_​𝑐𝑎𝑠𝑒𝑠\|\\mathit\{pass\\\_rate\}\\leftarrow\\mathit\{results\}\.\\mathit\{passed\}\\ /\\ \|\\mathit\{test\\\_cases\}\|
34:if

𝑝𝑎𝑠𝑠​\_​𝑟𝑎𝑡𝑒≥τ\\mathit\{pass\\\_rate\}\\geq\\tauthen

35:

𝑙𝑎𝑡𝑒𝑥←WriterAgent​\(𝑠𝑝𝑒𝑐,𝑓𝑜𝑟𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛\)\\mathit\{latex\}\\leftarrow\\text\{WriterAgent\}\(\\mathit\{spec\},\\ \\mathit\{formulation\}\)
36:return

𝑓𝑜𝑟𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛,𝑐𝑜𝑑𝑒,𝑙𝑎𝑡𝑒𝑥\\mathit\{formulation\},\\ \\mathit\{code\},\\ \\mathit\{latex\}
37:endif

38:if

𝑐𝑙𝑎𝑠𝑠=formulation\_error\\mathit\{class\}=\\textit\{formulation\\\_error\}then

39:

𝑓𝑜𝑟𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛←FormulizationAgent\(𝑠𝑝𝑒𝑐,𝑟𝑒𝑠𝑢𝑙𝑡𝑠\.𝑒𝑟𝑟𝑜𝑟𝑠\)\\mathit\{formulation\}\\leftarrow\\text\{FormulizationAgent\}\(\\mathit\{spec\},\\ \\mathit\{results\}\.\\mathit\{errors\}\)
40:

𝑐ℎ𝑒𝑐𝑘←JudgeAgent​\(𝑠𝑝𝑒𝑐,𝑓𝑜𝑟𝑚𝑢𝑙𝑎𝑡𝑖𝑜𝑛\)\\mathit\{check\}\\leftarrow\\text\{JudgeAgent\}\(\\mathit\{spec\},\\ \\mathit\{formulation\}\)
41:endif

42:

𝑒𝑟𝑟𝑜𝑟←𝑟𝑒𝑠𝑢𝑙𝑡𝑠\.𝑒𝑟𝑟𝑜𝑟𝑠\\mathit\{error\}\\leftarrow\\mathit\{results\}\.\\mathit\{errors\}
43:endfor

44:returnFail

## Appendix BDetails of Dataset

### B\.1Overview

QUBOBench is a benchmark designed to evaluate Large Language Models \(LLMs\) on the task of formulating Quadratic Unconstrained Binary Optimization \(QUBO\) problems from natural\-language descriptions\. The dataset comprises 100 problem instances and 200 test cases spanning 12 application domains, encompassing classical graph\-theoretic and combinatorial problems \(e\.g\., Max\-Cut, Maximum Independent Set, Graph Coloring, Hamiltonian Path\), logistics and scheduling \(Vehicle Routing, Job Shop Scheduling, Bin Packing\), machine learning tasks formulated as discrete optimization \(feature selection,kk\-means andkk\-medoids clustering, Bayesian network structure learning\), computational biology and chemistry \(RNA folding, protein lattice folding, molecular conformation selection\), finance \(portfolio optimization, credit scorecard selection\), computer vision \(image segmentation, denoising, stereo matching\), networks and infrastructure \(sensor placement, distribution\-network reconfiguration\), and quantum computing itself \(qubit allocation, circuit compilation, prime factorization\)\.

### B\.2Dataset Structure

Each datapoint in QUBOBench consists of two files:

- •prompt\.txt: a natural\-language description of the optimization problem, expressed in the style and terminology of its source domain\.
- •sample\_cases\.txt: one or more natural\-language test cases that specify a concrete problem instance, the optimal solution configuration, and the corresponding ground\-truth objective value\. Each test case explicitly cites its source\.

This format preserves the natural\-language character of the input, ensuring that the benchmark evaluates an LLM’s ability to parse domain\-specific terminology, identify decision variables and constraints, and derive a valid QUBO formulation without relying on pre\-structured inputs\.

### B\.3Problem Sources

The 100 problem instances are curated from three complementary sources to balance rigor, diversity, and coverage\.

##### \(1\) Peer\-reviewed research papers \(76 problems\)\.

The majority of instances are drawn from journal articles and conference papers with verifiable DOIs\. Contributing venues include:

Journals—*The Journal of Finance*,*Management Science*,*Artificial Intelligence*,*PLOS Computational Biology*,*PLOS ONE*,*Nature Scientific Reports*,*npj Quantum Information*,*npj Unconventional Computing*,*Physical Review Research*,*Journal of Chemical Theory and Computation*,*Theoretical Computer Science*,*Quantum Machine Intelligence*,*Quantum Information Processing*,*Annals of Operations Research*,*Journal of Combinatorial Optimization*,*Journal of Optimization Theory and Applications*,*Applied Soft Computing*,*Future Generation Computer Systems*,*Neurocomputing*,*Electric Power Systems Research*,*Discrete Optimization*,*IEEE Transactions on Quantum Engineering*,*IEEE Internet of Things Journal*,*IEEE Computer Graphics and Applications*,*Entropy*,*Applied Sciences*,*Journal of Risk and Financial Management*,*Frontiers in Physics*,*Frontiers in Computer Science*,*Frontiers in ICT*,*Bioinformatics Advances*,*International Journal for Numerical Methods in Engineering*,*EPJ Quantum Technology*,*Results in Engineering*,*Array*,*SN Computer Science*,*Journal of Membrane Computing*,*IEICE Communications Express*, and*Journal of Information Processing*\.

Conferences—*AAAI*,*ACM SIGKDD*,*ACM/SIGDA FPGA*,*IEEE BigData*,*IEEE GLOBECOM*,*IEEE QAI*,*IEEE QCE*,*IEEE EIT*,*ICCSA*,*JSME Robotics and Mechatronics*, and*IFAC*\.

##### \(2\) Competitions and hackathons \(5 problems\)\.

To capture practitioner\-style framings and applied challenges, we include problems posed in:

- •Fixstars Amplify Benchmark Suite
- •Aqora / U\.S\. DOE Global Industry Challenge 2026
- •iQuHACK 2025 D\-Wave Hackathon
- •AtCoder Educational DP Contest
- •D\-Wave Examples Repository

##### \(3\) Canonical NP\-hard problems \(19 problems\)\.

Classical decision and optimization problems including Max\-Cut, Hamiltonian Cycle, Travelling Salesman, Subset Sum, and Vertex Cover which are drawn primarily from Lucas\([Lucas, 2014](https://arxiv.org/html/2609.10629#bib.bib6)\), supplemented with hand\-curated textbook instances\. These problems serve as foundational test cases against which any general\-purpose QUBO\-formulation system should perform reliably\.

All natural\-language prompts and test cases were hand\-curated by the authors to ensure clarity, consistency, and faithful representation of each source problem\.

### B\.4Domain\-wise Distribution

Table[3](https://arxiv.org/html/2609.10629#A2.T3)summarizes the per\-domain distribution of problems and test cases\. Graph theory dominates due to the centrality of graph\-theoretic formulations in the QUBO literature, while domains such as Robotics and Electronics & VLSI remain comparatively sparse, reflecting the relative scarcity of published QUBO formulations in these areas\.

Table 3:Per\-domain distribution of problems and test cases in QUBOBench\.
![Refer to caption](https://arxiv.org/html/2609.10629v1/piechart.png)Figure 2:Per\-domain distribution of problems in QUBOBench\.