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

A polynomial-time algorithm for optimization of quadratic pseudo-boolean functions

Mulero Martínez, Juan Ignacio

Published May 13, 2020• 0 citations
OpenAlex

Abstract

We develop a polynomial-time algorithm to minimize pseudo-Boolean functions. The computational complexity is O(n □(15/2)), although very conservative, it is su_cient to prove that this minimization problem is in the class P. A direct application of the algorithm is the 3-SAT problem, which is also guaranteed to be in the class P with a computational complexity of order O(n □(45/2)). The algorithm was implemented in MATLAB and checked by generating one million matrices of arbitrary dimension up to 24 with random entries in the range [-50; 50]. All the experiments were successful.

Related papers

A Polynomial-Time Algorithm for Unconstrained Binary Quadratic Optimization

Juan Ignacio Mulero-Martínez

In this paper, an exact algorithm in polynomial time is developed to solve unrestricted binary quadratic programs. The computational complexity is $O\left( n^{\frac{15}{2}}\right) $, although very conservative, it is sufficient to prove that this minimization problem is in the complexity class $P$. The implementation aspects are also described in detail with a special emphasis on the transformation of the quadratic program into a linear program that can be solved in polynomial time. The algorithm was implemented in MATLAB and checked by generating five million matrices of arbitrary dimensions up to 30 with random entries in the range $\left[ -50,50\right] $. All the experiments carried out have revealed that the method works correctly.

arXiv:2005.07030•May 13, 2020•0 citations

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

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•1 citation

Quadratic reformulations for the optimization of pseudo-boolean functions

Yves Crama, Sourour Elloumi, Amélie Lambert +1 more

We investigate various solution approaches for the uncon-strained minimization of a pseudo-boolean function. Moreprecisely, we assume that the original function is expressedas a real-valued polynomial in 0-1 variables, of degree threeor more, and we consider a generic family of two-step ap-proaches for its minimization. First, a quadratic reformu-lation step aims at transforming the minimization probleminto an equivalent constrained or unconstrained quadratic0-1 minimization problem (where “equivalent” means herethat a minimizer of the original function can be easily de-duced from a minimizer of the reformulation). Second, anoptimization step handles the obtained equivalent quadraticproblem.We provide a unified presentation of several quadratic re-formulation schemes proposed in the literature, e.g., (An-thony et al. 2017; Buchheim and Rinaldi 2007; Rodr ́ıguez-Heck 2018; Rosenberg 1975), and we review several meth-ods that can be applied in the optimization step, includinga standard linearization procedure (Fortet 1959) and moreelaborate convex quadratic reformulations, as in (Billionnetand Elloumi 2007; Billionnet, Elloumi, and Lambert 2012,2016; Elloumi, Lambert, and Lazare 2021). We discuss theimpact of the reformulation scheme on the efficiency of theoptimization step and we illustrate our discussion with somecomputational results on different classes of instances.

•Jan 3, 2022•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•5 citations

Algorithms for Boolean Function Query Properties

Scott Aaronson

We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N=2 n ) as input. Our main results are the following: O(N log 2 3 log N) algorithms for many common properties, an O(N log 2 5 log N) algorithm for block sensitivity, an O(N) algorithm for testing "quasi symmetry," a notion of a "tree decomposition" of a Boolean function, proof that the decomposition is unique, and an O(N log 2 3 log N) algorithm for finding it, a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic. The algorithms discussed have been implemented in a linkable library.

arXiv:cs/0107010•SIAM Journal on Computing•Jan 1, 2003•17 citations
We develop a polynomial-time algorithm to minimize pseudo-Boolean functions. The computational complexity is O(n □(15/2)), although very conservative, it is su_cient to prove that this minimization problem is in the class P. A direct application of the algorithm is the 3-SAT problem, which is also guaranteed to be in the class P with a computational complexity of order O(n □(45/2)). The algorithm was implemented in MATLAB and checked by generating one million matrices of arbitrary dimension up to 24 with random entries in the range [-50; 50]. All the experiments were successful.
In this paper, an exact algorithm in polynomial time is developed to solve unrestricted binary quadratic programs. The computational complexity is $O\left( n^{\frac{15}{2}}\right) $, although very conservative, it is sufficient to prove that this minimization problem is in the complexity class PPP. The implementation aspects are also described in detail with a special emphasis on the transformation of the quadratic program into a linear program that can be solved in polynomial time. The algorithm was implemented in MATLAB and checked by generating five million matrices of arbitrary dimensions up to 30 with random entries in the range $\left[ -50,50\right] $. All the experiments carried out have revealed that the method works correctly.
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.
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.
We investigate various solution approaches for the uncon-strained minimization of a pseudo-boolean function. Moreprecisely, we assume that the original function is expressedas a real-valued polynomial in 0-1 variables, of degree threeor more, and we consider a generic family of two-step ap-proaches for its minimization. First, a quadratic reformu-lation step aims at transforming the minimization probleminto an equivalent constrained or unconstrained quadratic0-1 minimization problem (where “equivalent” means herethat a minimizer of the original function can be easily de-duced from a minimizer of the reformulation). Second, anoptimization step handles the obtained equivalent quadraticproblem.We provide a unified presentation of several quadratic re-formulation schemes proposed in the literature, e.g., (An-thony et al. 2017; Buchheim and Rinaldi 2007; Rodr ́ıguez-Heck 2018; Rosenberg 1975), and we review several meth-ods that can be applied in the optimization step, includinga standard linearization procedure (Fortet 1959) and moreelaborate convex quadratic reformulations, as in (Billionnetand Elloumi 2007; Billionnet, Elloumi, and Lambert 2012,2016; Elloumi, Lambert, and Lazare 2021). We discuss theimpact of the reformulation scheme on the efficiency of theoptimization step and we illustrate our discussion with somecomputational results on different classes of instances.
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.
We investigate efficient algorithms for computing Boolean function properties relevant to query complexity. Such properties include, for example, deterministic, randomized, and quantum query complexities; block sensitivity; certificate complexity; and degree as a real polynomial. The algorithms compute the properties, given an n-variable function's truth table (of size N=2 n ) as input. Our main results are the following: O(N log 2 3 log N) algorithms for many common properties, an O(N log 2 5 log N) algorithm for block sensitivity, an O(N) algorithm for testing "quasi symmetry," a notion of a "tree decomposition" of a Boolean function, proof that the decomposition is unique, and an O(N log 2 3 log N) algorithm for finding it, a subexponential-time approximation algorithm for space-bounded quantum query complexity. To develop this algorithm, we give a new way to search systematically through unitary matrices using finite-precision arithmetic. The algorithms discussed have been implemented in a linkable library.