17
$\begingroup$

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?

$\endgroup$
8
  • 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 '19 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$ – Nike Dattani Jun 29 '19 at 22:45
  • 5
    $\begingroup$ @RodrigodeAzevedo Maybe you can expand your comment and post is as an answer? $\endgroup$ – Kevin Dalmeijer Jun 30 '19 at 14:06
  • 1
    $\begingroup$ The only real-world application of QUBO I know of is selling Quantum Annealing computers, for instance made by D-Wave. The only thing those computers can do is solve QUBOs. So QUBOs are not only the stare of the art way to sell Quantum Annealing computers, they're the only way. $\endgroup$ – Mark L. Stone Oct 21 '20 at 0:24
  • 1
    $\begingroup$ @MarkL.Stone Well before the existence of commercial quantum annealers, there was a classical algorithm for solving QUBOs, for example in this software called "QPBO" by Vladimir Koplmogorov: pub.ist.ac.at/~vnk/software.html. Surely you must be joking by saying that QUBO is useful for nothing else other than to sell D-Wave machines and to get people to download Kolmogorov's free Software called "QPBO" ? $\endgroup$ – Nike Dattani Oct 21 '20 at 1:57
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$
2
  • 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$ – Nike Dattani Jul 13 '19 at 19:54
  • $\begingroup$ @user1271772 You are correct. I have edited my answer accordingly. $\endgroup$ – brentertainer Jul 16 '19 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$
6
  • 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 '19 at 18:19
  • $\begingroup$ @MichaelFeldmeier, Thanks for your comment, I edited the answer. $\endgroup$ – Oguz Toragay Jul 10 '19 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 '19 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 '19 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 '19 at 1:59
4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ +1. Welcome to the site, and thanks for your contribution! Okay so combinatorial optimization algorithms can involve heuristics which use QUBOs. Is there no better way to do the heuristics, than to use QUBOs? $\endgroup$ – Nike Dattani Oct 21 '20 at 1:53

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.