What are some real-world applications of QUBO?

Question

QUBO (Quadratic Unconstrained Binary Optimization) is the minimization of a quadratic function of binary variables.

It has been used for computer vision, Ramsey numbers, factoring numbers, the integer partitioning problem, the MaxCut problem, and many other problems.

But in the real-world, one would not factor numbers this way, no new Ramsey number has been found by solving a QUBO problem, and it's not the most efficient way to solve the integer partitioning problem.

Are there any real-world problems, for which QUBO is the state-of-the-art way to solve the problem?

Answer 1

1QBit published a white paper "Optimal feature selection in credit scoring and classification using a quantum annealer". The authors compare their feature selecting QUBO model to mainstream recursive feature elimination (RFE) methods.

http://qbit.wpengine.com/wp-content/uploads/2017/04/1QBit_-Optimal-Feature-Selection-in-Credit-Scoring-and-Classification-Using-a-Quantum-Annealer-_2017.04.13.pdf

Quoting from their conclusions:

QUBO Feature Selection delivered a smaller feature set (24 features) than either recursive feature elimination (28 features) or recursive feature elimination with wrapped cross-validation (31 features). All three methods showed comparable accuracy.

The company has quite a few other related white papers. Their research is interesting if only because they had an actual quantum annealer at their disposal for tackling QUBO and its applications.

Answer 2

1. In chapter 10 of his dissertation [1], Gabriel Tavares, talked about some real-world applications of QUBO. He also proposed a new approach to solve QUBOs by modifying some of the previously existed methods.

2. Authors in [2], listed a wide range of important optimization problems that the QUBO model encompasses:

   • Quadratic Assignment Problems
   • Capital Budgeting Problems
   • Multiple Knapsack Problems
   • Task Allocation Problems (distributed computer systems)
   • Maximum Diversity Problems
   • P-Median Problems
   • Asymmetric Assignment Problems
   • Symmetric Assignment Problems
   • Side Constrained Assignment Problems
   • Quadratic Knapsack Problems
   • Constraint Satisfaction Problems (CSPs)
   • Set Partitioning Problems
   • Fixed Charge Warehouse Location Problems
   • Maximum Clique Problems
   • Maximum Independent Set Problems
   • Maximum Cut Problems
   • Graph Coloring Problems
   • Graph Partitioning Problems
   • Number Partitioning Problems
   • Linear Ordering Problems
   • Number Partitioning Problems.

3. In [3], which is a tutorial of modeling and solving combinatorial optimization problems, the authors mention illustrative computational examples of using QUBO in modeling and solving real-world problems in section 5 of the paper including the following examples:

   • Warehouse Location: (Single source, Uncapacitated)
   • Constraint Satisfiability problems (CSPs)
   • Quadratic Knapsack Problems
   • Maximum Diversity
   • Set Partitioning
   • Vertex Coloring
   • Maximum Clique (Max Independent Set)

These are some of the interesting papers that I found in the literature (because of my curiosity - I am not an expert in this field). I believe there should be some valuable clues to follow, in these papers.

[1] Tavares, Gabriel. New algorithms for Quadratic Unconstrained Binary Optimization (QUBO) with applications in engineering and social sciences. Diss. Rutgers University-Graduate School-New Brunswick, 2008.

[2] Glover, Fred, Gary Kochenberger, and Yu Du. "A Tutorial on Formulating and Using QUBO Models." (2019).

[3] Kochenberger, Gary A., and Fred Glover. "A unified framework for modeling and solving combinatorial optimization problems: A tutorial." Multiscale Optimization Methods and Applications. Springer, Boston, MA, 2006. 101-124.

Answer 3

Many state-of-art real-world large-scale combinatorial optimization problems are based on heuristics that use some sort of local search in them. Although not stated directly as a QUBO, many of these local search moves are based on solving a QUBO (with no "tricks" of penalizing the constraints). For example in the Travelling Salesman Problem, the popularly used 2-Opt and 3-Opt moves are in fact QUBOs with no penalized constraints. However, they form a very simple QUBO of just 2 and 3 variables respectively, thus brute force is sufficient to solve these QUBOs. So if you view this as a method that uses QUBOs in a state-of-art method, then there are many other applications, just not directly stated as a QUBO. Take a look at the paper on https://arxiv.org/abs/1911.09810 for more such examples where the QUBO's generate are no longer trivial to solver, for example in local search moves for the Quadratic Assignment Problem.