Computing Local Optima in Quadratic Unconstrained Binary Optimization Problems in Randomized Polynomial Time

Gary A. Kochenberger, Jin‐Kao Hao, Fred Glover +4 more

Amit Verma, Mark W. Lewis

The broad applicability of Quadratic Unconstrained Binary Optimization (QUBO) constitutes a general-purpose modeling framework for combinatorial optimization problems and are a required format for gate array and quantum annealing computers. QUBO annealers as well as other solution approaches benefit from starting with a diverse set of solutions with local optimality an additional benefit. This paper presents a new method for generating a set of one-flip local optima leveraging constraint programming. Further, as demonstrated in experimental testing, analysis of the solution set allows the generation of soft constraints to help guide the optimization process.

Karthik Natarajan, Dongjian Shi, Kim-Chuan Toh

In this paper, we consider a binary quadratic program (BQP) with random objective coefficients. Given only information on the marginal distributions of the objective coefficients, we propose a tight bound on the expected optimal value of the random BQP. We show that the complexity of computing this bound does not increase substantially with respect to the complexity of solving the corresponding deterministic BQP. For the quadratic unconstrained binary optimization (QUBO) problem with nonnegative off-diagonal random entries, the bound is shown to be computable in polynomial time. We generalize the asymptotic bound for the random quadratic assignment problem from independent random variables to dependent random variables and propose a new closed-form bound on the expected optimal value of the quadratic k-cluster problem. We also provide polynomial time computable upper bounds on the expected optimal value for the NP-hard instances using the linear and semidefinite programming relaxation of the deterministic BQP. The semidefinite programming bound of the expected optimal value of the random MAX-CUT problem inherits the approximation ratio of 0.878 from the semidefinite relaxation of the deterministic MAX-CUT problem. Computational experiments on random QUBO problems and random quadratic knapsack problems provide evidence of the quality of the bounds. Overall, our results indicate that the new bound on the expected optimal value of the random BQP is attractive since it exploits many of the nice results and formulations of the deterministic BQP and is valid under limited distributional information.

Peter Merz, Bernd Freisleben

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.