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

• URL: http://arxiv.org/abs/2609.10629v2
• Date: Fri, 11 Sep 2026 02:28:17 GMT
• Title: QuantumQUBO Agent: Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language
• Abstract summary: We propose an end-to-end multi-agent framework that automatically generates QUBO formulations from natural-language problem descriptions.<n>We also introduce QUBOBench, a benchmark containing 100 optimization problems across 12 application domains.<n>Our framework achieves 68% accuracy on QUBOBench, outperforming a direct single-call baseline by 22%.
• Score: 8.113418747367573
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Learning Discrete Decisions for MIPs with Constraint-Aware Diffusion [40.25954048196068]
  This paper proposes a novel learning-based approach to approximately solve instances of mixed-integer optimization problems.<n>The proposed method relies on a graph-based generative diffusion model that learns the discrete component of mixed-integer optimization problems.<n>The framework named Constrained Graph Diffusion (CGD) is problem-agnostic and can accommodate a broad class of mixed-integer optimization problems.
  arXiv  Detail & Related papers  (2026-08-13T10:46:18Z)
• CVaR-Assisted Custom Penalty Function for Constrained Optimization [3.652509571098291]
  Constrained optimization problems are frequently reformulated as quadratic unconstrained binary optimization (QUBO) models.<n>Standard QUBO formulations enforce inequality constraints through slack variables and quadratic penalties.<n>We propose a slack-free penalty formulation for constrained binary optimization that eliminates auxiliary slack variables.
  arXiv  Detail & Related papers  (2026-04-22T01:08:38Z)
• Quantum Optimization in Loc(Q)ation Science: QUBO Formulations, Benchmark Problems, and a Computational Study [0.0]
  Quadratic Unconstrained Binary Optimization provides a unifying modeling framework for a broad class of $mathbfNP$-hard problems.<n>We develop QUBO formulations for several fundamental problems in location science, network design, and logistics.<n>These QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware.
  arXiv  Detail & Related papers  (2026-02-11T15:39:26Z)
• Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization [1.3824488054100907]
  We study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces.<n>We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions.<n>Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum optimization.
  arXiv  Detail & Related papers  (2026-02-07T04:37:32Z)
• BONO-Bench: A Comprehensive Test Suite for Bi-objective Numerical Optimization with Traceable Pareto Sets [0.0]
  This paper proposes an extensive problem generation approach for bi-objective numerical optimization problems.<n>It supports configuration of test problem properties, such as the number of decision variables.<n>The general approach underlying our proposed generator is released in the Python package textttbonobench to facilitate reproducible benchmarking.
  arXiv  Detail & Related papers  (2026-01-23T18:42:20Z)
• Closing the Generalization Gap in Parameter-efficient Federated Edge Learning [43.00634399799955]
  Federated edge learning (FEEL) provides a promising foundation for artificial intelligence (AI)<n>limited and heterogeneous local datasets, as well as resource-constrained deployment, severely degrade both model generalization and resource utilization.<n>We propose a framework that jointly leverages model minimization and generalization selection to tackle such challenges.
  arXiv  Detail & Related papers  (2025-11-28T15:34:09Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• Learning Feasible Quantum States for Quadratic Constrained Binary Optimization Problems [41.23247424467223]
  We develop a variational approach that creates an equal superposition of quantum states that satisfy constraints in a QCBO.<n>The resulting equal superposition can be used as an initial state for quantum algorithms that solve QUBOs/QCBOs.
  arXiv  Detail & Related papers  (2025-08-04T16:44:53Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Towards an Automatic Framework for Solving Optimization Problems with Quantum Computers [2.9730678241643815]
  A framework is proposed to automatically convert conventional optimization problems into quantum solvers. The framework offers instruments for analyzing solution validity and quality. It represents a significant advancement towards automating quantum computing solutions.
  arXiv  Detail & Related papers  (2024-06-18T17:56:10Z)
• Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA [4.670374869377859]
  A core step in solving optimization problems with quantum algorithms is the problem formulation. Recent studies show that many problems can be solved more efficiently in their native Polynomial Unconstrained Optimization forms. Our evaluation on suitable benchmark functions, shows that PUBO formulations generally yield better results, while requiring less qubits.
  arXiv  Detail & Related papers  (2023-05-05T09:37:48Z)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.