# Are there any real-world problems where quadratization helps to solve something that couldn't have been solved without quadratization?

The closest thing I know is the computer vision problem, in which an image is de-blurred and/or de-noised by quadratizing a quartic problem into a quadratic optimization problem (QUBO) and then the QUBO is solved. However it seems that deep neural networks solve this computer vision problem much more efficiently. Are there any cases where quadratization is an essential component of a state-of-the-art algorithm for a real-world problem?

A recent paper by Quantum Computing Inc people is showing experiments on graph partitioning where QUBO approaches lead to better results than the state of the art.

Here is the paper: https://arxiv.org/pdf/2006.15067.pdf

Nevertheless, one can argue that this graph partitioning problem is not in essence what we can call a real-world OR problem. But it seems difficult to find publications where real-world optimization problems (that is, with rich, dirty features modeled) are tackled through several optimization techniques fairly compared.

• +1. Very nice find! And great to see a proper answer to this question! How did you come across this? Did you know this paper before you saw my question? Some initial comments: Table 1 shows that the smallest cut is marginally improved in their paper, compared to the "smallest previously known cut" in the same table, but the "smallest previously known cut" is not cited anywhere, so I can't find the papers where those calculations are done. Were they even trying to find the "smallest" cut? Were they done 10 years ago on worse hardware? Oct 18 '20 at 20:59
• Also the "constrained-optimization" in Table 1 gives better results than the QUBO column of the same table (there is not a single case where the QUBO is better than the "constrained optimization") but what exactly is "constrained optimization" in their paper? I do not see a single equation or formula in their paper. Is "constrained optimization" just QUBO with my deduc-reduc method: arxiv.org/abs/1508.04816 applied to simplify the QUBO using the constraints? Oct 18 '20 at 21:01
• I spoke just now to the first-author of Ref. 2 from this paper. He pointed out that the graph partitioning problem (the subject of the paper you linked) has nothing to do with quadratization, since the problem is quadratic to begin with. Perhaps your answer is more relevant here: or.stackexchange.com/q/828/727, but I've still given you +1 because I like this answer more than the other one I got. Oct 18 '20 at 22:14
• Note that for any problem expressed using Boolean variables, you can transform a given linear formulation of the problem into a quadratic one (by elevating each occurrence of the variables in constraints and objectives to the power of two). Conversely, you can transform a given quadratic formulation into a linear one (by applying the traditional linearization techniques for Boolean quadratic expressions). In both cases, the size of the transformed model remains of the same order than the original one. Oct 23 '20 at 19:47
• Why would you convert a linear problem into a quadratic one? Quadratic ones are harder to solve. As for converting from quadratic to linear, you often have to introduce "slack" variables or "auxiliary variables", which make the problem bigger. I personally have not seen people solve QUBO problems by converting it to a linear problem then solving the linear problem, though I've heard that people do this (maybe Henry Wolkowicz, but I think the # of linear variables became the square of the # of quadratic variables?). Oct 23 '20 at 19:51

Are there any cases where quadratization is an essential component of a state-of-the-art algorithm for a real-world problem?

Yes.

Quadratization has been used in pseudo-Boolean optimization (Implementation of QPBO (C++)) and unconstrained binary polynomial optimization problems.

• "Quadratic Reformulation of Nonlinear Pseudo-Boolean Functions via the Constraint Composite Graph", (Jun 2019), by Ka Wa Yip, Hong Xu, Sven Koenig, and T. K. Satish Kumar:

"Abstract:
Nonlinear pseudo-Boolean optimization (nonlinear PBO) is the minimization problem on nonlinear pseudo-Boolean functions (non-linear PBFs). One promising approach to nonlinear PBO is to first use a quadratization algorithm to reduce the PBF to a quadratic PBF by introducing intelligently chosen auxiliary variables and then solve it using a quadratic PBO solver. In this paper, we develop a new quadratization algorithm based on the idea of the constraint composite graph (CCG). We demonstrate its theoretical advantages over state-of-the-art quadratization algorithms. We experimentally demonstrate that our CCG-based quadratization algorithm outperforms the state-of-the-art algorithms in terms of both effectiveness and efficiency on randomly generated instances and a novel reformulation of the uncapacitated facility location problem.
...

Conclusion
We developed the CCG-based quadratization algorithm for the nonlinear PBO on general PBFs and compared it to state-of-the-art algorithms. We first proved the theoretical advantages of the CCG-based quadratization algorithm over other algorithms. We then experimentally verified these advantages. We observed that our CCG-based quadratization algorithm not only significantly outperforms other algorithms on medium-sized and large PBFs but is also preferable for smaller PBFs, to which asymptotic theoretical results are not directly applicable. We also showed that the CCG-based quadratization algorithm is applicable to real-world problems such as the UFLP, especially when the number of users to deliver products to is large.

