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

Quadratic Unconstrained Binary Optimization (QUBO) is a critical mathematical framework for solving combinatorial optimization problems on quantum and hybrid solvers. However, translating natural-language problem descriptions into valid QUBO formulations is a complex, error-prone task that requires significant domain expertise to identify variables, constraints, and penalty terms. Existing approaches often struggle with the end-to-end translation process, leading to the development of the QuantumQUBO Agent.

The authors propose a multi-agent framework that decomposes the formulation process into specialized roles: a Planner (extracts variables and constraints), a Formulizer (derives the QUBO cost function), a Judge (ensures consistency), a Debugger (handles test cases), and a Coder (generates executable Python code). This pipeline incorporates iterative feedback loops where agents refine their outputs based on critiques from the Judge or failures identified by a deterministic Test Runner. To evaluate this, the authors introduced QUBOBench, a comprehensive dataset of 100 combinatorial optimization problems across 12 domains, ranging from graph theory to computational biology.

The QuantumQUBO Agent achieved 68% accuracy on the QUBOBench dataset, a 22 percentage point improvement over a direct, single-call LLM baseline. Ablation studies revealed that iterative self-repair is the most critical component for success; removing this feedback mechanism caused performance to drop to 35%. Furthermore, error analysis showed that while the direct method struggles primarily with the mathematical formulation of QUBOs, the QuantumQUBO Agent successfully resolves most mathematical ambiguities, with the majority of its remaining errors being simple coding bugs.

This research demonstrates that agentic workflows with iterative feedback can effectively bridge the gap between natural language and complex mathematical optimization. By automating the formulation of QUBOs, this framework lowers the barrier to entry for researchers and practitioners looking to leverage quantum and quantum-inspired solvers for real-world optimization tasks.