QUBO Models in Optimization, Machine Learning, and Quantum Computing
The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing, positioning QUBO models at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. The consequences of these new computational technologies and their links to QUBO models are being explored in initiatives by organizations such as Google, Amazon and Lockheed Martin in the commercial realm and Los Alamos National Laboratory, Oak Ridge National Laboratory, Lawrence Livermore National Laboratory and NASA鈥檚 Ames Research Center 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.
We disclose the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. Using simple numerical examples, we show how many different types of constraining relationships arising in practice can be embodied within the 鈥渦nconstrained鈥� QUBO formulation in a very natural manner. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.
This is joint work with Gary Kochenberger, CU Denver.