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

International Conference on Algorithms, Computing and Systems (ICACS)

On Optimal QUBO Encoding of Boolean Logic, (Max-)3-SAT and (Max-)k-SAT with Integer Programming

Gregory Morse, Tamás Kozsik

Published Oct 19, 2023• 3 citations
Publisher

Abstract

We present an asymptotic improvement in the number of variables (n + m⌊log 2(k − 1)⌋) required for state-of-the-art formulation of (max-)k-SAT problems when encoded as a quadratic unconstrained binary optimization (QUBO) problem. We further show a variable reduction technique (max-)3-SAT formula which achieves the optimal number of substitution variables. We show optimality empirically by presenting an integer linear programming (ILP) construction for arbitrary Boolean formulas. We show how various goals can be encoded, and this model can be generalized to searching for arbitrary substitution variable functions. Lastly, we show the optimal high-order substitution reduction in cubic QUBO equations which has smaller coefficients than the typical construction used.

DOI
10.1145/3631908.3631929

Related papers

A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions

Gregory Morse, Tamás Kozsik, Oskar Mencer +1 more

We aim to advance the state-of-the-art in Quadratic Unconstrained Binary Optimization formulation with a focus on cryptography algorithms. As the minimal QUBO encoding of the linear constraints of optimization problems emerges as the solution of integer linear programming (ILP) problems, by solving special boolean logic formulas (like ANF and DNF) for their integer coefficients it is straightforward to handle any normal form, or any substitution for multi-input AND, OR or XOR operations in a QUBO form. To showcase the efficiency of the proposed approach we considered the most widespread cryptography algorithms including AES-128/192/256, MD5, SHA1 and SHA256. For each of these, we achieved QUBO instances reduced by thousands of logical variables compared to previously published results, while keeping the QUBO matrix sparse and the magnitude of the coefficients low. In the particular case of AES-256 cryptography function we obtained more than 8x reduction in variable count compared to previous results. The demonstrated reduction in QUBO sizes notably increases the vulnerability of cryptography algorithms against future quantum annealers, capable of embedding around $30$ thousands of logical variables.

arXiv:2409.07501•Sep 10, 2024•2 citations

Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions

Amit Verma, Mark W. Lewis, Gary A. Kochenberger

Quadratic Unconstrained Binary Optimization (QUBO) is recognized as a unifying framework for modeling a wide range of problems. Problems can be solved with commercial solvers customized for solving QUBO and since QUBO have degree two, it is useful to have a method for transforming higher degree pseudo-Boolean problems to QUBO format. The standard transformation approach requires additional auxiliary variables supported by penalty terms for each higher degree term. This paper improves on the existing cubic-to-quadratic transformation approach by minimizing the number of additional variables as well as penalty coefficient. Extensive experimental testing on Max 3-SAT modeled as QUBO shows a near 100% reduction in the subproblem size used for minimization of the number of auxiliary variables.

arXiv:2107.11695•Jul 24, 2021•12 citations

Efficient digital quadratic unconstrained binary optimization solvers for SAT problems

Robert Simon Fong, Yanming Song, Alexander Yosifov

Abstract Boolean satisfiability (SAT) is a propositional logic problem of determining whether an assignment of variables satisfies a Boolean formula. Many combinatorial optimization problems can be formulated in Boolean SAT logic—either as k-SAT decision problems or Max k-SAT optimization problems, with conflict-driven clause learning (CDCL) solvers being the most prominent. Despite their ability to handle large instances, CDCL-based solvers have fundamental scalability limitations. In light of this, we propose recently-developed quadratic unconstrained binary optimization (QUBO) solvers as an alternative platform for 3-SAT problems. To utilize them, we implement a 2-step [3-SAT]-[Max 2-SAT]-[QUBO] conversion procedure and present a novel approach using linear systems and Diophantine equation to calculate the number of both satisfied and violated clauses of the original 3-SAT instance from the transformed Max 2-SAT formulation. We then demonstrate, through numerical simulations on several benchmark instances, that digital QUBO solvers can achieve state-of-the-art accuracy on 78-variable 3-SAT benchmark problems. Our work facilitates the broader use of quantum annealers on noisy intermediate-scale quantum devices, as well as their quantum-inspired digital counterparts, for solving 3-SAT problems.

