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

Question

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?

Added: I thank the user named Rob for answering my question when no one else did, but I am still looking for an answer. The copying and pasting of those abstracts from papers that I am very familiar with, was not really what I was looking for (in fact I am an author on one of those papers!). The statement "Quadratization has been used in pseudo-Boolean optimization (Implementation of QPBO (C++)) and unconstrained binary polynomial optimization problems" is not really true, because QPBO happens after quadratization. QPBO is used in exactly the example I already gave (computer vision), but there's better ways to solve that computer vision problem (e.g. deep neural networks) so QPBO and quadratization are both not needed to to solve that problem. The question does not request a list of papers that have used quadratization, but asks for an example of a problem for which no better solution exists without using quadratization because in all examples given so far, the problem can be solved better without quadratization into QUBO form.

Answer 1

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.

Answer 2

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.".