Polyhedral Structure of Penalty Constants in Quadratic Unconstrained Binary Optimization and Applications to Quantum Computing.

In recent years, the study of Quadratic Unconstrained Binary Optimization (QUBO) problems has regained importance because it provides a unified framework to model and solve many combinatorial optimization problems (COPT); in particular, several quantum computing algorithms (like QAOA, VQE, quantum annealing algorithms, etc.) can be used to solve QUBO models. In this talk, we will present a polyhedral characterization of the penalty constants that arise when penalization methods are used to reformulate linear and quadratic integer programs as QUBO problems. As a result, we are able to recover previous reformulations and techniques used in the literature; and also obtain QUBO constructions that give a bijective correspondence between their optimal solutions and the ones corresponding to the original problem.

Furthermore, for inequality-constrained combinatorial optimization problems, our approach gives a characterization of QUBO formulations that do not use binary slack variables, but whose penalty constants are hard to find. Finally, we will provide some computational experiments illustrating these ideas.