arXiv:2408.03757•New Journal of Physics•Jan 1, 2025•3 citations

Encoding Binary Comparison Constraints in QUBO for Quantum Annealing

Philippe Codognet

We consider the encoding in Quadratic Unconstrained Binary Optimization (QUBO) of binary comparison constraints, that is, constraints of the form x < y + c, x ≤ y + c, and x = y + c, where x and y are two integer variables and c is an integer constant. For the sake of simplicity, we will consider that x and y are bounded and belong to the same interval {1,..., n}. We will show that such constraints can be encoded without the need of any extra-variable, conversely to the general scheme for linear inequations, which requires between n - 1 and ⌈log2(n - 1)⌉ extra-variables, depending on the encoding chosen for integers. Limiting the number of extra-variables needed in QUBO formulations is important as each Boolean QUBO variable will be implemented as a (logical) qubit on a quantum device and the number of such qubits is limited in quantum annealing systems such as D-Wave machines.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•1 citation

Resource-Constrained Heuristic for Max-SAT

Brian Matejek, Daniel Elenius, Cale M. Gentry +2 more

We propose a resource-constrained heuristic for instances of Max-SAT that iteratively decomposes a larger problem into smaller subcomponents that can be solved by optimized solvers and hardware. The unconstrained outer loop maintains the state space of a given problem and selects a subset of the SAT variables for optimization independent of previous calls. The resource-constrained inner loop maximizes the number of satisfiable clauses in the "sub-SAT" problem. Our outer loop is agnostic to the mechanisms of the inner loop, allowing for the use of traditional solvers for the optimization step. However, we can also transform the selected "sub-SAT" problem into a quadratic unconstrained binary optimization (QUBO) one and use specialized hardware for optimization. In contrast to existing solutions that convert a SAT instance into a QUBO one before decomposition, we choose a subset of the SAT variables before QUBO optimization. We analyze a set of variable selection methods, including a novel graph-based method that exploits the structure of a given SAT instance. The number of QUBO variables needed to encode a (sub-)SAT problem varies, so we additionally learn a model that predicts the size of sub-SAT problems that will fit a fixed-size QUBO solver. We empirically demonstrate our results on a set of randomly generated Max-SAT instances as well as real world examples from the Max-SAT evaluation benchmarks and outperform existing QUBO decomposer solutions.

