Given an undirected graph, a matching is a set of edges with no shared vertices. A maximal matching cannot be extended by adding edges without violating this condition. The minimum maximal matching problem seeks the smallest such matching. While it can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, existing methods require complex penalty terms. This paper presents a novel, penalty-free QUBO formulation that is simpler and more intuitive. We analyze its theoretical properties and evaluate its performance using several QUBO solvers. Our approach enhances the practicality of QUBO-based optimization for combinatorial graph problems.
Given an undirected graph, a matching is a set of edges with no shared vertices. A maximal matching cannot be extended by adding edges without violating this condition. The minimum maximal matching problem seeks the smallest such matching. While it can be formulated as a Quadratic Unconstrained Binary Optimization (QUBO) problem, existing methods require complex penalty terms. This paper presents a novel, penalty-free QUBO formulation that is simpler and more intuitive. We analyze its theoretical properties and evaluate its performance using several QUBO solvers. Our approach enhances the practicality of QUBO-based optimization for combinatorial graph problems.
Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The graph isomorphism problem is one of the applications of combinatorial optimization, and is not known to be solvable in polynomial time. The problem is also not known to be NP-complete. We propose four QUBO formulations for graph isomorphism problem instances. We also propose four QUBO formulations for induced subgraph isomorphism problem instances and two QUBO formulations for subgraph isomorphism problem instances, which are NP-complete problems. We solve QUBO instances defined by our QUBO formulations, using known QUBO solvers: Gurobi optimizer, Fixstars Amplify AE and OpenJij with SA.
In this paper, we introduce an approximate quadratic unconstrained binary optimization (QUBO) formulation for satisfiability (SAT) problems derived from real-world applications. The proposed method is an inexact (approximate) formulation of a SAT instance as a QUBO, where the ground state of the QUBO does not correspond to the solution of the SAT instance. The method leverages the fact that practical SAT instances often contain many binary (size 2) clauses, allowing us to use a MAX2SAT formulation directly. In comparative experiments using existing formulations, the proposed method exhibits superior performance on the pigeonhole principle, graph coloring problems, and a subset of instances from the SAT Competition 2023.
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.
In this paper, we introduce an approximated quadratic unconstrained binary optimization (QUBO) formulation on satisfiability (SAT) problems derived from real-world applications. The proposed method is an inexact (approximated) formalization of a SAT instance to a QUBO, where the ground state of the QUBO does not correspond to the solution of the SAT instance. The method leverages the fact that practical SAT instances often contain many binary (size 2) clauses, allowing us to directly use a MAX2SAT formalization. In comparative experiments using existing formulations, the proposed method exhibits superior performance on the pigeonhole principle, graph coloring problems, and a subset of instances from the SAT Competition 2023. Notably, we were able to find the exact solutions of PHP instances using our method, despite its approximate formalization.
In this paper, we introduce an approximated quadratic unconstrained binary optimization (QUBO) formulation on satisfiability (SAT) problems derived from real-world applications. The proposed method is an inexact (approximated) formalization of a SAT instance to a QUBO, where the ground state of the QUBO does not correspond to the solution of the SAT instance. The method leverages the fact that practical SAT instances often contain many binary (size 2) clauses, allowing us to directly use a MAX2SAT formalization. In comparative experiments using existing formulations, the proposed method exhibits superior performance on the pigeonhole principle, graph coloring problems, and a subset of instances from the SAT Competition 2023. Notably, we were able to find the exact solutions of PHP instances using our method, despite its approximate formalization.
Quantum computing has emerged as a promising alternative for solving combinatorial optimization problems. The standard approach for encoding optimization problems on quantum processing units (QPUs) involves transforming them into their Quadratic Unconstrained Binary Optimization (QUBO) representation. However, encoding constraints of optimization problems, particularly inequality constraints, into QUBO requires additional variables, which results in more qubits. Considering the limited availability of qubits in NISQ machines, existing encoding methods fail to scale due to their reliance on large numbers of qubits. We propose a generalized exponential penalty framework for QUBO inequality constraints inspired by a class of exponential functions, which we call exponential penalization. This paper presents an encoding strategy for inequality constraints in combinatorial optimization problems, inspired by a class of exponential functions, which we call exponential penalization. The initial idea of using exponential penalties for QUBO formulation was introduced by Montanez-Barrera et al. by applying a specific exponential function to reduce qubit requirements. In this work, we extend that approach by conducting a comprehensive study on a broader class of exponential functions, analyzing their theoretical properties and empirical performance. Our experimental results demonstrate that an exponential penalization achieves 57%, 83% qubit number reduction for Bin Packing Problem (BPP) and Traveling Salesman Problem (TSP), respectively. And we demonstrate comparable solution quality to classical with a probability of 6% and 21% accuracy for BPP with 8 and TSP with 12 qubits, respectively.