A Tutorial on Formulating and Using QUBO Models. (arXiv:1811.11538v3 [cs.DS] CROSS LISTED)

Recent years have witnessed the remarkable discovery that the Quadratic
Unconstrained Binary Optimization (QUBO) model unifies a wide variety of
combinatorial optimization problems, and moreover is the foundation of
adiabatic quantum computing and a subject of study in neuromorphic computing.
Through these connections, QUBO models lie at the heart of experimentation
carried out with quantum computers developed by D-Wave Systems and neuromorphic
computers developed by IBM and are actively being explored for their research
and practical applications by Google and Lockheed Martin in the commercial
realm and by Los Alamos National Laboratory, Oak Ridge National Laboratory and
Lawrence Livermore National Laboratory in the public sector. Computational
experience is being amassed by both the classical and the quantum computing
communities that highlights not only the potential of the QUBO model but also
its effectiveness as an alternative to traditional modeling and solution
methodologies. This tutorial discloses the basic features of the QUBO model
that give it the power and flexibility to encompass the range of applications
that have thrust it into prominence. We show how many different types of
constraints arising in practice can be embodied within the "unconstrained" QUBO
formulation in a very natural manner using penalty functions, yielding exact
model representations in contrast to the approximate representations produced
by customary uses of penalty functions. Each step of generating such models is
illustrated in detail by simple numerical examples, to highlight the
convenience of using QUBO models in numerous settings. We also describe recent
innovations for solving QUBO models that offer a rich potential for integrating
classical and quantum computing and for applying these models in machine

Article web page: