Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum

CUBO-to-QUBO Conversion: Reducing Cubic Formulations to Quadratic Formulations

Shunsuke Tsukiyama, Xiaotian Li, Koji Nakano, Victor Parque, Yasuaki Ito, Takumi Kato, Yuya Kawamata, Kaiki Ii

Published Jun 3, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.1109/ipdpsw66978.2025.00096

Related papers

QUBO formulations of three NP problems

Anuradha Mahasinghe, Vishmi Fernando, Paduma Samarawickrama

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.

Journal of Information and Optimization Sciences•Oct 3, 2021•10 citations

Breaking SHA-1 through QUBO models

Shunsuke Tsukiyama, Koji Nakano, Yasuaki Ito +2 more

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.

International Symposium on Computing and Networking Workshops (CANDARW)•Nov 26, 2024•0 citations

Toward Fast Quantum-Classical Hybrid Benders Decomposition for the SCUC Problem: An Efficient Approximate Formulation of QUBOs

Xiaodong Zheng, Jiahua Yang, Baorong Zhou

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.

IEEE Power Engineering Society General Meeting•Jul 27, 2025•1 citation

Uma reformulação quadrática para variáveis binárias aplicadas ao problema de otimização quadrática irrestrita

Petra Maria Bartmeyer, Christiano Lyra

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.

Anais do Simpósio Brasileiro de Pesquisa Operacional•Jan 1, 2018•0 citations

Embedding Inequality Constraints for Quantum Annealing Optimization.

Tomáš Vyskočil, Scott Pakin, Hristo N. Djidjev

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.

•Jan 1, 2017•0 citations

New algorithms for Quadratic Unconstrained Binary Optimization (QUBO) with applications in engineering and social sciences

Tavares, Gabriel

This dissertation investigates the Quadratic Unconstrained Binary Optimization (QUBO) problem, i.e. the problem of minimizing a quadratic function in binary variables. QUBO is studied at two complementary levels. First, there is an algorithmic aspect that tells how to preprocess the problem, how to find heuristics, how to get improved bounds and how to solve the problem with all the above ingredients.Second, there is a practical aspect that uses QUBO to solve various applications from the engineering and social sciences fields including: via minimization, 2D/3D Ising models, 1D Ising chain models, image binarization, hierarchical clustering, greedy graph coloring/partitioning, MAX-2-SAT, MIN-VC, MAX-CLIQUE, MAX-CUT, graph stability and minimum k-partition.Several families of fast heuristics for QUBO are analyzed, which include a novel probabilistic based class of methods.It is shown that there is a unique maximal set of persistencies for the linearization model for QUBO.This set is determined in polynomial time by a maximum flow followed by the computation of the strong components of a network that has 2n+2 nodes, where n is the number of variables. The identification of the above persistencies leads to a unique decomposition of the function, such that each component can be optimized separately. To find further persistencies, two additional techniques are proposed: one is based on the second order derivatives of Hammer et al. [HH81]; the other technique is a probing procedure on the two possible values of the variables.These preprocessing tools work remarkably well for certain classes of problems.We improved the Iterated Roof-Dual bound (IRD) of [BH89] by proposing two combinatorial methods: one was named the squeezed IRD; and the second was called the project-and-lift IRD method.The cubic-dual bound can be found by means of linear programming by adding a set of triangle inequalities to the standard linearization, whose number is cubic in the number of variables. We show that this set can be reduced depending on the coefficients of the terms of the function. This leads to the possibility of computing the cubic-duals of larger QUBOs.

•Jan 1, 2008•8 citations
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.
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.
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.
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.
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.
This dissertation investigates the Quadratic Unconstrained Binary Optimization (QUBO) problem, i.e. the problem of minimizing a quadratic function in binary variables. QUBO is studied at two complementary levels. First, there is an algorithmic aspect that tells how to preprocess the problem, how to find heuristics, how to get improved bounds and how to solve the problem with all the above ingredients.Second, there is a practical aspect that uses QUBO to solve various applications from the engineering and social sciences fields including: via minimization, 2D/3D Ising models, 1D Ising chain models, image binarization, hierarchical clustering, greedy graph coloring/partitioning, MAX-2-SAT, MIN-VC, MAX-CLIQUE, MAX-CUT, graph stability and minimum k-partition.Several families of fast heuristics for QUBO are analyzed, which include a novel probabilistic based class of methods.It is shown that there is a unique maximal set of persistencies for the linearization model for QUBO.This set is determined in polynomial time by a maximum flow followed by the computation of the strong components of a network that has 2n+2 nodes, where n is the number of variables. The identification of the above persistencies leads to a unique decomposition of the function, such that each component can be optimized separately. To find further persistencies, two additional techniques are proposed: one is based on the second order derivatives of Hammer et al. [HH81]; the other technique is a probing procedure on the two possible values of the variables.These preprocessing tools work remarkably well for certain classes of problems.We improved the Iterated Roof-Dual bound (IRD) of [BH89] by proposing two combinatorial methods: one was named the squeezed IRD; and the second was called the project-and-lift IRD method.The cubic-dual bound can be found by means of linear programming by adding a set of triangle inequalities to the standard linearization, whose number is cubic in the number of variables. We show that this set can be reduced depending on the coefficients of the terms of the function. This leads to the possibility of computing the cubic-duals of larger QUBOs.