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:1910.13583

All 4-variable functions can be perfectly quadratized with only 1 auxiliary variable

Nike Dattani, Hou Tin Chau

Published Oct 29, 2019• 7 citations
arXivHTMLPDF

Abstract

We prove that any function with real-valued coefficients, whose input is 4 binary variables and whose output is a real number, is perfectly equivalent to a quadratic function whose input is 5 binary variables and is minimized over the new variable. Our proof is constructive: we provide quadratizations for all possible 4-variable functions. There exists 4 different classes of 4-variable functions that each have their own 5-variable quadratization formula. Since we provide 'perfect' quadratizations, we can apply these formulas to any 4-variable subset of an n-variable function even if n >> 4. We provide 5 examples of functions that can be quadratized using the result of this work. For each of the 5 examples we compare the best possible quadratization we could construct using previously known methods, to a quadratization that we construct using our new result. In the most extreme example, the quadratization using our new result needs only N auxiliary variables for a 4N-variable degree-4 function, whereas the previous state-of-the-art quadratization requires 2N (double as many) auxiliary variables and therefore we can reduce by the cost of optimizing such a function by a factor of 2^1000 if it were to have 4000 variables before quadratization. In all 5 of our examples, the range of coefficient sizes in our quadratic function is smaller than in the previous state-of-the-art one, and our coefficient range is a factor of 7 times smaller in our 15-term, 5-variable example of a degree-4 function.

DOI
10.48550/arxiv.1910.13583

Related papers

Quadratizations of symmetric pseudo-Boolean functions: sub-linear bounds on the number of auxiliary variables

Endre Boros, Yves Crama, Elisabeth Rodríguez-Heck

The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications.A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques.Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials.A desirable property for a quadratization is to introduce small number of auxiliary variables.For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular.However, much less is known for positive monomials.The best lower bound on the number of variables required by a quadratization in the literature is n-1 2 .We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound.This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact kout-of-n functions, which is a more general class of symmetric functions.Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization.Finally, we provide quadratizations for general symmetric functions using O( √ n) auxiliary variables.This upper bound nicely matches a lower bound of Ω( √ n) variables that was recently introduced.

ISAIM•Jan 4, 2018•7 citations

Sharp sparse quadratization of weighted quartic Boolean costs

Robert Barritz

A quadratization represents a Boolean cost by minimizing a quadratic cost over auxiliary variables. For a four-variable family with one positive quartic coefficient and six sufficiently negative quadratic coefficients, this work determines the exact uniform error with at most six genuine pair interactions, allowing any finite auxiliary set. The optimum is the minimum of an explicit quadratic fallback and thirty-nine scalar capacities, explained by three response mechanisms. Interval endpoints and rational max flow construct attaining nonnegative rational networks with at most two auxiliary variables, without optimization linear programs. A structural lower bound covers all finite auxiliary sets. The paper also gives the separate one-auxiliary seven-, eight- and nine-interaction formulas, the one-auxiliary six-interaction procedure with 57 rational linear programs, and an exact interaction frontier. Absolute costs are retained. The results are proof-supported candidate theorems for this structured family; no claim about arbitrary quartic targets or hardware performance is made.

•Oct 27, 2026•0 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

Compressed Quadratization of Higher Order Binary Optimization Problems

Avradip Mandal, Arnab Roy, Sarvagya Upadhyay +1 more

Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space or in Boolean space. Many naturally occurring problem instances are higher-order in nature. The known method to reduce the degree of a higher-order optimization problem uses Rosenberg's polynomial. The method works in Boolean space by reducing the degree of one term by introducing one extra variable. In this work, we prove that in Ising space the degree reduction of one term requires the introduction of two variables. Our proposed method of degree reduction works directly in Ising space, as opposed to converting an Ising polynomial to Boolean space and applying previously known Rosenberg's polynomial. For sparse higher-order Ising problems, this results in a more compact representation of the resultant QUBO problem, which is crucial for utilizing resource-constrained QUBO solvers.

arXiv:2001.00658•DCC•Mar 1, 2020•45 citations

A Simple Heuristic for Expressing a Truth Table as a Quadratic Pseudo-Boolean Function

Scott Pakin

Quadratic pseudo-Boolean functions (i.e., quadratic functions with real-valued coefficients and two-valued variables) are the native input to quantum annealers and also a common problem format to optimize with the QAOA algorithm on circuitmodel quantum computers. In both cases, large, complex optimization problems can be expressed in terms of combinations of simpler problems. A key challenge in problem set-up lies in finding the coefficients for the constituent sub-problems. These need to be chosen such that the function is minimized on valid inputs and is higher elsewhere. One difficulty is that it is not possible in general to solve for a sub-problem’s coefficients without introducing ancillary variables, the number of which and their corresponding per-row values being unknown a priori. These unknowns lead to solving for a sub-problem’s coefficients being an NP-complete problem.In this paper we present a simple heuristic that considers a prioritized subset of the exponential number of possibilities for each per-row ancillary variable. Using this heuristic, coefficients can be found substantially faster than would be possible using a brute-force search and with less software complexity than is required by prior approaches.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2021•2 citations

