16
$\begingroup$

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

It has been used for computer vision, Ramsay 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?

$\endgroup$
  • 2
    $\begingroup$ Maybe a QUBO formulation is helpful when using quantum algorithms, like quantum annealing. In that case we may expect QUBO to become more important in the future. However, I am not an expert on this topic. $\endgroup$ – Kevin Dalmeijer Jun 29 at 22:40
  • $\begingroup$ I completely agree, but no real-world problem has been solved faster on a quantum annealer than on a classical computer yet (the biggest quantum annealer has only 2048 qubits, compare that to the trillions of bits in your laptop). $\endgroup$ – user1271772 Jun 29 at 22:45
  • $\begingroup$ Boolean least-squares to reconstruct digital signals. $\endgroup$ – Rodrigo de Azevedo Jun 30 at 13:13
  • 5
    $\begingroup$ @RodrigodeAzevedo Maybe you can expand your comment and post is as an answer? $\endgroup$ – Kevin Dalmeijer Jun 30 at 14:06
  • $\begingroup$ @RodrigodeAzevedo, I would definitely upvote your answer if you were to elaborate a bit. For example, a citation to a paper or review article/survey. Or comparison of cost to the previous state-of-the-art method, or leading competitor. $\endgroup$ – user1271772 Jun 30 at 14:27
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ They don't have a quantum annealer. They used to use D-Wave's quantum annealer, but are now backed by Fujitsu (who makes classical annealers) and I haven't seen them use a quantum annealer ever since. Perhaps they've used the D-Wave annealer recently and I didn't find out about it, but the point is still that they do not "have" a quantum annealer (which would cost them $10 million), they have just used such annealers in the past. $\endgroup$ – user1271772 Jul 13 at 19:54
  • $\begingroup$ @user1271772 You are correct. I have edited my answer accordingly. $\endgroup$ – brentertainer Jul 16 at 17:38
5
$\begingroup$
  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.

$\endgroup$
  • 4
    $\begingroup$ This answer could be improved by actually mentioning the applications, not just references to them. If there are too many to list them all, consider listing a few of them. $\endgroup$ – Michael Feldmeier Jul 10 at 18:19
  • $\begingroup$ @MichaelFeldmeier, Thanks for your comment, I edited the answer. $\endgroup$ – Oguz Toragay Jul 10 at 18:39
  • 1
    $\begingroup$ Thanks! I didn't look into the papers yet, but are all of those problem formulations really unconstrained? $\endgroup$ – Michael Feldmeier Jul 10 at 19:08
  • 2
    $\begingroup$ I think the problems are constrained, but we can convert them to a QUBO theoretically. A conventional trick is to penalize linear constraints, possibly by squaring it and bring it to the objective function though some tricks could be used depending on the problem. However, I am doubtful that QUBO is the state of the art method for any of these problems. $\endgroup$ – Siong Thye Goh Jul 11 at 1:54
  • $\begingroup$ @SiongThyeGoh, you are right, the authors mentioned some of those "tricks" to penalize the constraints. Actually, in [3], 0-1 formulation of the problems was given and after appropriate conversion, QUBO was used to solve some examples. $\endgroup$ – Oguz Toragay Jul 11 at 1:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.