arXiv:2410.09173•Oct 11, 2024•1 citation

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
We present an asymptotic improvement in the number of variables (n + m⌊log 2(k − 1)⌋) required for state-of-the-art formulation of (max-)k-SAT problems when encoded as a quadratic unconstrained binary optimization (QUBO) problem. We further show a variable reduction technique (max-)3-SAT formula which achieves the optimal number of substitution variables. We show optimality empirically by presenting an integer linear programming (ILP) construction for arbitrary Boolean formulas. We show how various goals can be encoded, and this model can be generalized to searching for arbitrary substitution variable functions. Lastly, we show the optimal high-order substitution reduction in cubic QUBO equations which has smaller coefficients than the typical construction used.
We aim to advance the state-of-the-art in Quadratic Unconstrained Binary Optimization formulation with a focus on cryptography algorithms. As the minimal QUBO encoding of the linear constraints of optimization problems emerges as the solution of integer linear programming (ILP) problems, by solving special boolean logic formulas (like ANF and DNF) for their integer coefficients it is straightforward to handle any normal form, or any substitution for multi-input AND, OR or XOR operations in a QUBO form. To showcase the efficiency of the proposed approach we considered the most widespread cryptography algorithms including AES-128/192/256, MD5, SHA1 and SHA256. For each of these, we achieved QUBO instances reduced by thousands of logical variables compared to previously published results, while keeping the QUBO matrix sparse and the magnitude of the coefficients low. In the particular case of AES-256 cryptography function we obtained more than 8x reduction in variable count compared to previous results. The demonstrated reduction in QUBO sizes notably increases the vulnerability of cryptography algorithms against future quantum annealers, capable of embedding around 303030 thousands of logical variables.
Quadratic Unconstrained Binary Optimization (QUBO) is recognized as a unifying framework for modeling a wide range of problems. Problems can be solved with commercial solvers customized for solving QUBO and since QUBO have degree two, it is useful to have a method for transforming higher degree pseudo-Boolean problems to QUBO format. The standard transformation approach requires additional auxiliary variables supported by penalty terms for each higher degree term. This paper improves on the existing cubic-to-quadratic transformation approach by minimizing the number of additional variables as well as penalty coefficient. Extensive experimental testing on Max 3-SAT modeled as QUBO shows a near 100% reduction in the subproblem size used for minimization of the number of auxiliary variables.
Abstract Boolean satisfiability (SAT) is a propositional logic problem of determining whether an assignment of variables satisfies a Boolean formula. Many combinatorial optimization problems can be formulated in Boolean SAT logic—either as k-SAT decision problems or Max k-SAT optimization problems, with conflict-driven clause learning (CDCL) solvers being the most prominent. Despite their ability to handle large instances, CDCL-based solvers have fundamental scalability limitations. In light of this, we propose recently-developed quadratic unconstrained binary optimization (QUBO) solvers as an alternative platform for 3-SAT problems. To utilize them, we implement a 2-step [3-SAT]-[Max 2-SAT]-[QUBO] conversion procedure and present a novel approach using linear systems and Diophantine equation to calculate the number of both satisfied and violated clauses of the original 3-SAT instance from the transformed Max 2-SAT formulation. We then demonstrate, through numerical simulations on several benchmark instances, that digital QUBO solvers can achieve state-of-the-art accuracy on 78-variable 3-SAT benchmark problems. Our work facilitates the broader use of quantum annealers on noisy intermediate-scale quantum devices, as well as their quantum-inspired digital counterparts, for solving 3-SAT problems.
We consider the encoding in Quadratic Unconstrained Binary Optimization (QUBO) of binary comparison constraints, that is, constraints of the form x < y + c, x ≤ y + c, and x = y + c, where x and y are two integer variables and c is an integer constant. For the sake of simplicity, we will consider that x and y are bounded and belong to the same interval {1,..., n}. We will show that such constraints can be encoded without the need of any extra-variable, conversely to the general scheme for linear inequations, which requires between n - 1 and ⌈log2(n - 1)⌉ extra-variables, depending on the encoding chosen for integers. Limiting the number of extra-variables needed in QUBO formulations is important as each Boolean QUBO variable will be implemented as a (logical) qubit on a quantum device and the number of such qubits is limited in quantum annealing systems such as D-Wave machines.
We propose a resource-constrained heuristic for instances of Max-SAT that iteratively decomposes a larger problem into smaller subcomponents that can be solved by optimized solvers and hardware. The unconstrained outer loop maintains the state space of a given problem and selects a subset of the SAT variables for optimization independent of previous calls. The resource-constrained inner loop maximizes the number of satisfiable clauses in the "sub-SAT" problem. Our outer loop is agnostic to the mechanisms of the inner loop, allowing for the use of traditional solvers for the optimization step. However, we can also transform the selected "sub-SAT" problem into a quadratic unconstrained binary optimization (QUBO) one and use specialized hardware for optimization. In contrast to existing solutions that convert a SAT instance into a QUBO one before decomposition, we choose a subset of the SAT variables before QUBO optimization. We analyze a set of variable selection methods, including a novel graph-based method that exploits the structure of a given SAT instance. The number of QUBO variables needed to encode a (sub-)SAT problem varies, so we additionally learn a model that predicts the size of sub-SAT problems that will fit a fixed-size QUBO solver. We empirically demonstrate our results on a set of randomly generated Max-SAT instances as well as real world examples from the Max-SAT evaluation benchmarks and outperform existing QUBO decomposer solutions.
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.