Applications and Computational Advances for Solving the QUBO Model

Yu Du, Haibo Wang, Rick Hennig +3 more

Abstract Advances in quantum computing with applications in combinatorial optimization have evolved at an increasing rate in recent years. The quadratic unconstrained binary optimization (QUBO) model is at the center of these developments and has become recognized as an effective alternative method for representing a wide variety of combinatorial optimization problems. Additional momentum has resulted from the arrival of quantum computers and their ability to solve the Ising spin glass problem, another form of the QUBO model. This paper highlights advances in solving QUBO models and extensions to more general polynomial unconstrained binary optimization (PUBO) models as important alternatives to traditional approaches. Computational experience is provided that compares the performance of unique quantum‐inspired metaheuristic solvers—the Next Generation Quantum (NGQ) solver for QUBO models and the NGQ‐PUBO solver for PUBO models—with the performance of CPLEX and the Dwave quantum advantage solver. Extensive results, including experiments with a set of large set partitioning problems representing the largest QUBO models reported in the literature to date, along with maximum diversity and max cut problem sets, disclose that our solvers outperform both CPLEX and Dwave by a wide margin in terms of both computational time and solution quality.

Thorsten Koch, Daniel Rehfeldt, Yuji Shinano

Frank Phillipson, Tariq Bontekoe, Irina Chiscop

Ming Chi

This paper discusses the solution method of the computational resource allocation problem based on the QUBO model, and analyzes the application in combination with the simulated annealing algorithm and the CIM simulator. The reasons for choosing the QUBO model and its advantages in logical reasoning are first introduced, and then the core principles of the QUBO model are analyzed, including its relationship with quadratic unconstrained optimization problems. Then the principles of simulated annealing algorithm and CIM simulator and their applications in problem solving are discussed in detail. In terms of specific problem solving, taking the optimal position of base station setting and the optimal path of overhauling as examples, the problem definition, decision variables, the establishment of QUBO model, and the solving process are described respectively, and the solving process is demonstrated through flowcharts. Finally, the solution results of the base station setup and maintenance path problems are given and the model is evaluated.

Vrinda Mehta, Hans A. De Raedt, Kristel F. L. Michielsen +1 more

Kyungtaek Jun, Rebecca Conley, Yecheng Huang +2 more

Many quantum computing algorithms are being developed with the advent of quantum computers. Solving linear systems is one of the most fundamental problems in almost all of science and engineering. HHL algorithm, a monumental quantum algorithm for solving linear systems on the gate model quantum computers, was invented and several advanced variations have been developed. However, HHL-based algorithms have a lot of limitations in spite of their importance. We address solving linear systems on a D-Wave quantum annealing device. To formulate a quadratic unconstrained binary optimization (QUBO) model for a linear system solving problem, we make use of a linear least-square problem with binary representation of the solution. We validate this QUBO model on the D-Wave system and discuss the results.