Quadratic Unconstrained Binary Optimization (QUBO) models are defined by quadratic expressions composed of binary variables, each taking a value of either 0 or 1. The objective of the QUBO problem is to find an optimal assignment of these binary variables that minimizes the value of the QUBO model. The QUBO problem has attracted significant research interest due to its versatility in reformulating various NP-complete problems and its potential for efficiently finding heuristic solutions through quantum annealing. This paper focuses on converting Cubic Unconstrained Binary Optimization (CUBO) problems, defined by cubic expressions, into equivalent QUBO models. Through this conversion, CUBO problems can be solved using quantum annealing. Since the important NP-hard problem 3-SAT can be straightforwardly represented as a CUBO problem, investigating the conversion from CUBO to QUBO models is a meaningful endeavor.
Quadratic Unconstrained Binary Optimization (QUBO) models are defined by quadratic expressions composed of binary variables, each taking a value of either 0 or 1. The objective of the QUBO problem is to find an optimal assignment of these binary variables that minimizes the value of the QUBO model. The QUBO problem has attracted significant research interest due to its versatility in reformulating various NP-complete problems and its potential for efficiently finding heuristic solutions through quantum annealing. This paper focuses on converting Cubic Unconstrained Binary Optimization (CUBO) problems, defined by cubic expressions, into equivalent QUBO models. Through this conversion, CUBO problems can be solved using quantum annealing. Since the important NP-hard problem 3-SAT can be straightforwardly represented as a CUBO problem, investigating the conversion from CUBO to QUBO models is a meaningful endeavor.
With the recent advancements in the field of combinatorial optimization, QUBO (quadratic unconstrained binary optimization) has become a topic of intense interest, as a problem format acceptable to several hardware heuristics such as quantum and digital annealers. Accordingly, transforming hard mathematical problems into QUBO problems is of particular importance. In this paper, we restate three problems in NP-complete and NP-hard classes as QUBO problems with proofs of equivalence. Our problems of interest are the numerical three-dimensional matching problem, the monochromatic triangle problem and the optimum facility location problem. Furthermore, we comment on the feasibility of these formulations on sophisticated QUBO solving platforms.
Mixed-integer linear programs (MILPs) are fundamental to power system operations but are challenging to solve due to their NP-hard nature. Quantum annealing, which seeks to find the ground state of an Ising model–a minimization of a quadratic binary function–offers potential speedups for solving combinatorial optimization problems. However, converting MILPs into quadratic unconstrained binary optimization (QUBO) problems often requires lots of slack variables, leading to significant qubit overhead and limiting the capability of quantum annealers. In this work, we propose an efficient formulation approach that generates a QUBO representation of a targeted MILP without introducing auxiliary binary variables. Geometrically, our method approximates the value function of the MILP with a quadratic binary function leveraging a simple convex optimization subroutine. We prove the existence of the QUBO representation, which preserves the MILP’s optimal solution and objective value with the same number of binary variables. The proposed approach is validated on several instances of the security-constrained unit commitment (SCUC) problem, with test cases featuring up to 288 binary variables, demonstrating its efficacy in reducing qubit overhead for quantum-classical hybrid Benders decomposition frameworks.
A Quadratic Unconstrained Binary Optimization (QUBO) model is defined by a quadratic objective function comprising binary variables, each taking values of 0 or 1. The objective of the QUBO problem is to determine the optimal assignment of these binary variables to minimize the QUBO model. QUBO models are instrumental in solving various combinatorial optimization problems, leading to extensive research on solver development, as many combinatorial optimization problems can be reformulated as QUBO problems. Notably, D-Wave Systems, a company specializing in quantum technologies, has developed quantum annealers which are programmable QUBO solvers that utilize quantum mechanics. SHA-1 is a cryptographic hash function that generates a 160-bit hash value from a message of an arbitrary length. This hash value makes it difficult to compute the original message within a practical timeframe. A pre-image attack, which aims to compute the original message from a hash value, is important in cryptographic hash functions. Previous research has shown that a QUBO can be designed to simulate SHA-1, facilitating the execution of a pre-image attack. In this paper, we present a novel QUBO model with fewer bits, linear terms, and quadratic terms than previous QUBO models for simulating hash values and pre-image calculations in SHA-1. While the previous QUBO model requires 34,016 bits, 32,584 linear terms, and 168,188 quadratic terms, our new model requires only 32,096 bits, 26,600 linear terms, and 157,308 quadratic terms. This approach can efficiently execute pre-image attacks using a quantum annealer, providing valuable insights for evaluating the robustness of cryptographic security systems.
The Quadratic Unconstrained Binary Optimization problem (QUBO) is the optimization of a quadratic function where the variables are binary; it is frequently used to model combinatorial problems in operational research and graph theory.QUBO is an NP-Complete problem and a challenge to exact methods.Therefore, the problem has been approached with heuristics.Here, we propose new ideas to solve QUBO with exact methods.We develop a new quadratic formulation that maps the binary problem into an equivalent continuous optimization problem with a single quadratic constraint.A further development delves into Lagrangian inspired concepts to obtain an equivalent unconstrained formulation.The case studies illustrate the benefit and limitations of both formulations.Also, the computational experiments show that problems with up to 2500 variables were solved with processing times under 500 seconds to achieve an average gap under 1%; these results also show that the approach allowed to solve, with an exact method, instances of 1500 more binary variables than the instances considered in previous papers.
Obtaining Quadratic Unconstrained Binary Optimisation models for various optimisation problems, in order to solve those on physical quantum computers (such as the the DWave annealers) is nowadays a lengthy and tedious process that requires one to remodel all problem variables as binary variables and squeeze the target function and the constraints into a single quadratic polynomial into these new variables. We report here on the basis of our automatic converter from MiniZinc to QUBO, which is able to process a large set of constraint optimisation and constraint satisfaction problems and turn them into equivalent QUBOs, effectively optimising the whole process.
Quantum annealing is a model for quantum computing that is aimed at solving hard optimization problems by representing them as quadratic unconstrained binary optimization (QUBO) problems. Although many NP-hard problems can easily be formulated as binary-variable problems with a quadratic objective function, such formulations typically also include constraints, which are not allowed in a QUBO. Hence, such constraints are usually incorporated in the objective function as additive penalty terms. While there is substantial previous work on implementing linear equality constraints, the case of inequality constraints has not much been studied. In this paper, we propose a new approach for formulating and embedding inequality constraints as penalties and describe early implementation results.