• "Solving unconstrained 0-1 polynomial programs through quadratic convex reformulation", (Jan 22 2019), by Sourour Elloumi, Amélie Lambert, and Arnaud Lazare (CEDRIC):

"Abstract
We propose an exact solution approach for the problem ($$P$$) of minimizing an unconstrained binary polynomial optimization problem. We call PQCR (Polynomial Quadratic Convex Reformulation) this three-phase method. The first phase consists in reformulating ($$P$$) into a quadratic program ($$QP$$). To that end, we recursively reduce the degree of ($$P$$) to two, by use of the standard substitution of the product of two variables by a new one. We then obtain a linearly constrained binary quadratic program. In the second phase, we rewrite the objective function of ($$QP$$) into an equivalent and parameterized quadratic function using the identity $$x^2_i =x_i$$ and other valid quadratic equalities that we introduce from the reformulation of phase 1. Then, we focus on finding the best parameters to get a quadratic convex program which continuous relaxation’s optimal value is maximized. For this, we build a new semi-definite relaxation ($$SDP$$) of ($$QP$$). Then, we prove that the standard linearization inequalities, used for the quadratization step, are redundant in presence of the new quadratic equalities. Next, we deduce our optimal parameters from the dual optimal solution of ($$SDP$$). The third phase consists in solving ($$QP∗$$), the optimally reformulated problem, with a standard solver. In particular, at each node of the branch-and-bound, the solver computes the optimal value of a continuous quadratic convex program. We present computational results where we compare PQCR with other convexification methods, and with the solver Baron. We evaluate our method on instances of the image restoration problem and the low autocorrelation binary sequence problem from minlplib. For this last problem, 33 instances among the 45 were unsolved in minlplib. We solve to optimality 6 of them, and for the 27 others we improve primal and/or dual bounds.".

• "Quadratization in discrete optimization and quantum mechanics" (Jan 14 2019), by Nike Dattani:

Abstract:
"A book about turning high-degree optimization problems into quadratic optimization problems that maintain the same global minimum (ground state). This book explores quadratizations for pseudo-Boolean optimization, perturbative gadgets used in QMA completeness theorems, and also non-perturbative k-local to 2-local transformations used for quantum mechanics, quantum annealing and universal adiabatic quantum computing. The book contains ~70 different Hamiltonian transformations, each of them on a separate page, where the cost (in number of auxiliary binary variables or auxiliary qubits, or number of sub-modular terms, or in graph connectivity, etc.), pros, cons, examples, and references are given. One can therefore look up a quadratization appropriate for the specific term(s) that need to be quadratized, much like using an integral table to look up the integral that needs to be done. This book is therefore useful for writing compilers to transform general optimization problems, into a form that quantum annealing or universal adiabatic quantum computing hardware requires; or for transforming quantum chemistry problems written in the Jordan-Wigner or Bravyi-Kitaev form, into a form where all multi-qubit interactions become 2-qubit pairwise interactions, without changing the desired ground state. Applications cited include computer vision problems (e.g. image de-noising, un-blurring, etc.), number theory (e.g. integer factoring), graph theory (e.g. Ramsey number determination), and quantum chemistry. The book is open source, and anyone can make modifications here: "Open collaborative book on quadratization in discrete optimization and quantum mechanics".

• "Proximal gradient flow and Douglas-Rachford splitting dynamics: global exponential stability via integral quadratic constraints" (Aug 23 2019), by Sepideh Hassan-Moghaddam and Mihailo R. Jovanović:

Abstract:
"Many large-scale and distributed optimization problems can be brought into a composite form in which the objective function is given by the sum of a smooth term and a nonsmooth regularizer. Such problems can be solved via a proximal gradient method and its variants, thereby generalizing gradient descent to a nonsmooth setup. In this paper, we view proximal algorithms as dynamical systems and leverage techniques from control theory to study their global properties. In particular, for problems with strongly convex objective functions, we utilize the theory of integral quadratic constraints to prove global exponential stability of the differential equations that govern the evolution of proximal gradient and Douglas-Rachford splitting flows. In our analysis, we use the fact that these algorithms can be interpreted as variable-metric gradient methods on the forward-backward and the Douglas-Rachford envelopes and exploit structural properties of the nonlinear terms that arise from the gradient of the smooth part of the objective function and the proximal operator associated with the nonsmooth regularizer. We also demonstrate that these envelopes can be obtained from the augmented Lagrangian associated with the original nonsmooth problem and establish conditions for global exponential convergence even in the absence of strong convexity.".