Quadratic unconstrained binary optimization

Not to be confused with Qubo, a television service owned by Ion Media Networks.

Quadratic unconstrained binary optimization (QUBO) is a pattern matching technique, common in machine learning applications. QUBO is an NP hard problem. Examples of problems that can be formulated as QUBO problems are the Maximum cut, Graph coloring and the Partition problem.

QUBO problems may sometimes be well-suited to algorithms aided by quantum annealing.

QUBO is the problem of minimizing a quadratic polynomial over binary variables. The quadratic polynomial will be of the form $E(X_{1},X_{2},...,X_{N})=\sum _{i=1}^{N}\sum _{j=1}^{i}Q_{ij}\times X_{i}\times X_{j}$ with $X_{i}\in \{0,1\}$ and $Q_{ij}\in R$.

External links

• Endre Boros, Peter L Hammer & Gabriel Tavares (April 2007). "Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)". Journal of Heuristics. 13 (2). Association for Computing Machinery: 99–132. doi:10.1007/s10732-007-9009-3. S2CID 32887708. Retrieved 12 May 2013.
• Di Wang & Robert Kleinberg (November 2009). "Analyzing quadratic unconstrained binary optimization problems via multicommodity flows". Discrete Applied Mathematics. 157 (18). Elsevier: 3746–3753. doi:10.1016/j.dam.2009.07.009. PMC 2808708. PMID 20161596.