Variable Reduction For Quadratic Unconstrained Binary Optimization

Amit Verma, Mark W. Lewis

Quadratic Unconstrained Binary Optimization models are useful for solving a diverse range of optimization problems. Constraints can be added by incorporating quadratic penalty terms into the objective, often with the introduction of slack variables needed for conversion of inequalities. This transformation can lead to a significant increase in the size and density of the problem. Herein, we propose an efficient approach for recasting inequality constraints that reduces the number of linear and quadratic variables. Experimental results illustrate the efficacy.

arXiv:2105.07032•May 14, 2021•7 citations
We prove that any function with real-valued coefficients, whose input is 4 binary variables and whose output is a real number, is perfectly equivalent to a quadratic function whose input is 5 binary variables and is minimized over the new variable. Our proof is constructive: we provide quadratizations for all possible 4-variable functions. There exists 4 different classes of 4-variable functions that each have their own 5-variable quadratization formula. Since we provide 'perfect' quadratizations, we can apply these formulas to any 4-variable subset of an n-variable function even if n >> 4. We provide 5 examples of functions that can be quadratized using the result of this work. For each of the 5 examples we compare the best possible quadratization we could construct using previously known methods, to a quadratization that we construct using our new result. In the most extreme example, the quadratization using our new result needs only N auxiliary variables for a 4N-variable degree-4 function, whereas the previous state-of-the-art quadratization requires 2N (double as many) auxiliary variables and therefore we can reduce by the cost of optimizing such a function by a factor of 2^1000 if it were to have 4000 variables before quadratization. In all 5 of our examples, the range of coefficient sizes in our quadratic function is smaller than in the previous state-of-the-art one, and our coefficient range is a factor of 7 times smaller in our 15-term, 5-variable example of a degree-4 function.
The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications.A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques.Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials.A desirable property for a quadratization is to introduce small number of auxiliary variables.For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular.However, much less is known for positive monomials.The best lower bound on the number of variables required by a quadratization in the literature is n-1 2 .We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound.This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact kout-of-n functions, which is a more general class of symmetric functions.Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization.Finally, we provide quadratizations for general symmetric functions using O( √ n) auxiliary variables.This upper bound nicely matches a lower bound of Ω( √ n) variables that was recently introduced.
A quadratization represents a Boolean cost by minimizing a quadratic cost over auxiliary variables. For a four-variable family with one positive quartic coefficient and six sufficiently negative quadratic coefficients, this work determines the exact uniform error with at most six genuine pair interactions, allowing any finite auxiliary set. The optimum is the minimum of an explicit quadratic fallback and thirty-nine scalar capacities, explained by three response mechanisms. Interval endpoints and rational max flow construct attaining nonnegative rational networks with at most two auxiliary variables, without optimization linear programs. A structural lower bound covers all finite auxiliary sets. The paper also gives the separate one-auxiliary seven-, eight- and nine-interaction formulas, the one-auxiliary six-interaction procedure with 57 rational linear programs, and an exact interaction frontier. Absolute costs are retained. The results are proof-supported candidate theorems for this structured family; no claim about arbitrary quartic targets or hardware performance is made.
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.
Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space or in Boolean space. Many naturally occurring problem instances are higher-order in nature. The known method to reduce the degree of a higher-order optimization problem uses Rosenberg's polynomial. The method works in Boolean space by reducing the degree of one term by introducing one extra variable. In this work, we prove that in Ising space the degree reduction of one term requires the introduction of two variables. Our proposed method of degree reduction works directly in Ising space, as opposed to converting an Ising polynomial to Boolean space and applying previously known Rosenberg's polynomial. For sparse higher-order Ising problems, this results in a more compact representation of the resultant QUBO problem, which is crucial for utilizing resource-constrained QUBO solvers.
Quadratic pseudo-Boolean functions (i.e., quadratic functions with real-valued coefficients and two-valued variables) are the native input to quantum annealers and also a common problem format to optimize with the QAOA algorithm on circuitmodel quantum computers. In both cases, large, complex optimization problems can be expressed in terms of combinations of simpler problems. A key challenge in problem set-up lies in finding the coefficients for the constituent sub-problems. These need to be chosen such that the function is minimized on valid inputs and is higher elsewhere. One difficulty is that it is not possible in general to solve for a sub-problem’s coefficients without introducing ancillary variables, the number of which and their corresponding per-row values being unknown a priori. These unknowns lead to solving for a sub-problem’s coefficients being an NP-complete problem.In this paper we present a simple heuristic that considers a prioritized subset of the exponential number of possibilities for each per-row ancillary variable. Using this heuristic, coefficients can be found substantially faster than would be possible using a brute-force search and with less software complexity than is required by prior approaches.
Quadratic Unconstrained Binary Optimization models are useful for solving a diverse range of optimization problems. Constraints can be added by incorporating quadratic penalty terms into the objective, often with the introduction of slack variables needed for conversion of inequalities. This transformation can lead to a significant increase in the size and density of the problem. Herein, we propose an efficient approach for recasting inequality constraints that reduces the number of linear and quadratic variables. Experimental results illustrate the efficacy.