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

arXiv:2404.12797

Conversion of Boolean and Integer FlatZinc Builtins to Quadratic or Linear Integer Problems

Wolf, Armin

Published Apr 19, 2024• 0 citations
arXivHTMLPDF

Abstract

Constraint satisfaction or optimisation models -- even if they are formulated in high-level modelling languages -- need to be reduced into an equivalent format before they can be solved by the use of Quantum Computing. In this paper we show how Boolean and integer FlatZinc builtins over finite-domain integer variables can be equivalently reformulated as linear equations, linear inequalities or binary products of those variables, i.e. as finite-domain quadratic integer programs. Those quadratic integer programs can be further transformed into equivalent Quadratic Unconstrained Binary Optimisation problem models, i.e. a general format for optimisation problems to be solved on Quantum Computers especially on Quantum Annealers.

DOI
10.48550/arxiv.2404.12797

Related papers

Automatic Conversion of MiniZinc Programs to QUBO

Wolf, Armin, Cristian Grozea

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.

arXiv:2307.10032•Jul 19, 2023•1 citation

Converting of Boolean Expression to Linear Equations, Inequalities and QUBO Penalties for Cryptanalysis

A. I. Pakhomchik, Vladimir Voloshinov, V. M. Vinokur +1 more

There exists a wide range of constraint programming (CP) problems defined on Boolean functions depending on binary variables. One of the approaches to solving CP problems is using specific appropriate solvers, e.g., SAT solvers. An alternative is using the generic solvers for mixed-integer linear programming problems (MILP), but they require transforming expressions with Boolean functions to linear equations or inequalities. Here, we present two methods of such a transformation which applies to any Boolean function defined by explicit rules giving values of the Boolean function for all combinations of its Boolean variables. The first method represents the Boolean function as a linear equation in the original binary variables and, possibly, binary ancillaries, which become additional variables of the MILP problem being composed. The second method represents the Boolean function as a set of linear inequalities in the original binary variables and one additional continuous variable (representing the value of the function). The choice between the first or second method is a trade-off between the number of binary variables and number of linear constraints in the emerging MP problem. The advantage of the proposed approach is that both methods reduce important cryptanalysis problems, such as the preimaging of hash functions or breaking symmetric ciphers as the MILP problems, which are solved by the generic MILP solvers. Furthermore, the first method enables to reduce the binary linear equations to quadratic unconstrained binary optimization (QUBO), by the quantum annealer, e.g., D-Wave.

Algorithms•Jan 21, 2022•28 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

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

Shunsuke Tsukiyama, Xiaotian Li, Koji Nakano +5 more

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.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•Jun 3, 2025•1 citation

Comparing QUBO models for quantum annealing: integer encodings for permutation problems

Philippe Codognet

Abstract QUBO (quadratic unconstrained binary optimization) has become the modeling language for quantum annealing and quantum‐inspired annealing solvers. We present different approaches in QUBO for the magic square problem and the quadratic assignment problem (QAP), which can be modeled by linear equations and a permutation constraint over integer variables. Different ways of encoding integers by Booleans in QUBO amount to models, the implementation of which could have very different performance. Experiments performed on the Fixstars Amplify Annealer Engine, a quantum‐inspired annealing solver, show that, compared to the classical one‐hot encoding, using unary encoding for integers performs slightly better for the QAP and much better for magic square.

International Transactions in Operational Research•Apr 30, 2024•17 citations

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
Constraint satisfaction or optimisation models -- even if they are formulated in high-level modelling languages -- need to be reduced into an equivalent format before they can be solved by the use of Quantum Computing. In this paper we show how Boolean and integer FlatZinc builtins over finite-domain integer variables can be equivalently reformulated as linear equations, linear inequalities or binary products of those variables, i.e. as finite-domain quadratic integer programs. Those quadratic integer programs can be further transformed into equivalent Quadratic Unconstrained Binary Optimisation problem models, i.e. a general format for optimisation problems to be solved on Quantum Computers especially on Quantum Annealers.
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.
There exists a wide range of constraint programming (CP) problems defined on Boolean functions depending on binary variables. One of the approaches to solving CP problems is using specific appropriate solvers, e.g., SAT solvers. An alternative is using the generic solvers for mixed-integer linear programming problems (MILP), but they require transforming expressions with Boolean functions to linear equations or inequalities. Here, we present two methods of such a transformation which applies to any Boolean function defined by explicit rules giving values of the Boolean function for all combinations of its Boolean variables. The first method represents the Boolean function as a linear equation in the original binary variables and, possibly, binary ancillaries, which become additional variables of the MILP problem being composed. The second method represents the Boolean function as a set of linear inequalities in the original binary variables and one additional continuous variable (representing the value of the function). The choice between the first or second method is a trade-off between the number of binary variables and number of linear constraints in the emerging MP problem. The advantage of the proposed approach is that both methods reduce important cryptanalysis problems, such as the preimaging of hash functions or breaking symmetric ciphers as the MILP problems, which are solved by the generic MILP solvers. Furthermore, the first method enables to reduce the binary linear equations to quadratic unconstrained binary optimization (QUBO), by the quantum annealer, e.g., D-Wave.
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.
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.
Abstract QUBO (quadratic unconstrained binary optimization) has become the modeling language for quantum annealing and quantum‐inspired annealing solvers. We present different approaches in QUBO for the magic square problem and the quadratic assignment problem (QAP), which can be modeled by linear equations and a permutation constraint over integer variables. Different ways of encoding integers by Booleans in QUBO amount to models, the implementation of which could have very different performance. Experiments performed on the Fixstars Amplify Annealer Engine, a quantum‐inspired annealing solver, show that, compared to the classical one‐hot encoding, using unary encoding for integers performs slightly better for the QAP and much better for magic square.
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.