QUBOBench — QUBO Formulation Benchmark

Overview

What is QUBOBench?

A comprehensive benchmark for evaluating AI agents on automated QUBO formulation generation.

QUBOBench is a curated benchmark dataset of 100 distinct Quadratic Unconstrained Binary Optimization (QUBO) problems spanning 11 problem domains — from classical graph theory and combinatorial optimization to quantum computing, bioinformatics, machine learning, and beyond.

Each problem in QUBOBench includes a natural language specification describing the optimization objective, binary variable structure, and constraints. Problems are paired with structured test cases and ground-truth solutions that enable fully automatic evaluation of generated QUBO formulations.

QUBOBench is the evaluation backbone for the QuantumQUBO Agent, an LLM-based system that autonomously generates correct, executable QUBO formulations from natural language problem descriptions — a key capability for quantum optimization workflows.

The dataset covers real-world problems sourced from competitive programming judges, quantum computing challenges, domain-specific benchmarks, and original problem designs, ensuring breadth and difficulty diversity.

QUBOBench dataset overview diagram — QUBOBench: 100 optimization problems spanning 11 diverse domains.

Distribution of QUBOBench problems across domains

Problem distribution across 11 domains

Distribution of QUBOBench problem sources

Distribution of problem sources

Dataset

100 QUBO Problems

Browse all problems by domain. Click a category to filter.

Examples

Sample Problems

Each problem consists of a natural language prompt and test cases with ground-truth solutions.

Max-Cut — Natural Language Prompt Prompt

// graph_theory · max_cut/prompt.txt Problem: Given an undirected graph with N nodes and a set of weighted edges, partition the nodes into two groups (labeled 0 and 1) so that the total weight of edges crossing between the two groups is maximized. Variables: Each node i has a binary variable x_i ∈ {0, 1} indicating group membership. Objective: An edge (i, j) with weight w_ij contributes w_ij to the cut if x_i ≠ x_j.

Knapsack — Test Case Test Case

// combinatorial · knapsack/sample_cases.txt Test case 1: 3 items, capacity 8 Items (index, weight, value): 0: w=3, v=30 1: w=4, v=50 2: w=5, v=60 Maximum value = 90 Optimal selection: Items {0, 2} (weight 3+5=8, value 30+60=90) Test case 2: 5 items, capacity 5 (large values — answer exceeds 32-bit int) Maximum value = 5,000,000,000 Optimal selection: Items {0,1,2,3,4} (all items, weight 5=W, value 5×10⁹)

Graph Coloring — Prompt Prompt

// graph_theory · graph_coloring/prompt.txt Problem: Graph K-Coloring Given an undirected graph and K available colors, assign exactly one color to each vertex so that adjacent vertices receive different colors. Task: Find a valid K-coloring if one exists. Objective: Minimize the number of violated edges. A violated edge has both endpoints assigned the same color. In feasibility form, the optimal value is 0 exactly when a valid K-coloring exists. Goal: Return a color assignment and the minimum number of violated edges.

Portfolio Optimization — Prompt Prompt

// finance · portfolio_optimization/prompt.txt Problem: Cardinality-Constrained Portfolio Selection Given a set of assets, choose exactly K assets for a portfolio. Each asset has an expected return score. Each pair of assets has a covariance/risk penalty. Task: Choose exactly K assets. Objective: Maximize the risk-adjusted score: total score = Σ expected return of selected assets − Σ pairwise risk penalties QUBO convention: One binary variable per asset. The exactly-K constraint is encoded as a quadratic penalty term.

Citation

Cite This Work

If you use QUBOBench in your research, please cite our paper.

BibTeX

@inproceedings{
  mondal2026quantumqubo,
  title     = {QuantumQUBO Agent: Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language},
  author    = {Niloy Kumar Mondal and Md Rizwan Parvez},
  booktitle = {ICML 2026 Workshop: AI as a Tool for Mathematics, Computer Science, and Machine Learning},
  year      = {2026},
  url       = {https://openreview.net/forum?id=9YTedapat4}
}